Siykt的博客Linked List
Contents
链表
在计算机科学中, 一个 链表 是数据元素的线性集合
在最简单的形式下, 每个节点由数据两个部分组成, 一个是用于存储数据的 <元素域/值域>, 一个是用于存储指针信息的 <链接域/指针域>
其元素的线性顺序是由每个元素的链接域中指针信息所组成:
链表集合: { {元素域, 链接域}, {元素域, 链接域}, {元素域, 链接域} }
在使用内存空间的表现上, 因为其节点存在指针信息的链接域, 所以链表不需要连续的内存地址:
| 访问地址 | 元素域 | 链接域 |
|---|---|---|
| 100 | 0 | 130 |
| 130 | 1 | 180 |
| 180 | 2 | - |
由于每个元素必须存储指向前后元素位置的指针, 会消耗相对更多的储存空间
因为链表的存储空间不连续, 你无法根据一个索引算出对应元素的地址, 所以不能随机访问
链表节点的实现参考:
export interface LinkedListNode<Data = any> {
// -- 元素域 --
/** 保存的数据 */
elem: Data;
// -- 链接域 --
/** 指向下一个元素 */
next?: LinkedListNode<Data>;
/** 指向上一个元素 */
pre?: LinkedListNode<Data>;
}
export class LinkedListNode<Data = any> {
constructor(public elem: Data, public next?: LinkedListNode<Data>, public pre?: LinkedListNode<Data>) {}
}
链表的细分种类
链表有很多种不同的类型: 单向链表, 双向链表以及循环链表
单向链表
链表中最简单的一种是单向链表 (又名单链表、线性链表) , 其特点是链表的链接方向是单向的而最后一个节点则指向一个空值. 对链表的访问要通过从头部开始, 依序往下读取
实现参考:
export class SingleLinkedList<Data = any> {
head?: LinkedListNode<Data>;
tail?: LinkedListNode<Data>;
constructor(...elements: Data[]) {
if (elements) {
// 初始化时调用 shift 或 push 都可以实现
elements.forEach(e => this.append(e));
}
}
/** 获取链表的长度, 此属性将会迭代链表请谨慎使用 */
get length() {
let cur = this.head;
let count = 0;
// 根据节点是否存在判断链表的长度
while (cur) {
count += 1;
cur = cur.next;
}
return count;
}
/**
* 判断链表是否为空
*/
isEmpty() {
return !this.head;
}
/**
* 添加元素至链表的头部 {1} -> [{1}, {0}]
* @param elem 元素
*/
add(elem: Data) {
const node = new LinkedListNode(elem);
node.next = this.head;
this.head = node;
if (!this.tail) {
this.tail = node;
}
return this;
}
/**
* 添加元素至链表的尾部 {1} -> [{0}, {1}]
* @param elem 元素
*/
append(elem: Data) {
const node = new LinkedListNode(elem);
// 如果链表为空, 添加至头部
if (this.isEmpty()) {
this.head = node;
this.tail = node;
} else {
if (this.tail) {
this.tail.next = node;
}
this.tail = node;
}
return this;
}
/**
* 添加元素至链表的指定位置 {2},1 -> [{0}, {2}, {1}]
* @param elem 元素
* @param pos 元素坐标
*/
inset(elem: Data, pos = 0) {
// 若指定位置为第一个元素之前, 则执行头部插入
if (pos <= 0) {
this.add(elem);
} else if (pos > this.length) {
// 若指定位置为第一个元素之前, 则执行尾部插入
this.append(elem);
} else {
const node = new LinkedListNode(elem);
const pre = this.search(pos - 1);
node.next = pre.next;
pre.next = node;
}
return this;
}
/**
* 根据位置查询元素
* @param pos 元素坐标
*/
search(pos: number) {
let result: LinkedListNode<Data> | undefined;
// 如果输入的数小于等于 0, 返回 head
if (pos <= 0) {
result = this.head;
} else {
result = this.head;
// 遍历节点获取位置
while (pos--) result = result?.next;
}
// 抛出索引超出错误
if (!result) {
throw new Error(`[SingleLinkedList] 链表索引超出: ${pos}`);
}
return result;
}
/**
* 根据位置删除元素
* @param pos 坐标
*/
remove(pos: number) {
// 获取要删除的节点的上一个节点以便更新节点坐标
const pre = this.search(pos - 1);
const node = pre.next;
if (node) {
// 当要删除的节点为尾节点时更新尾节点
if (node === this.tail) {
this.tail = pre;
}
// 将上一个节点的next索引更新为删除节点的next索引
pre.next = node.next;
return true;
}
return false;
}
/**
* 遍历链表
* @param callbackfn 回调函数
*/
map<Result>(callbackfn: LinkedListTraversalCallback<Data, Result>): Result[] {
let cur = this.head;
let index = 0;
const result: Result[] = [];
while (cur) {
result.push(callbackfn(cur.elem, index++, cur));
cur = cur.next;
}
return result;
}
}
双向链表
双向链表与单向链表的差异就在于其链接域保存的指针有两个, 一个指向上一个节点(前驱), 一个指向下一个节点(后继), 所以, 从双向链表中的任意一个结点开始, 都可以很方便地访问它的前驱结点和后继结点
实现参考:
export class DoubleLinkedList<Data = any> {
head?: LinkedListNode<Data>;
tail?: LinkedListNode<Data>;
constructor(...elements: Data[]) {
if (elements) {
// 初始化时调用 shift 或 push 都可以实现
elements.forEach(e => this.append(e));
}
}
/** 获取链表的长度, 此属性将会迭代链表请谨慎使用 */
get length() {
let cur = this.head;
let count = 0;
// 根据节点是否存在判断链表的长度
while (cur) {
count += 1;
cur = cur.next;
}
return count;
}
/**
* 判断链表是否为空
*/
isEmpty() {
return !this.head;
}
/**
* 添加元素至链表的头部 {1} -> [{1}, {0}]
* @param elem 元素
*/
add(elem: Data) {
const node = new LinkedListNode(elem);
// 设置新节点的后继为原head节点
node.next = this.head;
if (this.head) {
// 设置原head节点的前驱为新节点
this.head.pre = node;
}
// 更新head节点
this.head = node;
// 如果尾节点不存在则设置尾部节点
if (!this.tail) {
this.tail = node;
}
return this;
}
/**
* 添加元素至链表的尾部 {1} -> [{0}, {1}]
* @param elem 元素
*/
append(elem: Data) {
const node = new LinkedListNode(elem);
// 如果链表为空, 添加至头部
if (this.isEmpty()) {
this.head = node;
this.tail = node;
} else {
if (this.tail) {
// 设置原tail节点的后继为新节点
this.tail.next = node;
// 设置新节点的前驱为原tail节点
node.pre = this.tail;
}
// 更新tail节点
this.tail = node;
}
return this;
}
/**
* 添加元素至链表的指定位置 {2},1 -> [{0}, {2}, {1}]
* @param elem 元素
* @param pos 元素坐标
*/
inset(elem: Data, pos = 0) {
// 若指定位置为第一个元素之前, 则执行头部插入
if (pos <= 0) {
this.add(elem);
} else if (pos > this.length) {
// 若指定位置为第一个元素之前, 则执行尾部插入
this.append(elem);
} else {
const newNode = new LinkedListNode(elem);
const oldNode = this.search(pos);
// 查找到它的前一个节点进行操作
const { pre } = oldNode;
if (pre) {
// 更新前一个节点的后继为新节点
pre.next = newNode;
// 更新新节点的前驱为前一个节点
newNode.pre = pre;
}
newNode.next = oldNode;
oldNode.pre = newNode;
}
return this;
}
/**
* 从右侧(尾部)添加元素至链表的指定位置 {2},0 -> [{0}, {1}, {2}]
* @param elem 元素
* @param pos 元素坐标
*/
insetRight(elem: Data, pos = 0) {
// 若指定位置为第一个元素之前, 则执行尾部插入
if (pos <= 0) {
this.append(elem);
} else if (pos > this.length) {
// 若指定位置为最后一个元素之后, 则执行头部插入
this.add(elem);
} else {
const newNode = new LinkedListNode(elem);
const oldNode = this.searchRight(pos);
// 查找到它的前一个节点进行操作
const { pre } = oldNode;
if (pre) {
// 更新前一个节点的后继为新节点
pre.next = newNode;
// 更新新节点的前驱为前一个节点
newNode.pre = pre;
}
newNode.next = oldNode;
oldNode.pre = newNode;
}
return this;
}
/**
* 根据位置查询元素
* @param pos 元素坐标
*/
search(pos: number) {
let result: LinkedListNode<Data> | undefined;
// 如果输入的数小于等于 0, 返回 head
if (pos <= 0) {
result = this.head;
} else {
result = this.head;
// 遍历节点获取位置
while (pos--) result = result?.next;
}
// 抛出索引超出错误
if (!result) {
throw new Error(`[DoubleLinkedList] 链表索引超出: ${pos}`);
}
return result;
}
/**
* 根据位置从右侧(尾部)查询元素
* @param pos 元素坐标
*/
searchRight(pos: number) {
let result: LinkedListNode<Data> | undefined;
// 如果输入的数小于等于 0, 返回 tail
if (pos <= 0) {
result = this.tail;
} else {
result = this.tail;
// 遍历节点获取位置
while (pos--) result = result?.pre;
}
// 抛出索引超出错误
if (!result) {
throw new Error(`[DoubleLinkedList] 链表索引超出: ${pos}`);
}
return result;
}
/**
* 根据位置删除元素
* @param pos 坐标
*/
remove(pos: number) {
// 获取要删除的节点的上一个节点以便更新节点坐标
const pre = this.search(pos - 1);
const node = pre.next;
if (node) {
// 当要删除的节点为尾节点时更新尾节点
if (node === this.tail) {
this.tail = pre;
}
// 将上一个节点的next索引更新为删除节点的next索引
pre.next = node.next;
return true;
}
return false;
}
/**
* 根据位置从右侧(尾部)删除元素
* @param pos 坐标
*/
removeRight(pos: number) {
// 获取要删除的节点的上一个节点以便更新节点坐标
const pre = this.search(pos - 1);
const node = pre.next;
if (node) {
// 当要删除的节点为尾节点时更新尾节点
if (node === this.tail) {
this.tail = pre;
}
// 将上一个节点的next索引更新为删除节点的next索引
pre.next = node.next;
return true;
}
return false;
}
/**
* 遍历链表
* @param callbackfn 回调函数
*/
map<Result>(callbackfn: LinkedListTraversalCallback<Data, Result>): Result[] {
let cur = this.head;
let index = 0;
const result: Result[] = [];
while (cur) {
result.push(callbackfn(cur.elem, index++, cur));
cur = cur.next;
}
return result;
}
/**
* 从右侧(尾部)遍历链表
* @param callbackfn 回调函数
*/
mapRight<Result>(callbackfn: LinkedListTraversalCallback<Data, Result>): Result[] {
let cur = this.tail;
let index = 0;
const result: Result[] = [];
while (cur) {
result.push(callbackfn(cur.elem, index++, cur));
cur = cur.pre;
}
return result;
}
/**
* 双向迭代
* @param callbackfn 回调函数, 返回false停止循环
*/
travelBidirectional(
callbackfn: (startNode: LinkedListNode<Data>, endNode: LinkedListNode<Data> | undefined, count: number) => any
) {
let start = this.head;
let end = this.tail;
let count = 0;
while (start !== end && start && end) {
if (callbackfn(start, end, count++) === false) {
return;
}
start = start?.next;
end = end?.pre;
}
if (start && start.next === end) {
callbackfn(start, undefined, count);
} else if (end && end.pre === start) {
callbackfn(end, undefined, count);
}
}
}
s;
实例
没有实例的数据结构都是空洞且乏味的
链表使用在对于不需要搜索但在变动频繁且无法预知数量上限的数据, 比如内存池、进程管理等场景.
合并有序链表
将两个升序链表合并为一个新的 升序 链表并返回, 新链表是通过拼接给定的两个链表的所有节点组成的
详细参见: 21. 合并两个有序链表 - 力扣（LeetCode）
算法实现:
export function mergeTwoSortedLists(
list1?: LinkedListNode<number>,
list2?: LinkedListNode<number>
): LinkedListNode<number> | undefined {
// 创建虚拟节点保存head指针
const dummy = new LinkedListNode(-1);
let cur = dummy;
while (list1 && list2) {
// 循环比较 list1 与 list2 的大小
// 并将小的一方挂载至cur.next上以保证“升序”的返回结果
// ? 如果需要降序结果只需调整判断的逻辑为小于
if (list1.elem > list2.elem) {
cur.next = list2;
list2 = list2.next;
} else {
cur.next = list1;
list1 = list1.next;
}
// 更新当前节点(cur)为后继节点
cur = cur.next;
}
// 到此只存在单个有效的链了, 直接将其挂载至当前节点的后继
cur.next = list1 || list2;
// 返回虚拟head节点中保存的实际head节点
return dummy.next;
}
有序链表的去重算法
给定一个已排序的链表的头 head, 删除所有重复的元素使每个元素只出现一次, 返回已排序的链表
详细参见: 83. 删除排序链表中的重复元素 - 力扣（LeetCode）
算法实现:
方法一
export function deleteDuplicates(head?: LinkedListNode<number>): LinkedListNode<number> | undefined {
if (!head) {
return head;
}
// 创建一个移动的指针用于更新链表
let cur = head;
// TODO 当值域相等时抛弃该节点, 否则更新当前节点为后继节点
while (cur.next) {
if (cur.elem === cur.next.elem) {
// 抛弃节点 cur.next
cur.next = cur.next.next;
} else {
// 更新当前节点为后继节点
cur = cur.next;
}
}
return head;
}
方法二
export function deleteDuplicates2(head?: LinkedListNode<number>): LinkedListNode<number> | undefined {
if (!head) {
return head;
}
// 创建虚拟节点保存head指针
const dummy = new LinkedListNode(Number.MIN_VALUE);
let cur = dummy;
// TODO 当值域不相等时添加该节点并更新节点指针为后继节点, 否则更新当前节点为后继节点
while (head) {
if (cur.elem !== head.elem) {
// 添加该节点并更新节点指针为后继节点
cur.next = head;
cur = cur.next;
}
// 更新当前节点为后继节点
head = head.next;
}
// 移除多余节点
cur.next = undefined;
return dummy.next;
}
方法三
export function deleteDuplicates3(head?: LinkedListNode<number>): LinkedListNode<number> | undefined {
if (!head || !head.next) {
return head;
}
// TODO 递归更新后继节点, 当值域相等时抛弃该节点
head.next = deleteDuplicates3(head.next);
if (head.elem === head.next?.elem) {
// 抛弃节点
head = head.next;
}
return head;
}
两个链表的两数相加
合并两个链表将其值域相加并返回为一个新的链表
详细参见: 2. 两数相加 - 力扣（LeetCode）)
算法实现:
export function addTwoNumbers(l1?: LinkedListNode<number>, l2?: LinkedListNode<number>): LinkedListNode<number> | undefined {
// 创建虚拟节点保存head指针
const dummy = new LinkedListNode(-1);
let cur = dummy;
let nextNum = 0;
// 循环相加两个链表的值, 并用 0 补位
while (l1 || l2) {
// 如果链表不相同时, 使用 0 补位 (任意一个实数 + 0等于其本身)
const v1 = l1 ? l1.elem : 0;
const v2 = l2 ? l2.elem : 0;
// 两数相加并且添加可能存在的进位
const addNum = v1 + v2 + nextNum;
cur.next = new LinkedListNode(addNum % 10);
// 计算进位
nextNum = addNum >= 10 ? 1 : 0;
// 更新节点
l1 = l1?.next;
l2 = l2?.next;
cur = cur.next;
}
if (nextNum) {
cur.next = new LinkedListNode(nextNum);
}
return dummy.next;
}
删除链表的倒数第 N 个结点
删除链表的倒数第 N 个结点并且返回链表的头结点
详细参见: 19. 删除链表的倒数第 N 个结点 - 力扣（LeetCode）)
算法实现:
type ListNode = LinkedListNode<number> | undefined;
export function removeNthNodeFromEndOfList(head: ListNode, n: number): ListNode {
// 倒数第 n 个节点也就是正数第 len - n 个节点
// 而删除此节点需要获取其前一个节点的位置
// 所以我们让指针 p1 先走 n + 1 步
// 剩下的路程就是 len - n - 1
// 也就是倒数第n个节点的前一个节点
// 创建虚拟头节点用于处理边界问题
const dummy = new LinkedListNode(-1);
dummy.next = head;
// 让指针p1先走 n + 1 步
let p1: ListNode = dummy;
for (let i = n + 1; i > 0; i--) {
p1 = p1?.next;
}
// 再让指针p2跟随p1一起走 len - n - 1 找到倒数第n个节点的
let p2: ListNode = dummy;
while (p1) {
p1 = p1.next;
p2 = p2?.next;
}
if (p2) {
p2.next = p2.next?.next;
}
return dummy.next;
}
反转链表
给你单链表的头节点 head, 请你反转链表, 并返回反转后的链表
详细参见: 206. 反转链表 - 力扣（LeetCode）)
算法实现:
type ListNode = LinkedListNode<number> | undefined;
export function reverseList(head?: ListNode): ListNode {
// 三指针操作节点, pre 用于保存上一个节点的信息, next用于临时保存下一个节点的信息
let pre = undefined;
let cur = head;
// 假设 head = [1, 2, 3, 4, 5]
while (cur) {
// 此时 cur(当前节点) = [1, 2, 3, 4, 5], pre(上一个节点) = null, next(下一个节点) = [2, 3, 4, 5]
const next = cur.next;
// 将 cur 的 下一个节点更新为 pre 就可以得倒一个 [1, null] 的链表
// 下次迭代即为 node([2, 3, 4, 5]).next = pre([1, null]) = [2, 1, null]
cur.next = pre;
// 再将 [1, null] 保存至 pre
// 重复即可得 [2, 1, null], [3, 2, 1, null], [4, 3, 2, 1, null], [5, 4, 3, 2, 1, null]
pre = cur;
// 最后更新 cur 为 next (即 [2, 3, 4, 5])
cur = next;
}
return pre;
}