javascript

手写链表：单向与双向链表的完整实现

By AI-Writer 22 min read

手写链表：单向与双向链表的完整实现

链表（Linked List）是一种非连续、非顺序的线性数据结构。与数组不同，链表的元素在内存中不必相邻，它们通过**指针（引用）**串联起来。这种特性使链表在插入和删除操作上具有天然的优势，但也付出了随机访问能力较弱的代价。

本文将手写实现单向链表和双向链表，深入剖析指针操作的本质，并通过经典的约瑟夫斯问题展示链表的实战价值。

链表 vs 数组：核心差异

在动手实现之前，先理解链表与数组的根本区别：

特性数组（Array）链表（Linked List）
内存布局连续存储分散存储，通过指针连接
随机访问O(1)O(n)
头部插入/删除O(n)O(1)
尾部插入/删除O(1) 均摊O(n)（需遍历找尾）
中间插入/删除O(n)O(n)（查找）+ O(1)（修改指针）
内存占用紧凑，可能预分配额外存储指针，灵活分配

数组适合频繁读取、极少修改的场景；链表适合频繁插入删除、顺序遍历的场景。

单向链表（Singly Linked List）

单向链表的每个节点只包含数据和指向下一个节点的引用。最后一个节点的 next 指向 null。

节点定义

js
class ListNode {
  constructor(data) {
    this.data = data;   // 节点存储的数据
    this.next = null;   // 指向下一个节点的引用
  }
}

完整实现

js
class SinglyLinkedList {
  constructor() {
    this.head = null;   // 头节点
    this.tail = null;   // 尾节点
    this.length = 0;    // 链表长度
  }

  // 在尾部追加元素
  append(data) {
    const newNode = new ListNode(data);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++;
  }

  // 在头部插入元素
  prepend(data) {
    const newNode = new ListNode(data);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head = newNode;
    }

    this.length++;
  }

  // 在指定索引处插入元素
  insert(index, data) {
    if (index < 0 || index > this.length) {
      throw new Error('索引越界');
    }

    if (index === 0) {
      this.prepend(data);
      return;
    }

    if (index === this.length) {
      this.append(data);
      return;
    }

    const newNode = new ListNode(data);
    let current = this.head;

    // 找到目标位置的前一个节点
    for (let i = 0; i < index - 1; i++) {
      current = current.next;
    }

    newNode.next = current.next;
    current.next = newNode;
    this.length++;
  }

  // 删除指定索引处的元素
  removeAt(index) {
    if (index < 0 || index >= this.length) {
      throw new Error('索引越界');
    }

    // 删除头节点
    if (index === 0) {
      const removed = this.head;
      this.head = this.head.next;
      // 如果链表只有一个元素，更新 tail
      if (this.length === 1) {
        this.tail = null;
      }
      this.length--;
      return removed.data;
    }

    let current = this.head;

    // 找到目标位置的前一个节点
    for (let i = 0; i < index - 1; i++) {
      current = current.next;
    }

    const removed = current.next;
    current.next = removed.next;

    // 如果删除的是尾节点，更新 tail
    if (index === this.length - 1) {
      this.tail = current;
    }

    this.length--;
    return removed.data;
  }

  // 查找元素，返回索引；未找到返回 -1
  indexOf(data) {
    let current = this.head;
    let index = 0;

    while (current) {
      if (current.data === data) {
        return index;
      }
      current = current.next;
      index++;
    }

    return -1;
  }

  // 获取指定索引处的元素
  get(index) {
    if (index < 0 || index >= this.length) {
      return undefined;
    }

    let current = this.head;
    for (let i = 0; i < index; i++) {
      current = current.next;
    }

    return current.data;
  }

  // 反转链表 —— 面试高频题
  reverse() {
    let prev = null;
    let current = this.head;
    this.tail = this.head; // 原来的头变成尾

    while (current) {
      const nextTemp = current.next; // 暂存下一个节点
      current.next = prev;           // 反转指针方向
      prev = current;                // prev 前移
      current = nextTemp;            // current 前移
    }

    this.head = prev; // 新的头节点
  }

  // 打印链表内容
  toString() {
    const values = [];
    let current = this.head;

    while (current) {
      values.push(current.data);
      current = current.next;
    }

    return values.join(' -> ');
  }

  // 清空链表
  clear() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }
}

反转链表的图解

反转链表是面试中最常考的链表操作题。核心逻辑是用三个指针遍历链表，逐步将每个节点的 next 指向前一个节点：

plaintext
初始:  1 -> 2 -> 3 -> 4 -> null
       ↑
      head

步骤 1: null <- 1    2 -> 3 -> 4 -> null
                ↑      ↑
               prev  current

步骤 2: null <- 1 <- 2    3 -> 4 -> null
                     ↑      ↑
                    prev  current

最终: null <- 1 <- 2 <- 3 <- 4
                            ↑
                           head

使用示例

js
const list = new SinglyLinkedList();
list.append(10);
list.append(20);
list.append(30);
list.prepend(5);
list.insert(2, 15);

console.log(list.toString()); // 5 -> 10 -> 15 -> 20 -> 30
console.log(list.get(2));     // 15

list.reverse();
console.log(list.toString()); // 30 -> 20 -> 15 -> 10 -> 5

list.removeAt(2);
console.log(list.toString()); // 30 -> 20 -> 10 -> 5

双向链表（Doubly Linked List）

