Skip to content

链表

一句话解释

链表是一种线性数据结构,每个元素(节点)指向下一个,而非使用连续内存。

用大白话说

链表将数据存放在节点中,每个节点含一个值和一个指向下一节点的引用(指针)。与数组不同,元素并不存放在连续内存中——它们靠指针串联。遍历链表时从 head 出发,沿 next 指针一路走到末尾(null)。链表擅长在头部插入和删除(O(1)),因为只需调整指针,无需搬移元素。但按下标随机访问是 O(n),必须从头遍历。数组恰好相反:访问 O(1),头部插入 O(n)。变体包括双向链表(每个节点还指向前一个)和循环链表(末节点指回头节点)。链表是栈、队列及许多更高级结构的基础。

示例

javascript
class Node {
  constructor(value) { this.value = value; this.next = null; }
}

class LinkedList {
  constructor() { this.head = null; }
  prepend(value) {
    const node = new Node(value);
    node.next = this.head;
    this.head = node;
  }
  toArray() {
    const arr = []; let cur = this.head;
    while (cur) { arr.push(cur.value); cur = cur.next; }
    return arr;
  }
}

const list = new LinkedList();
list.prepend("c"); list.prepend("b"); list.prepend("a");
console.log(list.toArray()); // ["a", "b", "c"]

每个 Node 持有一个值和一个 next 指针。prepend() 在 O(1) 内插入头部。toArray() 顺着链条遍历。

相关术语

相关资源

相关课程

解读错误信息

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

查看错误

← 返回术语表