链表

Nash

• 8 min read

链表的本质是一种 动态数据结构，由一系列通过指针（或引用）连接的节点组成。每个节点包含两个部分：

  1. 数据域（Data）：存储数据元素的实际内容。
  2. 指针域（Pointer / Link）：存储指向下一个节点的引用或指针。在双向链表中，还会包含指向前一个节点的指针。

链表与数组不同，它不要求数据元素在内存中是连续存储的，而是通过指针将数据元素按顺序连接起来。链表的节点在内存中是散布的，每个节点都知道自己与下一个节点的连接关系，因此支持灵活的插入和删除操作。

链表的本质特征：

动态内存分配：链表的大小不固定，节点可以动态地添加或删除。这意味着链表能够更高效地利用内存，尤其是在需要频繁修改数据时，不需要重新分配和复制数据（如数组那样）。

节点连接性：每个节点除了存储数据，还持有一个指向下一个节点的引用或指针（单向链表），或者是指向前后节点的引用（双向链表）。这种指针的连接让链表能够按照线性顺序进行遍历。

灵活性：插入、删除节点操作非常高效，尤其是在链表头部或中间位置，因为不需要像数组那样移动大量元素，只需要调整指针的指向即可。

顺序访问：链表的节点是线性排列的，但它不支持随机访问。为了访问某个元素，需要从头节点开始按顺序遍历整个链表，直到找到目标节点。这也是链表的一大限制，它的时间复杂度是 O(n)。

主要优缺点：

  • 优点：
  • 灵活的内存管理：链表动态分配内存，避免了数组大小固定的问题。
  • 高效的插入和删除：尤其是在链表的头部和中间插入、删除操作具有常数时间复杂度 O(1)。
  • 缺点：
  • 不支持高效的随机访问：访问链表中的某个元素需要遍历整个链表，时间复杂度是 O(n)。
  • 每个节点需要额外的内存来存储指针，因此空间开销相对较大。

链表的分类：

单向链表（Singly Linked List）：每个节点只包含一个指向下一个节点的指针，链表只能单向遍历。

双向链表（Doubly Linked List）：每个节点包含两个指针，一个指向下一个节点，一个指向前一个节点，支持双向遍历。

循环链表（Circular Linked List）：链表的尾节点指向头节点，形成一个循环结构。可以是单向循环链表或双向循环链表。

class Node {
  constructor(value) {
    this.value = value;  // 节点的值
    this.next = null;    // 指向下一个节点的指针
  }
}

class LinkedList {
  constructor() {
    this.head = null;  // 链表的头部
    this.size = 0;     // 链表的大小
  }

  // 插入新节点到链表尾部
  append(value) {
    const newNode = new Node(value);
    if (!this.head) {
      this.head = newNode;
    } else {
      let current = this.head;
      while (current.next) {
        current = current.next;
      }
      current.next = newNode;
    }
    this.size++;
  }

  // 遍历链表
  printList() {
    let current = this.head;
    let result = '';
    while (current) {
      result += current.value + ' -> ';
      current = current.next;
    }
    console.log(result.slice(0, -4)); // 去掉最后的箭头
  }
}

// 测试链表
const list = new LinkedList();
list.append(10);
list.append(20);
list.append(30);
list.printList();  // 输出: 10 -> 20 -> 30

链表在前端中的使用场景并不像在传统的数据结构中那样常见，但在一些特定的应用场景下，链表能够发挥其高效的插入和删除操作优势。

1. 虚拟滚动（Virtual Scrolling）

虚拟滚动技术用于优化长列表（如动态加载的内容或大数据列表）的渲染性能。链表可以帮助高效地管理可视区域中的数据，避免一次性渲染大量DOM节点，从而提高性能。

示例：

当你实现一个虚拟滚动列表时，通常会根据用户滚动的位置动态加载和卸载列表项。在这种情况下，链表可以用来管理这些动态添加和删除的列表项，而不是每次都重新渲染整个列表。链表的优点是可以快速插入和删除节点，特别是在处理较大的列表时，能显著提高渲染效率。

class Node {
  constructor(value) {
    this.value = value;
    this.next = null;
    this.prev = null; // 如果是双向链表
  }
}

class VirtualList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  append(value) {
    const newNode = new Node(value);
    if (!this.tail) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
      this.tail = newNode;
    }
    this.size++;
  }

  // 删除链表中的某个节点
  remove(value) {
    let current = this.head;
    while (current) {
      if (current.value === value) {
        if (current.prev) current.prev.next = current.next;
        if (current.next) current.next.prev = current.prev;
        if (current === this.head) this.head = current.next;
        if (current === this.tail) this.tail = current.prev;
        this.size--;
        return;
      }
      current = current.next;
    }
  }
  
  // 打印列表数据
  printList() {
    let current = this.head;
    while (current) {
      console.log(current.value);
      current = current.next;
    }
  }
}