单向链表只能单向遍历，删除节点时必须找到其前驱节点。双向链表在每个节点中额外存储了指向前驱节点的引用，支持双向遍历，操作更加灵活。

节点定义

js
class DoublyListNode {
  constructor(data) {
    this.data = data;
    this.prev = null;   // 指向前一个节点
    this.next = null;   // 指向后一个节点
  }
}

完整实现

js
class DoublyLinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.length = 0;
  }

  append(data) {
    const newNode = new DoublyListNode(data);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.prev = this.tail;
      this.tail.next = newNode;
      this.tail = newNode;
    }

    this.length++;
  }

  prepend(data) {
    const newNode = new DoublyListNode(data);

    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      newNode.next = this.head;
      this.head.prev = newNode;
      this.head = newNode;
    }

    this.length++;
  }

  // 在指定索引处插入
  insert(index, data) {
    if (index < 0 || index > this.length) {
      throw new Error('索引越界');
    }

    if (index === 0) {
      this.prepend(data);
      return;
    }

    if (index === this.length) {
      this.append(data);
      return;
    }

    const newNode = new DoublyListNode(data);

    // 判断从头部还是尾部遍历更快
    let current;
    if (index < this.length / 2) {
      current = this.head;
      for (let i = 0; i < index; i++) {
        current = current.next;
      }
    } else {
      current = this.tail;
      for (let i = this.length - 1; i > index; i--) {
        current = current.prev;
      }
    }

    // 插入新节点
    newNode.prev = current.prev;
    newNode.next = current;
    current.prev.next = newNode;
    current.prev = newNode;

    this.length++;
  }

  // 删除指定索引处的元素
  removeAt(index) {
    if (index < 0 || index >= this.length) {
      throw new Error('索引越界');
    }

    // 只有一个节点
    if (this.length === 1) {
      const removed = this.head;
      this.head = null;
      this.tail = null;
      this.length = 0;
      return removed.data;
    }

    // 删除头节点
    if (index === 0) {
      const removed = this.head;
      this.head = this.head.next;
      this.head.prev = null;
      this.length--;
      return removed.data;
    }

    // 删除尾节点
    if (index === this.length - 1) {
      const removed = this.tail;
      this.tail = this.tail.prev;
      this.tail.next = null;
      this.length--;
      return removed.data;
    }

    // 找到目标节点（双向遍历优化）
    let current;
    if (index < this.length / 2) {
      current = this.head;
      for (let i = 0; i < index; i++) {
        current = current.next;
      }
    } else {
      current = this.tail;
      for (let i = this.length - 1; i > index; i--) {
        current = current.prev;
      }
    }

    current.prev.next = current.next;
    current.next.prev = current.prev;
    this.length--;

    return current.data;
  }

  // 正向遍历
  toString() {
    const values = [];
    let current = this.head;

    while (current) {
      values.push(current.data);
      current = current.next;
    }

    return values.join(' <-> ');
  }

  // 反向遍历
  toReverseString() {
    const values = [];
    let current = this.tail;

    while (current) {
      values.push(current.data);
      current = current.prev;
    }

    return values.join(' <-> ');
  }
}

双向链表的优势在于支持双向遍历，在查找靠近尾部的节点时，可以从 tail 反向遍历，将时间减少一半。

实战：约瑟夫斯问题

约瑟夫斯问题（Josephus Problem）是一个经典的数学问题：

n 个人围成一圈，从第一个人开始报数，报到 k 的人被淘汰，下一个人从 1 开始重新报数，直到所有人都被淘汰。求幸存者的初始编号。

链表天然适合模拟环形结构，是解决此问题的理想数据结构。

js
function josephus(n, k) {
  if (n <= 0 || k <= 0) return -1;

  // 构建环形链表
  const head = new ListNode(1);
  let current = head;

  for (let i = 2; i <= n; i++) {
    current.next = new ListNode(i);
    current = current.next;
  }

  // 尾节点指向头节点，形成环
  current.next = head;

  // 开始淘汰
  current = head;
  while (current.next !== current) {
    // 报数 k-1 次，找到第 k 个人的前一个人
    for (let i = 1; i < k - 1; i++) {
      current = current.next;
    }

    // current.next 就是要淘汰的人
    const eliminated = current.next;
    console.log(`淘汰: ${eliminated.data}`);

    // 跳过被淘汰的人
    current.next = eliminated.next;
    current = current.next;
  }

  return current.data; // 最后剩下的幸存者
}

console.log(`幸存者: ${josephus(7, 3)}`);
// 淘汰: 3 -> 6 -> 2 -> 7 -> 5 -> 1
// 幸存者: 4

环形链表的关键在于让尾节点指向头节点，淘汰操作只需要修改指针跳过对应节点即可，无需移动任何数据。

总结

链表的核心在于指针操作。理解以下几点，你就能驾驭链表：

  1. 插入操作：先连接新节点，再断开旧连接，避免丢失链表后半段
  2. 删除操作：用临时变量保存要删除的节点，修改前驱的 next 指向后继
  3. 边界处理：始终考虑空链表、单节点链表、头节点、尾节点的特殊情况
  4. 遍历安全：操作前保存 next 引用，防止修改指针后丢失遍历路径

链表是树、图等更复杂结构的基石。掌握链表的手写实现，意味着你已经迈入了数据结构的深水区。

#javascript #data-structure #algorithm #linked-list

评论

A

Written by

AI-Writer

Related Articles

Back to All Articles