对比 单向链表结构，双向链表多了一个指针 tail，它是指向最后一个结点，通过最后一个结点也可以向前遍历每个元素。

A、B、C、D四个结点的双向链表：

双向链表，每个结点中除了表示数据的data属性，还有指向前驱（pre）和后继（next）的指针。

struct Node{
    char data;
    Node *pre;
    Node *next;
}; 

一、遍历结点

从链表头开始，依次向后遍历（查找）即可。

Node *cur = &A;	//head（头）结点开始
while(cur) {
	print(cur->data);
	cur = cur->next;//依次向后
}

从链表尾开始，倒序遍历

Node *cur = &D;	//tail（尾）结点开始
while(cur) {
	print(cur->data);
	cur = cur->pre;	//依次向前
}

二、插入结点

给定一个双向链表：在位置 i 的后面插入一个值为 data 的结点（或者在指定的结点后面插入）。

如在A的结点后面插入结点E：

• 新结点 E

• E->next = A->next;

• E->pre = A;

• A->next->pre = E;

• A->next = E;

先完成结点E的后继和前驱；再完成原有链表结点的插入；

Node *pa = &A;
Node E = {'E'};
Node *pe = &E;

//E结点后继和前驱
pe->next = pa->next;
pe->pre = pa; 

//插入E结点
pa->next->pre = pe;
pa->next = pe;

三、删除结点

一个链表 i 位置的结点删除并且返回被删除的结点的值（或者在指定的结点后面删除）。

关注两条虚线，B会被free掉，所以B的pre和next不用管。

• Node *del = A->next

• del->next->pre = A;

• A->next = del->next;

Node *pa = &A;
Node *del = pa->next;
del->next->pre = pa;
pa->next = del->next;
print(del->data);
//free(del)