03- 链表

认识

链表（Linked List） 是一种 线性数据结构，与数组类似，也用来存储一系列的元素。与数组不同的是，链表中的元素不是按连续的内存地址存储的，而是通过 节点（Node）之间的 指针（或引用）连接起来。

链表是多个元素组成的列表，元素存储不连续，用next指针连在一起。JavaScript中没有链表，但是可以用Object模拟链表。

基本概念

一个链表由多个 节点（Node）组成，每个节点包含两个部分（数据+指针）

1. 数据部分：存储节点的数据。
2. 指针部分：指向下一个节点的引用。对于链表中的最后一个节点，指针部分为 null 或 undefined，表示链表的结束。

类型

• 单向链表（Singly Linked List）：每个节点指向下一个节点，链表是单向的。
• 双向链表（Doubly Linked List）：每个节点有两个指针，一个指向下一个节点，一个指向前一个节点。
• 循环链表（Circular Linked List）：链表的最后一个节点指向链表的头节点，形成循环。

链表与数组的比较

链表的常见操作

1. 插入（Insertion）：可以在链表的头部、尾部或任意位置插入节点。
2. 删除（Deletion）：可以删除链表的头部、尾部或指定位置的节点。
3. 遍历（Traversal）：从头节点开始逐一访问链表中的每个节点，直到链表的结束。
4. 查找（Search）：查找链表中是否有某个特定的数据。

在 JavaScript 中如何理解链表

在 JavaScript 中，链表通常通过 对象 来实现，因为 JavaScript 对象本身就能存储 键值对，而每个节点的指针可以用对象的属性来表示。

TS实现

 /**
 * 定义一个 node 节点
 */
interface ILinkListNode {
    value: number
    next?: ILinkListNode
}

/**
 * 根据数组创建单向链表
 * @param arr 
 * @returns 
 */
function createLinkList(arr: number[]): ILinkListNode {
    const len = arr.length
    if (len === 0) throw new Error('arr is empty')

    let curNode: ILinkListNode = {
        value: arr[len - 1]
    }
    if (len === 1) return curNode

    for (let i = len - 2; i >= 0; i--) {
        curNode = {
            value: arr[i],
            next: curNode 
        }
    }

    return curNode
}

使用场景

• 场景一：JS中的原型链
• 场景二：使用链表指针获取 JSON 的节点值

LeetCode题目

● 237. 删除链表中的节点
● 206. 反转链表
● 2. 两数相加
● 83. 删除排序链表中的重复元素
● 141. 环形链表

单向链表的实现

// 节点类
class Node {
    constructor(data) {
        this.data = data; // 节点数据
        this.next = null; // 指向下一个节点的指针
    }
}

// 链表类
class LinkedList {
    constructor() {
        this.head = null; // 链表的头部
    }

    // 添加节点到链表尾部
    append(data) {
        const newNode = new Node(data);
        
        // 如果链表为空，将新节点设置为头节点
        if (!this.head) {
            this.head = newNode;
            return;
        }
        
        // 否则找到链表的最后一个节点，并将其 next 指向新节点
        let current = this.head;
        while (current.next) {
            current = current.next;
        }
        current.next = newNode;
    }

    // 打印链表的所有节点
    print() {
        let current = this.head;
        let output = '';
        while (current) {
            output += current.data + ' -> ';
            current = current.next;
        }
        console.log(output + 'null');
    }

    // 查找某个节点
    find(data) {
        let current = this.head;
        while (current) {
            if (current.data === data) {
                return current;
            }
            current = current.next;
        }
        return null;
    }

    // 删除某个节点
    remove(data) {
        if (!this.head) return; // 链表为空
        
        // 如果要删除的是头节点
        if (this.head.data === data) {
            this.head = this.head.next;
            return;
        }
        
        let current = this.head;
        while (current.next) {
            if (current.next.data === data) {
                current.next = current.next.next;
                return;
            }
            current = current.next;
        }
    }
}

// 测试链表操作
let list = new LinkedList();
list.append(10);  // 添加节点 10
list.append(20);  // 添加节点 20
list.append(30);  // 添加节点 30
list.print();     // 打印链表 10 -> 20 -> 30 -> null

console.log(list.find(20));  // 查找值为 20 的节点
list.remove(20);             // 删除值为 20 的节点
list.print();                // 打印链表 10 -> 30 -> null

实际应用

1. 动态内存管理：链表在内存中分配空间时，不需要连续的内存空间，可以有效地利用碎片化的内存。
2. 实现队列和栈：链表可以用来实现队列（FIFO）和栈（LIFO）。链表的插入和删除操作是 O(1) 的，非常适合用来实现这两种数据结构。
3. 处理大量数据：对于大小动态变化的数据集，链表非常适合，因为它能够灵活地扩展而不需要移动已有的数据。