图解链表结构
链表(非连续的) VS 数组的物理存储结构(连续存储)
链表通过指针将一组零散的内存块串联在一起。其中,我们把内存块称为链表的“结点”。为了将所有的结点串起来,每个链表的结点除了存储数据之外,还需要记录链上的下一个结点的地址。如图所示,我们把这个记录下个结点地址的指针叫作后继指针 next。
我们习惯性地把第一个结点叫作头结点,把最后一个结点叫作尾结点。其中,头结点用来记录链表的基地址。有了它,我们就可以遍历得到整条链表。而尾结点特殊的地方是:指针不是指向下一个结点,而是指向一个空地址 NULL,表示这是链表上最后一个结点。
单链表
循环链表
双向链表
常见的链表操作
链表尾部添加元素
链表中插入元素
代码实现链表
const assert = require("assert");
class Node {
constructor(element) {
this.element = element;
this.next = null;
}
}
class LinkedList {
constructor() {
this.head = null;
this.length = 0;
}
// 在链表尾部追加结点
append(element) {
const addNode = new Node(element);
// 空链表
if (this.isEmpty()) {
this.head = addNode;
} else {
// 非空链表,先找到链表尾部
let cur = this.head;
while (cur.next) {
cur = cur.next;
}
cur.next = addNode;
}
this.length += 1;
}
insert(position, element) {
// 边界情况处理
if (
(Number.isInteger(position) && position > -1) ||
position < this.size()
) {
const addNode = new Node(element);
let cur = this.head;
let prev = null;
// 在链表头位置插入
if (position === 0) {
this.head = addNode;
addNode.next = cur;
} else {
// 在其他位置插入
let index = 0;
while (index < position) {
prev = cur;
cur = cur.next;
index++;
}
prev.next = addNode;
addNode.next = cur;
}
this.length++;
}
}
removeAt(position) {
if (
(Number.isInteger(position) && position > -1) ||
position < this.size()
) {
let cur = this.head;
// 移除链表头
if (position === 0) {
this.head = cur.next;
} else {
// 移除其他元素
let index = 0;
let prev = null;
while (index < position) {
prev = cur;
cur = cur.next;
index++;
}
prev.next = cur.next;
}
this.length--;
return cur;
}
return null;
}
indexOf(element) {
let index = 0;
let cur = this.head;
while (cur) {
if (cur.element === element) {
return index;
}
cur = cur.next;
index++;
}
return -1;
}
remove(element) {
return this.removeAt(this.indexOf(element));
}
isEmpty() {
return this.length === 0;
}
size() {
return this.length;
}
}
// test case
const l = new LinkedList();
l.append(1);
assert.strictEqual(l.head.element, 1);
l.append(2);
l.append(3);
assert.strictEqual(l.length, 3);
l.insert(0, 0);
l.insert(1, 100);
assert.strictEqual(l.head.next.element, 100);
assert.strictEqual(l.removeAt(1).element, 100);
assert.strictEqual(l.size(), 4);
assert.strictEqual(l.head.next.element, 1);
assert.strictEqual(l.indexOf(1), 1)
assert.strictEqual(l.remove(3).element, 3)
assert.strictEqual(l.size(), 3);
链表 VS 数组性能大比拼
不过,数组和链表的对比,并不能局限于时间复杂度。而且,在实际的软件开发中,不能仅仅利用复杂度分析就决定使用哪个数据结构来存储数据。数组简单易用,在实现上使用的是连续的内存空间,可以借助 CPU 的缓存机制,预读数组中的数据,所以访问效率更高。而链表在内存中并不是连续存储,所以对 CPU 缓存不友好,没办法有效预读。
数组的缺点是大小固定,一经声明就要占用整块连续内存空间。如果声明的数组过大,系统可能没有足够的连续内存空间分配给它,导致“内存不足(out of memory)”。如果声明的数组过小,则可能出现不够用的情况。这时只能再申请一个更大的内存空间,把原数组拷贝进去,非常费时。链表本身没有大小的限制,天然地支持动态扩容,我觉得这也是它与数组最大的区别。
所以,在我们实际的开发中,针对不同类型的项目,要根据具体情况,权衡究竟是选择数组还是链表
PS: 感兴趣的可以关注下我的公众号。