链表是一种通过节点存储数据的非连续内存结构，每个节点包含数据域和指针域，通过指针连接实现高效插入删除。单向链表由头节点开始，next指向下一节点，末节点指向null；基本操作包括头部/尾部插入、删除指定值节点、查找与遍历。双向链表增加prev指针，支持前后双向遍历，提升操作灵活性。相比数组，链表适合频繁修改场景，但访问需从头遍历，时间复杂度O(n)。常用于实现栈队列、浏览器历史、播放列表等动态集合。
链表是一种常见的数据结构，它通过节点（node）来存储数据，每个节点包含数据和指向下一个节点的指针。与数组不同，链表在内存中不是连续存储的，而是通过指针连接各个节点。这使得插入和删除操作更高效，尤其在频繁修改数据时。
链表的基本结构
一个最简单的链表节点通常包含两个部分：数据域和指针域。
class ListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}
链表本身由一个头节点（head）开始，通过 next 指针依次连接后续节点，直到最后一个节点的 next 为 null，表示链表结束。
基本操作包括：
立即学习“Java免费学习笔记（深入）”；
- 插入节点：可以在头部、尾部或指定位置插入新节点
- 删除节点：根据值或位置找到并移除节点
- 查找节点：遍历链表寻找特定值
- 遍历链表：从头到尾访问每个节点
实现单向链表
下面是一个简单的单向链表实现：
class LinkedList {
constructor() {
this.head = null;
this.size = 0;
}
append(data) {
const newNode = new ListNode(data);
if (!this.head) {
this.head = newNode;
} else {
let current = this.head;
while (current.next) {
current = current.next;
}
current.next = newNode;
}
this.size++;
}
prepend(data) {
const newNode = new ListNode(data);
newNode.next = this.head;
this.head = newNode;
this.size++;
}
remove(data) {
if (!this.head) return;
if (this.head.data === data) {
this.head = this.head.next;
this.size--;
return;
}
let current = this.head;
while (current.next && current.next.data !== data) {
current = current.next;
}
if (current.next) {
current.next = current.next.next;
this.size--;
}
}
display() {
const result = [];
let current = this.head;
while (current) {
result.push(current.data);
current = current.next;
}
return result;
}
}
使用示例：
const list = new LinkedList(); list.append(10); list.append(20); list.prepend(5); console.log(list.display()); // [5, 10, 20] list.remove(10); console.log(list.display()); // [5, 20]
双向链表的特点与实现
双向链表在单向链表的基础上增加了前驱指针（prev），每个节点既能指向下一个节点，也能指向前一个节点。这种结构支持从任意方向遍历，提高了某些操作的效率。
节点定义如下：
class DoublyListNode {
constructor(data) {
this.data = data;
this.next = null;
this.prev = null;
}
}
双向链表的插入和删除操作需要同时维护 next 和 prev 指针。
class DoublyLinkedList {
constructor() {
this.head = null;
this.tail = null;
this.size = 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.size++;
}
remove(data) {
let current = this.head;
while (current && current.data !== data) {
current = current.next;
}
if (!current) return;
if (current.prev) {
current.prev.next = current.next;
} else {
this.head = current.next;
}
if (current.next) {
current.next.prev = current.prev;
} else {
this.tail = current.prev;
}
this.size--;
}
display() {
const result = [];
let current = this.head;
while (current) {
result.push(current.data);
current = current.next;
}
return result;
}
displayReverse() {
const result = [];
let current = this.tail;
while (current) {
result.push(current.data);
current = current.prev;
}
return result;
}
}
优势体现在可以从尾部快速插入/删除，也可以反向遍历。
链表 vs 数组
链表适合频繁插入和删除的场景，因为不需要移动大量元素。但访问某个位置的元素时，必须从头开始遍历，时间复杂度为 O(n)，而数组可以通过索引直接访问。
常见应用场景：
基本上就这些。链表理解起来不难，关键在于指针操作的细节处理，尤其是边界情况，比如头尾节点的更新。双向链表虽然逻辑稍复杂，但提供了更大的灵活性。实际开发中，虽然 JavaScript 内置了数组，但在特定算法题或自定义数据结构中，链表仍然非常有用。