// 使用示例
const virtualList = new VirtualList();
virtualList.append('item1');
virtualList.append('item2');
virtualList.append('item3');
virtualList.remove('item2');
virtualList.printList();  // 输出: item1, item3

2. 撤销/重做（Undo/Redo）功能

在许多前端应用中，比如文本编辑器、绘图应用等，撤销（Undo）和重做（Redo）功能是常见需求。链表可以用于管理每次操作的历史记录，允许你高效地进行撤销和重做。

示例：

在撤销和重做的场景中，每次操作都会产生一个新的节点，节点保存操作的状态。链表的灵活性使得插入和删除操作变得高效，而不需要重新生成整个历史记录。

class ActionNode {
  constructor(action, prev = null) {
    this.action = action;
    this.prev = prev;
  }
}

class UndoRedoManager {
  constructor() {
    this.head = null;
    this.tail = null;
    this.current = null; // 当前操作指针
  }

  // 执行一个新操作
  execute(action) {
    const newNode = new ActionNode(action, this.current);
    if (this.tail === this.current) {
      this.tail = newNode;
    }
    this.current = newNode;
    if (!this.head) {
      this.head = newNode;
    }
  }

  // 撤销操作
  undo() {
    if (this.current && this.current.prev) {
      this.current = this.current.prev;
      return this.current.action;
    }
    return null; // 无法撤销
  }

  // 重做操作
  redo() {
    if (this.current && this.current.next) {
      this.current = this.current.next;
      return this.current.action;
    }
    return null; // 无法重做
  }
}

// 使用示例
const manager = new UndoRedoManager();
manager.execute('Action 1');
manager.execute('Action 2');
console.log(manager.undo()); // 输出: Action 1
console.log(manager.redo()); // 输出: Action 2

3. 动画队列

链表可以用于实现动画队列，特别是在需要对动画元素进行动态添加、删除、暂停、恢复时。链表的插入和删除操作可以帮助你快速更新动画队列，而不需要重绘整个动画。

示例：

假设有多个动画对象，你需要动态管理这些动画的启动顺序、暂停或删除等。链表可以让你快速实现这些操作。

class AnimationNode {
  constructor(animation) {
    this.animation = animation;  // 动画对象
    this.next = null;
  }
}

class AnimationQueue {
  constructor() {
    this.head = null;
    this.tail = null;
  }

  addAnimation(animation) {
    const newNode = new AnimationNode(animation);
    if (!this.head) {
      this.head = this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
  }

  startAllAnimations() {
    let current = this.head;
    while (current) {
      current.animation.start();
      current = current.next;
    }
  }

  removeAnimation(animation) {
    let current = this.head;
    let prev = null;
    while (current) {
      if (current.animation === animation) {
        if (prev) {
          prev.next = current.next;
        } else {
          this.head = current.next;
        }
        if (!current.next) this.tail = prev;
        break;
      }
      prev = current;
      current = current.next;
    }
  }
}

// 使用示例
const animationQueue = new AnimationQueue();
const anim1 = { start: () => console.log('Anim1 started') };
const anim2 = { start: () => console.log('Anim2 started') };

animationQueue.addAnimation(anim1);
animationQueue.addAnimation(anim2);
animationQueue.startAllAnimations();  // 输出: Anim1 started, Anim2 started
animationQueue.removeAnimation(anim1);

4. 链式调用（Chaining）

链表的设计非常适合实现链式调用模式，在这种模式中，函数调用可以通过返回当前对象本身来实现连锁反应。虽然链式调用通常是通过对象和方法链实现的，但其内部实现往往类似于链表结构。

示例：

链式调用常见于流式API中，例如jQuery等库就利用链表的思想来实现方法的链式调用。

class Chainable {
  constructor(value = 0) {
    this.value = value;
  }

  add(num) {
    this.value += num;
    return this;  // 返回当前对象，实现链式调用
  }

  subtract(num) {
    this.value -= num;
    return this;  // 返回当前对象，实现链式调用
  }

  getResult() {
    return this.value;
  }
}

// 使用示例
const result = new Chainable(10)
  .add(5)
  .subtract(3)
  .getResult();
console.log(result);  // 输出: 12

总结来说，链表在前端中的使用场景并不广泛，但在某些特定的需求下，它能够提供高效的操作，尤其是在需要频繁动态修改数据结构（如插入、删除、撤销、重做、队列管理等）时。链表的优势主要体现在其灵活性和高效的内存管理上，尤其适合那些不要求数据元素按顺序存储且需要频繁修改数据结构的场景。

形象化理解：

你可以将链表看作是一个火车，每一节车厢都包含一些货物（数据），而每节车厢的前面或后面（取决于链表类型）都有一个指向下一节车厢的指针。你无法直接跳到某一节车厢，而是需要从第一节车厢开始，按顺序查看每一节车厢。

总结来说，链表的本质是一个由节点通过指针链接起来的线性结构，其核心优势在于能够高效地进行插入和删除操作，缺点是访问速度较慢，且内存开销较大。

苏ICP备2025153828号