单链表实现
中等 约 35 分钟
你将构建什么
一个 LinkedList 类,其节点持有值和 next 指针,支持 append、prepend、delete 和 toArray 操作。
学习目标
- 将节点建模为包含 value 和 next 引用的对象
- 通过跟随 next 指针遍历链表
- 在插入和删除节点时保持链条完整
- 比较链表与数组的取舍
前置要求
- 对象与属性访问
- 函数与返回值
- while 循环
步骤
- 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
实现 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
实现 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
实现 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
实现 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。
自己动手试试
起始代码
class Node { constructor(value) { this.value = value; this.next = null; } }
class LinkedList {
constructor() { this.head = null; this.size = 0; }
// TODO: append, prepend, delete, toArray
}解决方案代码
class Node { constructor(v) { this.value = v; this.next = null; } }
class LinkedList {
constructor() { this.head = null; this.size = 0; }
append(v) {
const n = new Node(v);
if (!this.head) this.head = n;
else { let c = this.head; while (c.next) c = c.next; c.next = n; }
this.size++; return this;
}
prepend(v) {
const n = new Node(v); n.next = this.head; this.head = n; this.size++; return this;
}
delete(v) {
if (!this.head) return false;
if (this.head.value === v) { this.head = this.head.next; this.size--; return true; }
let p = this.head, c = this.head.next;
while (c) { if (c.value === v) { p.next = c.next; this.size--; return true; } p = c; c = c.next; }
return false;
}
toArray() { const r = []; let c = this.head; while (c) { r.push(c.value); c = c.next; } return r; }
}你学到了什么
你构建了基于节点的数据结构并练习了指针操作——这是树、图以及其他数组难以表达的链式结构的基础。
相关资源
相关术语
新手友好的术语表用大白话解释编程术语——变量、函数、DOM、Promise 等等。
解读错误信息
用大白话解释常见错误——什么意思、为什么发生、如何修复。