什么是链表?

菜园前端
• 阅读 428

原文链接:https://note.noxussj.top/?source=helloworld


什么是链表?

链表是有序的数据结构,链表中的每个部分称为节点。可以首、尾、中间进行数据存取,链表的元素在内存中不必是连续的空间,每个节点通过 next 指针指向下一个节点。

什么是链表?

优点

链表的添加和删除不会导致其余元素位移。

缺点

无法根据索引快速定位元素。

数组和链表区别

  • 获取、修改元素时,数组效率高
  • 添加、删除元素时,链表效率高
  • 数组添加、移除会导致后续元素位移,性能开销大

环形链表

指的是链表最后一个节点的 next 指向第一个节点,形成首尾相连的循环结构。

链表环路检测

解题思路

  1. 快慢指针法实现
  2. slow 指针每次移动一位,fast 指针每次移动两位,如果他们相遇则说明链表存在环
  3. 新指针 ptr 从 head 开始移动,与 slow 相遇的位置即为环的起点
  4. 由 fast 指针移动距离为 slow 的两倍可得出公式: a + (nb + nc + b) = 2(a + b)
  5. 变化处理后得到新公式: a = (n - 1)(b + c) + c

什么是链表?

实现功能

在 JavaScript 中没有链表,我们可以通过模拟一个类或者是通过 Object 实现链表的所有功能。

节点类

  • value 当前节点值
  • next 指向下一个节点

链表类

  • addAtTail 尾部添加节点
  • addAtHead 头部添加节点
  • addAtIndex () 指定位置添加节点
  • get 获取节点
  • removeAtIndex () 删除指定节点

应用场景

  • leetcode 两数相加

基础案例

通过对象实现

// 链表
let a = { val: 'a', next: null }
let b = { val: 'b', next: null }
let c = { val: 'c', next: null }
let d = { val: 'd', next: null }

a.next = b
b.next = c
c.next = d

// 尾部添加节点
let e = { val: 'e', next: null }
d.next = e

// 头部添加节点
let z = { val: 'z', next: null }
z.next = a
a = z

// 指定位置添加节点
let f = { val: 'f', next: null }
c.next = f
f.next = d

// 删除指定节点
d.next = null

通过类模拟实现

/**
 * 节点类
 */
class Node {
    constructor(value) {
        this.value = value
        this.next = null
    }
}

/**
 * 链表类
 */
class Link {
    constructor() {
        this.head = null
        this.count = 0
    }

    /**
     * 尾部添加节点
     */
    addAtTail(item) {
        if (this.count === 0) {
            this.head = new Node(item)

            this.count++

            return this.head
        }

        let endNode = this.head

        while (endNode.next) {
            endNode = endNode.next
        }

        endNode.next = new Node(item)

        this.count++

        return item
    }

    /**
     * 头部添加节点
     */
    addAtHead(item) {
        if (this.head) {
            const oldHead = this.head

            this.head = new Node(item)
            this.head.next = oldHead
        } else {
            this.head = new Node(item)
        }

        this.count++

        return item
    }

    /**
     * 指定位置添加节点
     */
    addAtIndex(index, item) {
        if (this.isInvalidIndex(index) || !this.head) {
            return -1
        }

        if (index === 0) {
            this.addAtHead(item)

            return item
        }

        let prev = this.head

        while (index > 0) {
            index--
        }

        const next = prev.next

        const cur = new Node(item)

        prev.next = cur
        cur.next = next

        this.count++

        return item
    }

    /**
     * 获取节点
     */
    get(index) {
        if (this.isInvalidIndex(index) || !this.head) {
            return -1
        }

        let cur = this.head

        while (index > 0) {
            cur = cur.next

            index--
        }

        return cur
    }

    /**
     * 删除指定节点
     */
    removeAtIndex(index) {
        if (this.isInvalidIndex(index) || !this.head) {
            return -1
        }

        if (index === 0) {
            const oldHead = this.head
            this.head = this.head.next

            this.count--

            return oldHead
        }

        let prev = this.head

        while (index - 1 > 0) {
            prev = prev.next

            index--
        }

        const cur = prev.next

        prev.next = cur.next

        this.count--

        return cur
    }

