接昨天，仍没有代码实现。

3.Linked list（链表）

在数组 (Array) 中，元素顺序是由数组索引决定。数组插、删元素的时候会移动很多元素，所以时间复杂度会更高；且数组占用的空间是连续的，必须声明足够的空间。

但在链表中，元素顺序由每个对象的指针决定。链表的存储是不连续的，可以节省很多空间。

如下图所示，链表中每一个object中，除了存储element的key外，还额外开辟出了两个内存空间，prev(ious)以及next。这个prev和next分别为访问前一个链表节点以及后一个链表节点。

如果x.prev为NULL，则这个节点中的element，即x，为首元素，或称为head；反之若x.next为NULL，则x为尾元素，或成为tail.

 

 

 

 

 

 

上图是一个双链表，即可以双向链接。除此之外还有单链表，即单向链接，只能寻找上一个或者下一个节点；还有循环单链表，即尾部tail可以去寻找head。

关于L.head的理解，（有点难）。L.head要理解为一个pointer，而不是一个对象。非空链表的第一个结点称为链表的head。要访问链表中的对象，需要有一个指向链表头的指针。从head开始，可以根据 .next 访问链表中的其余节点，也可以反过来通过 .prev访问前面的节点。

 对链表的操作

 Insert（简化程序为插在表头）

x.next = L.head         #将原来.head，赋给新插入的对象x.next，就是把原来的头，和新插入x的屁股接在了一起（粗暴理解）
if L.head != NULL       #如果原来的.head不是NULL
    L.head.prev = x     #则让原来.head的.prev指针 → x。目前新插入对象x与后面的正反向指针都有了。
L.head = x              #让新插入的对象x 成为新的.head。
x.prev = NULL           #此时让x的左侧指针（指向前方的）为NULL。新head诞生。

insert的时间复杂度为O(1)。

 

 Delete

if x.prev !=NULL        #若被删除对象.prev非NULL，也就是不是首个对象
    x.prev.next = x.next#则可将 被删除对象.next指针，指向被删除对象.prev的对象.next指针，有点乱。下图中就是4.next → 16.next
else L.head = x.next    #若被删除对象.prev为NULL，是首个对象的话。则把x.next的指针赋给L.head，令x.next成为链表新的head（没head不行）
if x.next != NULL       #如果被删除对象.next非NULL，也就是不是最后一个对象
    x.next.prev = x.prev#则可将 被删除对象.pre的指针，指向被删除对象.next的对象.prev的指针。下图就是4.prev → 1.prev

 

Delete的时间复杂度同上，O(1)。

 

写在最后，如果实在理解不了，去观看电影《人体蜈蚣》，会加深理解。