线性表

2.5.3 循环链表

最后一个结点的指针域指向头结点

终止条件：p != L && p -> next != L

循环链表的合并：设立尾指针。将第一个表的尾指针指向第二个表的第一个结点，第二个表的尾指针指向第一个表的头结点，然后释放第二个表的头结点。时间复杂度是O（1）

2.5.4 双向链表

克服了单链表单向性的缺点，即既可以查找直接后继，也可以查找直接前驱

一个双链表结点有两个指针域。

d -> next -> prior = d -> prior -> next = d

插入

在第i个位置之前插入元素e

先找到第i - 1个结点的指针域，生成新结点使之数据域赋为e，然后对第i - 1个和第i个结点的指针域赋值（注意赋值顺序），实现新元素的插入。

s = new DulNode;
s -> data = e;
s -> prior = p -> prior;
p -> prior -> next = s;
s -> next = p;
p -> prior = s;

> 第3 4和5 6行代码可以换顺序 但是不能把5 6放在3 4前面 因为5 6改变了p的前驱

删除

删除第i个结点

找到第i - 1个结点的指针域，分别修改被删结点的前驱结点的后继指针和其后继结点的前驱指针

p -> prior -> next = p -> next;
p -> next -> prior = p -> prior;
delete p;