在数组里插入或删除数据需要保证内存空间的连续性，需要做数据的搬移，但是链表里数据内存空间是独立的，插入删除只需要改变指针指向即可，所以链表的插入删除非常高效。如图：
单向链表每个结点只知道自己下一个结点是谁，是一条单向的“链条”，而在双向链表里每个结点既知道下一个结点，还知道前一个结点，相比单链表，双向链表每个结点多了一个前驱指针（prev）指向前一个结点的地址，如下图所示：
因为每个结点要额外的空间来保存前驱结点的地址，所以相同数据情况下，双向链表比单链表占用的空间更多。双向链表在找前驱结点时间复杂度为O(1)，插入删除都比单链表高效，典型的空间换时间的例子。
循环链表将一个单链表首尾相连就形成了一个环，这就是循环链表，循环链表里尾结点不在是null，而是指向头结点。当数据具有环形结构时候就可以使用循环链表。
与循环链表类似，尾结点指向头结点，同时每个结点除了保存自身数据，分别有一个前驱指针和后继指针，就形成了双向循环链表：
1、在P结点后插入数据
new_node->next = p->next; p->next = new_node