什么是链表？

链表数据结构

链表的核心思想：分离存储与连接

1. 链表的物理存储 vs 逻辑结构

物理存储（内存中）：

javascript

// 节点在内存中是分散的，通过地址连接
地址0x100: {val: 1, next: 0x200}
地址0x200: {val: 2, next: 0x300}
地址0x300: {val: 3, next: 0x400}
地址0x400: {val: 4, next: 0x500}
地址0x500: {val: 5, next: null}

存储结构：

// 假设内存情况
class Node {
  constructor(value) {
    this.value = value;  // 假设value占4字节
    this.next = null;    // 指针占8字节（64位系统）
  }
}

// 创建链表：1 -> 2 -> 3
const node1 = new Node(1);  // 假设分配在地址0x1000
const node2 = new Node(2);  // 假设分配在地址0x2000（不连续！）
const node3 = new Node(3);  // 假设分配在地址0x1500（还是不连续！）

node1.next = node2;  // 0x1000处的next字段存储0x2000
node2.next = node3;  // 0x2000处的next字段存储0x1500

逻辑结构（我们看到的）：

text

head(0x100)
  ↓
[1|next→0x200] → [2|next→0x300] → [3|next→0x400] → [4|next→0x500] → [5|next→null]

链表操作：

head 的作用：

• 它是访问链表的唯一入口
• 如果丢失了 head，整个链表就无法访问
• 它应该始终指向链表的第一个节点（除非特别设计）
  在函数中操作时：

//遍历时， current作为临时‘探针’，负责移动和寻找位置
let cur = head  //避免直接操作head，创建cur指向head指向的节点

####✅

链表 = 头节点 + 连接关系

反转链表 = 改变连接方向 + 更新头节点

链表中，你永远只需要关心两件事：

1. 头节点在哪里（访问入口）
2. 节点之间的连接关系

链表如何遍历

最基础的 while 循环遍历

function traverseBasic(head) {
    let current = head;  // 关键：使用临时变量
    // 遍历所有节点，到最后current为null，while(current.next)这样current是最后一个节点
    while (current !== null) {
        console.log(current.val);  // 处理当前节点
        current = current.next;    // 移动到下一个
    }
}

示例：查找值

// 示例：查找值
function findValue(head, target) {
    let current = head;
    
    while (current !== null) {
        if (current.val === target) {
            return true;  // 找到了
        }
        current = current.next;
    }
    
    return false;  // 没找到
}

链表的节点本质：

链表节点是特殊用途的对象

// 链表节点就是一个JavaScript对象
const node = {
    val: 10,          // 存储的数据
    next: null        // 指向下一个节点的引用
};

// 或者用class创建，本质上也是对象
class ListNode {
    constructor(val) {
        this.val = val;    // 属性1：数据
        this.next = null;  // 属性2：指向下一个对象的引用
    }
}

const node2 = new ListNode(20);
// node2在内存中：{val: 20, next: null}

链表的插入删除

头部插入(O(1)

function insertAtHead(head, val) {
    let newPoint = new ListNode(val);
    newPoint.next = head;
    return newPoint;
}
insertAtHead(head, 1)

尾部插入(O(n))

function insertAtEnd(head, val) {
    let newPoint = new ListNode(val);
    let current = head;
    while (current) {
        current = current.next;
    }
    current.next = newPoint;
    return head
}
insertAtEnd(head, 4)

指定位置插入(O(n))

function insertAtIndex(head, index, val) {
    // 索引为0，代表在头部插入
    if (index === 0) {
        insertAtHead(head, val)
    }
    let current = head;
    const newPoint = new ListNode(val)
    let position = 0;
    while(current && position < index - 1) {
        current = current.next;
        position++;
    }
    newPoint.next = current.next;
    current.next = newPoint.next;
    return head
}

删除头节点

function deleteAtHead(head) {
    if (!head) return null;
    return head.next;
}

删除尾节点

function deleteAtEnd(head) {
    if (!head || !head.next) return null;
    let current = head;
    //移动到倒数第二个节点
    if (current.next && current.next.next) {
        current = current.next;
    }
    current.next = null;
    return head;
}

删除指定值的节点

function deleteByValue(head, val) {
    if (head && head.val == val) {
        return head.next;
    }
    let current = head;
    while (current.next) {
        if (current.next.val == val) {
            current.next = current.next.next;
            break;
        }
        current = current.next;
    }
    return head;
}

双向链表

双向链表 (Doubly Linked List) 每一个节点（Node）都由三部分组成：

1. Value: 存储的数据。
2. Next: 指向后一个节点的指针。
3. Prev: 指向前一个节点的指针。

class ListNode {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null;
  }
}