javascript 中的链表

链表作为一种基础的数据结构，相较于数组的优势是不需要预先知道存储数据的大小，但也就无法像数组那样通过下标方便读取。

但是在javascript中本身没有链表，只有数组，但是得益于javascript中数组的一些方法，比如 push pop unshift shift splice等，使得数组可以方便的模拟链表，并且可以用下标直接访问。

但我们也可以通过一些方法来创建出更接近链表的结构。

单向链表

1
2
3
4
function Chain(val) {
    this.val = val;
    this.next = null;
}

以上的结构可以简单模拟单向链表。

比如把数组 ['January', 'February', 'March', 'April'] 转换成单向链表。

1
2
3
4
5
6
7
8
9
10
11
let array = ['January', 'February', 'March', 'April'];
let head = new Chain(array.shift());
let tail = head;
while(array.length > 0) {
    let node = new Chain(array.shift());
    tail.next = node;
    tail = node;
}

// 现在其中的值只能通过头部逐一向后查找了
console.log(head);

循环链表

如果把尾部的next指向头部， 我们就得到了一个循环链表

1
tail.next = head;

双向链表

如果我们修改下 Chain 的结构, 增加一个向前的“指针“

1
2
3
4
5
function Chain(val) {
    this.val = val;
    this.prev = null;
    this.next = null;
}

并在创建链表的时候多做一点，将当前节点的“前指针”指向前一个节点，于是就能得到一个双向链表。

1
2
3
4
5
6
7
8
9
10
let array = ['January', 'February', 'March', 'April'];
let head = new Chain(array.shift());
let tail = head;
while(array.length > 0) {
    let node = new Chain(array.shift());
    tail.next = node;
    node.prev = tail;
    tail = node;
}
console.log(head);

双向循环链表

将双向链表的最后一个节点与第一个节点相连

1
2
tail.next = head;
head.prev = tail;