链表
链表
链表是一种线性数据结构，其元素不存储在连续的内存位置，而是通过指针相互链接。每个元素（称为节点）包含数据和一个指向下一个节点的指针。
基本概念
节点结构
┌─────────────┐ ┌─────────────┐ ┌─────────────┐
│ data | next │───▶│ data | next │───▶│ data | null │
└─────────────┘ └─────────────┘ └─────────────┘
节点 1 节点 2 节点 3每个节点包含：
- 数据域（data）：存储实际数据
- 指针域（next）：指向下一个节点
链表与数组的对比
| 特性 | 数组 | 链表 |
|---|---|---|
| 内存布局 | 连续 | 分散 |
| 访问方式 | 随机访问 O(1) | 顺序访问 O(n) |
| 插入/删除 | O(n) | O(1) |
| 内存开销 | 低 | 高（需存储额外指针） |
| 缓存友好性 | 好 | 差 |
链表类型
单链表
- 单链表详解
- 每个节点只有一个指向下一节点的指针
- 只能从头到尾单向遍历
双链表
- 双链表详解
- 每个节点有两个指针：prev 和 next
- 可双向遍历
循环链表
- 最后一个节点指向第一个节点
- 形成环形结构
基本操作
创建节点
class ListNode {
constructor(data) {
this.data = data;
this.next = null;
}
}遍历链表
function traverse(head) {
let current = head;
while (current !== null) {
console.log(current.data);
current = current.next;
}
}查找元素
function search(head, target) {
let current = head;
let index = 0;
while (current !== null) {
if (current.data === target) {
return index;
}
current = current.next;
index++;
}
return -1; // 未找到
}时间复杂度分析
| 操作 | 时间复杂度 | 说明 |
|---|---|---|
| 访问 | O(n) | 需要从头遍历 |
| 查找 | O(n) | 需要遍历搜索 |
| 插入（头部） | O(1) | 直接修改头指针 |
| 插入（尾部） | O(n) | 需要找到尾节点 |
| 插入（已知位置） | O(1) | 直接修改指针 |
| 删除（头部） | O(1) | 直接修改头指针 |
| 删除（已知节点） | O(1) | 直接修改指针 |
| 删除（按值） | O(n) | 需要先查找 |
优缺点
优点
- 动态大小：可在运行时动态增长和缩减
- 高效的插入/删除：在已知位置的插入/删除为 O(1)
- 内存利用率高：按需分配内存
- 灵活性强：可实现复杂数据结构
缺点
- 额外内存开销：每个节点需要存储指针
- 不支持随机访问：无法直接访问第 i 个元素
- 缓存性能差：节点在内存中不连续
- 指针管理复杂：容易出现内存泄漏或悬空指针
应用场景
适合使用的情况
- 频繁插入/删除：尤其是在列表中间操作
- 大小未知：运行时数据量变化较大
- 实现其他结构：如栈、队列、图的邻接表
- 撤销操作：编辑器的撤销功能
不适合使用的情况
- 需要随机访问：频繁通过下标访问元素
- 内存敏感：对内存使用有严格要求
- 缓存敏感：需要高性能顺序访问
实际应用示例
1. 音乐播放列表
class Song {
constructor(title, artist) {
this.title = title;
this.artist = artist;
this.next = null;
}
}
class Playlist {
constructor() {
this.head = null;
this.current = null;
}
addSong(title, artist) {
const newSong = new Song(title, artist);
if (!this.head) {
this.head = newSong;
this.current = newSong;
} else {
let last = this.head;
while (last.next) {
last = last.next;
}
last.next = newSong;
}
}
nextSong() {
if (this.current && this.current.next) {
this.current = this.current.next;
return this.current;
}
return null;
}
}2. 浏览器历史记录
class HistoryEntry {
constructor(url, title) {
this.url = url;
this.title = title;
this.next = null;
}
}
class BrowserHistory {
constructor() {
this.head = null;
this.maxSize = 100;
this.size = 0;
}
visit(url, title) {
const entry = new HistoryEntry(url, title);
entry.next = this.head;
this.head = entry;
this.size++;
// 限制历史记录大小
if (this.size > this.maxSize) {
this.removeLast();
}
}
getHistory() {
const history = [];
let current = this.head;
while (current) {
history.push({
url: current.url,
title: current.title,
});
current = current.next;
}
return history;
}
}学习建议
- 从基础开始：先掌握单链表的基本操作
- 用图形辅助理解：用图示理解指针变化
- 注意边界情况：空链表、单节点、头尾节点的特殊处理
- 多练习指针操作：熟练掌握指针的增删改查
- 对比学习：与数组对比，理解各自的适用场景
下一步
建议按以下顺序学习：
掌握链表是理解更复杂数据结构（如树和图）的必要基础！
贡献者
这篇文章有帮助吗？
最近更新
Involution Hell© 2026 byCommunityunderCC BY-NC-SA 4.0
