我报名参加金石计划1期挑战——瓜分10万奖池，这是我的第 1 篇文章，点击查看活动详情
关键词: 线性结构 指针
ps：其实本质和小时候玩回形针没什么区别。
链表的定义
每个数据（节点）都有一个指针，指向下一个数据。
优点：将数据分散到内存各处，无须事先寻找连续的空格子。
缺点：只能顺序访问，从第一个开始找。
链表和数组是常用基础的数据结构，最好对比记忆。
| 概念 | 读取 | 查找 | 插入 | 删除 | |
| 链表 | 通过指针将一组零散的内存块串联使用 | O(n) 只能顺序访问 | O(n) | O(1) | O(1) |
| 数组 | 连续的内存空间来存储 | O(1) 可以通过下标直接访问 | O(n) | O(n) 末尾添加是O(1) | O(n) 末尾删除是O(1) |
各个操作及其复杂度
添加 O(1)
删除 O(1)
只需要把Green指针指向的位置从Yellow变成Red，删除就完成了。
动手实现一个链表
- 链表是由节点(node)组成的，
node包含两个属性：next表示指向下一结点的指针（后继指针）data表示结点所保存的数据。
/** * 节点类 LinkNode 有两个属性 * node 表示结点所保存的数据 * next 表示指向下一结点的指针 */ class LinkNode { constructor(data) { this.data = data; this.next = null } } /** * LinkList 的作用就是一个指针，它指向链表的第一个结点，让程序知道链表的起始位置 * 有两个属性 * head 链表的开端 * length 链表长度 */ class LinkList { constructor() { this.head = null
this.length = 0; }}- 添加。 判断
this.head是否存在。不存在就直接赋值。存在则需要往后遍历，直到不存在的时候赋值。
LinkList.prototype.add = function (data) { const node = new LinkNode(data); if (this.head) { let cur = this.head; while (cur.next) { cur = cur.next; } cur.next = node } else { this.head = node } this.length += 1; return this.length }
为了验证方法是否正确，我们给 LinkList 增加打印整个链表的方法。
LinkList.prototype.print = function () { let cur = this.head; let cache = []; while (cur) { cache.push(cur.data) cur = cur.next; } console.log(cache.join("->")) } let list = new LinkList(); list.add("hello"); list.add("world"); list.print() // hello->world
- 查找。 两种查找方法：通过链表中索引；通过链表中的值。
LinkList.prototype.find = function (index) { let i = 0; let cur = this.head; while (cur && i < index) { cur = cur.next; i++ } return cur } LinkList.prototype.indexOf = function (value) { let cur = this.head; let i = 0; while(cur) { if(cur.data === value) { return i } cur = cur.next; i++ } return null } console.log(list.find(2)) // LinkNode { data: 'thank', ...} console.log(list.indexOf('you')) // 3
- 插入。链表的插入要分三种情况：头部插入；中部插入；尾部插入。
如果是头部插入，新增的节点 node 后继指针是 this.head，this.head 重新赋值。
如果是尾部插入，直接调用之前写得 add 方法就行。
如果是中部插入，需要知道 index 之前的节点 prev，使 prev 的后继指针指向新节点。
LinkList.prototype.insert = function (index, data) { const node = new LinkNode(data); if (index === 0) { // 开头插入 // node.next = this.head; // this.head = node; // 通过解构赋值 [this.head, node.next] = [node, this.head]; this.length += 1; return this.length } else if (this.length > index) {// 中间插入 // 先找出新结点插入位置前的那一结点 const prev = this.find(index - 1); // 使前一结点的链指向新结点 // node.next = prev.next; // prev.next = node; // 通过解构赋值 [prev.next, node.next] = [node, prev.next] this.length += 1; return this.length } else { // 末端插入 return this.add(data) } } let list = new LinkList(); list.add("hello"); list.add("world"); list.insert(0, "a"); // a->hello->world // list.insert(1, "b"); // hello->b->world // list.insert(2, "c"); // hello->world->c list.print()
- 删除。操作和插入是类似的。
LinkList.prototype.removeAt = function (index) { let cur = this.head; if (index === 0) { this.head = cur.next; } else { const prev = this.find(index - 1); const cur = prev.next; // prev.next = cur.next; // cur.next = null; // 解构赋值 [prev.next, cur.next] = [cur.next, null] } this.length -= 1; return cur } let list = new LinkList(); list.add("hello"); list.add("world"); list.removeAt(1) list.print() // hello
拓展
循环链表
循环链表跟单链表的区别就在于尾结点。单链表的尾结点为 null，循环链表尾结点的后继指针是指向链表的某个节点。
双向链表
双向链表和单向链表的区别就在于：除了后继指针，双向链表的节点上还有指向前一个节点的前继指针。
leetcode 相关问题
- 203 移除链表元素
- 206 反转链表
- 141 环形链表
- 24 两两交换列表中的节点
- 21 合并两个有序链表
- 23 合并 K 个有序链表
