Skip to content

单链表实现

中等 约 35 分钟

你将构建什么

一个 LinkedList 类,其节点持有值和 next 指针,支持 append、prepend、delete 和 toArray 操作。

学习目标

  • 将节点建模为包含 value 和 next 引用的对象
  • 通过跟随 next 指针遍历链表
  • 在插入和删除节点时保持链条完整
  • 比较链表与数组的取舍

前置要求

  • 对象与属性访问
  • 函数与返回值
  • while 循环

步骤

  1. 1

    定义节点与链表

    链表是由节点组成的链条。每个节点存储一个值和对下一个节点的引用。创建 Node 辅助类和以 head 指针(初始为 null)开头的 LinkedList 类。

    代码
    class Node {
      constructor(value) {
        this.value = value;
        this.next = null;
      }
    }
    
    class LinkedList {
      constructor() {
        this.head = null;
        this.size = 0;
      }
    }

    预期结果

    一个空 LinkedList,head === null 且 size === 0。

  2. 2

    实现 append

    在尾部追加需要从 head 走到最后一个节点(next === null),然后挂上新节点。若链表为空,新节点直接成为 head。

    代码
    append(value) {
      const node = new Node(value);
      if (!this.head) {
        this.head = node;
      } else {
        let current = this.head;
        while (current.next) current = current.next;
        current.next = node;
      }
      this.size++;
      return this;
    }

    预期结果

    list.append(1).append(2).append(3) 构建出链条 1 → 2 → 3。

  3. 3

    实现 prepend

    在头部前插需要把新节点的 next 指向当前 head,再把新节点设为 head。这是 O(1) 操作,比 append 更快。

    代码
    prepend(value) {
      const node = new Node(value);
      node.next = this.head;
      this.head = node;
      this.size++;
      return this;
    }

    预期结果

    list.prepend(0) 使 0 成为新 head,其余节点右移。

  4. 4

    实现 delete

    删除某个值需要遍历链表并保留前驱节点引用。当当前节点匹配时,通过将 prev.next 指向 current.next 来解除其链接。head 的情况需单独处理。

    代码
    delete(value) {
      if (!this.head) return false;
      if (this.head.value === value) {
        this.head = this.head.next;
        this.size--;
        return true;
      }
      let prev = this.head;
      let current = this.head.next;
      while (current) {
        if (current.value === value) {
          prev.next = current.next;
          this.size--;
          return true;
        }
        prev = current;
        current = current.next;
      }
      return false;
    }

    预期结果

    delete(2) 后,链条跳过值为 2 的节点。

  5. 5

    实现 toArray 并测试

    添加 toArray 方法,遍历链表将值收集到数组中,然后运行完整的端到端测试。

    代码
    toArray() {
      const result = [];
      let current = this.head;
      while (current) {
        result.push(current.value);
        current = current.next;
      }
      return result;
    }
    
    // Test
    const list = new LinkedList();
    list.append(1).append(2).append(3);
    list.prepend(0);
    console.log(list.toArray()); // [0, 1, 2, 3]
    list.delete(2);
    console.log(list.toArray()); // [0, 1, 3]
    console.log('Size:', list.size); // 3

    预期结果

    输出依次为 [0,1,2,3]、[0,1,3]、Size: 3。

自己动手试试

你学到了什么

你构建了基于节点的数据结构并练习了指针操作——这是树、图以及其他数组难以表达的链式结构的基础。

相关资源

相关课程

  • 对象

    每个节点都是包含 value 和 next 引用的对象。

  • 循环

    遍历使用 while 循环跟随 next 指针。

相关术语

  • 链表

    由引用连接的节点链条。

  • 指针

    对另一个节点或对象的引用。

相关术语

新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。

  • 链表

    由引用连接的节点链条。

  • 指针

    对另一个节点或对象的引用。

解读错误信息

用大白话解释常见错误——什么意思、为什么发生、如何修复。

查看错误

← 返回主题