链表
- 链表的每个节点至少包含两部分:数据域 与 指针域,并且每个节点,通过指针域的值,形成的一个线性结构
- 指针域的指在不同编程语言中有不同的概念,如 C 语言中的
地址
,js/python/java 中的引用
,数组的下标,也叫相对地址,都可以作为指针域
- 指针域的指在不同编程语言中有不同的概念,如 C 语言中的
- 链表查找节点的复杂度为O(n),插入/删除节点的复杂度为 O(1)
- 链表不适合快速的定位数据,比较适合动态的插入和删除数据的应用场景
创建链表的四种方法
用构造函数创建对象的方式,比较好理解
const createListNode1 = () => {
function ListNode(value) {
this.value = value;
this.next = null;
}
const head = new ListNode(1);
head.next = new ListNode(2);
head.next.next = new ListNode(3);
head.next.next.next = new ListNode(4);
let current = head;
let listNodeValue = [];
while (current !== null) {
listNodeValue.push(current.value);
current = current.next;
}
console.log(listNodeValue.join("->"));
};
createListNode1(); // 1->2->3->4
创建 2 个数组,一个当作数据域,一个当作指针域,也能创建链表,不好理解,但很神奇
const createListNode2 = () => {
let next = []; // 指针域
let data = []; // 数据域
// 在 index 的位置,添加一个节点 node,其值为 value
const addNode = (index, node, value) => {
// 将插入的节点的指针指向 当前插入位置的 下一个节点
next[node] = next[index]; // 这行代码是防止不按顺序插入节点
next[index] = node;
data[node] = value;
};
const head = 3; // 定义头节点 3,其值为 0
data[3] = 0;
addNode(3, 5, 1); // 在节点 3 的后面添加节点 5,其值为 1
addNode(5, 2, 2);
addNode(2, 7, 3);
addNode(7, 9, 4); // 现在的链表为 0->1->2->3->4
addNode(5, 6, 5); // 不按顺序插入节点,0->1->5->2->3->4
let node = head;
let listNodeValue = [];
while (node) {
listNodeValue.push(data[node]);
node = next[node];
}
console.log(listNodeValue.join("->"));
};
createListNode2(); // 0->1->5->2->3->4
todo
todo
链表的应用场景
操作系统内的动态内存分配
- 用于操作系统内的动态内存分配,管理剩余的内存空间
- 如下图所示,一块 4G 的内存,被 malloc 申请 1G 内存之后,剩下的内存区在底层就是通过链表去维护的
LRU 缓存淘汰算法
- 实际的实现不是简单的链表,而是哈希链表
- 这里简单理解缓存中存储的数据,是通过普通链表维护的
- 假设缓存总共只能存 3 个数据,当要存第 4 个数据时,系统会将最先插入的数据 1 删除,然后在数据 3 后面添加一个数据 4