    /**
     * 判断index是否为空,是否超出数据长度大小
     */
    isInvalidIndex(index) {
        if (index === '' || index === null || index === undefined || index < 0 || index > this.count - 1) {
            return true
        }

        return false
    }
}

const link = new Link()

link.addAtTail('a')
link.addAtTail('b')
link.addAtTail('c')
点赞
收藏
评论区
推荐文章
22 22
3年前
【数据结构之链表】详细图文教你花样玩链表
【系列文章推荐阅读】0.提要钩玄文章已经介绍了链式存储结构,介绍了链式存储结构的最基本(简单)实现——单向链表。单向链表,顾名思义,它是单向的。因为单链表的每个结点只有一个数据域和一个指针域,而该指针域只存储了下一个结点的地址,所以我们只能通过某结点找到其直接后继结点,却不能通过某节点找到其直接前驱结点。此外,由于单链表到尾结点(链表的最后一
Easter79 Easter79
3年前
tbox链表list和list_entry的使用
TBOX中提供了各种列表操作:1.list:元素在内部维护的双向链表2.list\_entry:元素在外部维护的双向链表3.single\_list:元素在内部维护的单向链表4.single\_list\_entry:元素在外部维护的单向链表由于双链和单链的接口使用类似,这里主要就
似梦清欢 似梦清欢
2年前
查找算法
顺序查找顺序查找又称为线性查找,对线性表和链表都适用。线性表可以通过数组下标递增来顺序扫描每个元素,链表可以通过next指针依次扫描每一个元素。:::tip指针实现顺序表时,顺序表中是指针时,在定义顺序表的结构体后,需要对顺序表初始化,初始化时为指针申请堆
Souleigh ✨ Souleigh ✨
4年前
JS 实现单链表
要存储多个元素,数组(或列表)可能是最常用的数据结构。但这种数据结构有一个缺点:(在大多数语言中)数据的大小是固定的,从数组的起点或中间插入或移除项的成本很高。  链表存储有序的集合,但不同于数组,链表中的元素在内存中并不是连续放置的。每个元素由一个存储元素本身的节点和一个指向下一个元素的引用(也称指针或链接)组成。  相对于传统的数组,链表的一个好处是
Wesley13 Wesley13
3年前
275,环形链表 II
给定一个链表,返回链表开始入环的第一个节点。 如果链表无环,则返回null。为了表示给定链表中的环,我们使用整数 pos 来表示链表尾连接到链表中的位置(索引从0开始)。如果 pos 是 1,则在该链表中没有环。说明:不允许修改给定的链表。示例1:输入:head3,2,0,4,pos
Wesley13 Wesley13
3年前
Java实现单链表反转操作
单链表是一种常见的数据结构,由一个个节点通过指针方式连接而成,每个节点由两部分组成:一是数据域,用于存储节点数据。二是指针域,用于存储下一个节点的地址。在Java中定义如下:publicclassNode{privateObjectdata;//数据域privateNodenext;//指针域publicNo
Wesley13 Wesley13
3年前
Java HashSet集合的子类LinkedHashSet集合
说明HashSet保证元素的唯一性,可是元素存放进去是没有顺序的。在HashSet下面有一个子类java.util.LinkedHashSet,它是链表哈希表(数组链表或者数组红黑树)组合的一个数据结构。即相对HashSet而言,多了一个链表结构。多了的那条链表,用来记录元素的存储顺序,保证元素有序举例Hash
Stella981 Stella981
3年前
C#Redis列表List
转载自:https://www.cnblogs.com/5ishare/p/6291034.html一、前戏 在Redis中,List类型是按照插入顺序排序的字符串链表。和数据结构中的普通链表一样,我们可以在其头部(left)和尾部(right)添加新的元素。在插入时,如果该键并不存在,Redis将为该键创建一个新的链表。与此相反,如果链表中所有的元
Wesley13 Wesley13
3年前
D1
1\.数据结构  1.1线性结构  (1)最常用的数据结构,特点是数据元素之间存在一对一的线性关系  (2)有两种不同的存储结构,即顺序存储结构和链式存储结构    顺序存储的线性表称为顺序表,顺序表中的存储元素是连续的    链式存储的线性表称为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息