链表

我们要存储一个有序的对象列表，正常的选择会是一个数组：

let arr = [obj 1, obj 2, obj 3]

但是用数据有个问题。"删除元素"和"插入元素"的操作代价很大，arr.unshift(obj)操作必须对所有元素重新编号以便为新的元素ojb出空间，如果数组很大，会耗费大量时间。此时我们可以选择另一种叫做链表的数据结构。

链表元素 是一个使用以下元素通过递归定义的对象：

let list = {

    value: 1,

    next: {

        value: 2,

        next: {

            value: 3

            next: null

        }

    }

}

注：value为当前链表元素的值，next属性引用下一个链表元素或者代表末尾的null。

一段用来创建链表的代码：

let list = { value: 1 };

list.next = { value: 2 };

list.next.next = { value: 3 };

list.next.next.next = null;

从上面的代码我们可以清楚地看到，这里有很多个对象，每一个都有value和指向邻居的next。变量list是链表中的第一个对象，因此顺着next指针，我们可以抵达任何元素。

比如，将新值添加到链表头部

list = { value: "new item", next: list }

要从中间删除一个值，可以修改前一个元素的next：

list.next = list.next.next

我们让 list.next 从 1 跳到值 2。现在值 1 就被从链表中移除了。如果它没有被存储在其它任何地方，那么它会被自动从内存中删除。

链表和数组对比

与数组不同，链表没有大规模重排，我们可以很容易地重新排列元素。链表主要的缺点就是我们无法很容易地通过元素的编号获取元素。但在数组中却很容易：arr[n] 是一个直接引用。而在链表中，我们需要从起点元素开始，顺着 next 找 N 次才能获取到第 N 个元素。