链表

Mr.ZhaoAbout 4 min

本文部分图片来自：Hello算法，https://www.hello-algo.com/open in new window

1. 什么是链表

链表和数组相似，它们都是有序的列表、都是线性结构（有且仅有一个前驱、有且仅有一个后继）

不同点在于，链表中，数据单位的名称叫做“结点”，而结点和结点的分布，在内存中可以是离散的

在链表中，每一个结点的结构都包括了两部分的内容：数据域和指针域

2. 链表实现

JS 中的链表，是以嵌套的对象的形式来实现的：

{
    // 数据域
    val: 1,
    // 指针域，指向下一个结点
    next: {
        val:2,
        next: ...
    }
}

数据域存储的是当前结点所存储的数据值，而指针域则代表下一个结点（后继结点）的引用。有了 next 指针来记录后继结点的引用，每一个结点至少都能知道自己后面的是哪位了，原本相互独立的结点之间就有联系

要想访问链表中的任何一个元素，我们都得从起点结点开始，逐个访问 next，一直访问到目标结点为止。为了确保起点结点是可抵达的，我们有时还会设定一个 head 指针来专门指向链表的开始位置

1. 链表结点的创建

创建链表结点，需要一个构造函数：

function ListNode(val) {
    this.val = val;
    this.next = null;
}

在使用构造函数创建结点时，传入 val （数据域对应的值内容）、指定 next （下一个链表结点）即可：

const node = new ListNode(1);
node.next = new ListNode(2);

以上，就创建出了一个数据域值为1，next 结点数据域值为2的链表结点：

2. 链表元素的插入

在链表尾部添加：直接将尾部的next指针指向要添加的元素结点即可

在两个结点间插入一个结点：

过程演示：
JS数据结构与算法-链表04.png

代码实现：

// 如果目标结点本来不存在，那么记得手动创建
const P = new ListNode(0);     
// 把p的 next 指针指向 n1（即 n0.next）
P.next = n0.next;
// 把n0的 next 指针指向 nodeP
n0.next = P;

3. 链表元素的删除

我们直接让要删除结点的前驱结点的 next 指针跳过它，指向要删除结点的后继即可

过程演示：

代码实现：

n0.next = P.next;

4. 链表的遍历

let p = node;
while(p){
    console.log(p.val);
    p = p.next;
}

3. 链表与数组

1. JS中的数组

在JS中，如果我们在一个数组中只定义了一种类型的元素，如：

const arr = [1,2,3,4];

它是一个纯数字数组，那么对应的确实是连续内存

但如果我们定义了不同类型的元素：

const arr = ['haha', 1, {a:1}];

它对应的就是一段非连续的内存。此时，JS 数组不再具有数组的特征，其底层使用哈希映射分配内存空间，是由对象链表来实现的

2. 链表的特点

有高效的增删操作，但是访问操作很麻烦

// 记录目标结点的位置
const index = 10;  
// 设一个游标指向链表第一个结点，从第一个结点开始遍历
let node = head;  
// 反复遍历到第10个结点为止
for(let i=0;i<index&&node;i++) {
    node = node.next;
}

随着链表长度的增加，我们搜索的范围也会变大、遍历其中任意元素的时间成本自然随之提高。这个变化的趋势呈线性规律，用大 O 表示法表示为 O(n)

但在数组中，我们直接访问索引、可以做到一步到位，这个操作的复杂度会被降级为常数级别(O(1))

和数组相比，内存空间消耗更大，因为每个存储数据的结点都需要额外的空间存储后继指针

链表

# 1. 什么是链表

# 2. 链表实现

# 1. 链表结点的创建

# 2. 链表元素的插入

# 3. 链表元素的删除

# 4. 链表的遍历

# 3. 链表与数组

# 1. JS中的数组

# 2. 链表的特点