一、双链表
单链表结点中只有一个指向其后继的指针，使得单链表只能从头结点依次顺序地向后遍历。
要访问某个结点的前驱结点(插入、删除操作时)，只能从头开始遍历，访问后继结点的时间复杂度为0(1)，访问前驱结点的时间复杂度为O(n)。
为了克服单链表的上述缺点，引入了双链表，双链表结点中有两个指针prior和next，分别指向其前驱结点和后继结点。
1.1 双链表的存储定义：
typedef struct DuLNode{
ElemType data; // 数据域
struct DuLNode *prior,*next; // 前驱和后继指针
}DNode,*DlinkList
双链表在单链表的结点中增加了一个指向其前驱的prior指针，因此双链表中的按值查找和按位查找的操作与单链表的相同。但双链表在插入和删除操作的实现上,与单链表有着较大的不同。
1.2 双链表的初始化：
bool InitDLinklist(DlinkList l&){
L = (DNode *)malloc(sizeof(DNode)); // 分配头结点
if(L==NULL) // 内存不足，分配失败
return false;
L->prior = NULL; // 头结点的prior永远指向NULL
L->next = NULL; // 头结点之后暂时还没有节点
return true;
}
1.3 双链表的判空：
bool Empty(DlinkList L){
if(L->next==NULL)
return true;
else
return false;
}
1.4 双链表的查找操作：
在带头结点的双向链表L中查找第i个元素，返回结点的地址。
DNode *GetElemP_DuL(DlinkList L, int i) {
//在带头结点的双向链表L中查找第i个元素，返回结点的地址
int j;
DlinkList p;
p = L->next;
j = 1; //初始化，p指向第一个结点，j为计数器
while (j<i&&p) { // 循环直到p指向第i个元素或p为空
p = p->next;
++j;
}
if (!p||j>i)
return NULL; // 第i个元素不存在
return p;
}
1.5 双链表的插入操作：
在L中确定第i个元素的位置指针p，进行前插或者后插。
【分析】：循环操作：在L中确定第i个元素的合法位置指针p；再创建s结点，把e赋给s的数据域。
-
在第i位置后插： 充分条件：1、p的下一个结点是s的下一个结点；2、p的下一个结点的前驱是s结点；因此 –> 3、s的(前驱)前一个结点是p，p的(后继)下一个结点是s。
-
在第i位置前插： 充分条件：1、p的上一个结点是s的上一个结点；2、p的上一个结点的后继是s结点；因此 –> 3、s的(后继)后一个结点是p，p的(前驱)上一个结点是s。
1、后插核心代码：
s = new DNode; // 生成新结点*s
s->data = e; // 将结点*s数据域置为e
s->next = p->next;
p->next->prior = s;
s->prior = p;
p->next = s;
++length;
----
2、前插核心代码：
s = new DNode; // 生成新结点*s
s->data = e; // 将结点*s数据域置为e
s->prior = p->prior;
p->prior->next = s;
s->next = p;
p->prior = s;
++length;
----
3、在双向链表的第一个元素上插入
if(i==1){
s = new DNode;
s->data = e;
DlinkList p = L->next;
L->next = s;
s->prior = L;
s->next = p;//将结点*s插入L中
p->prior = s;
++length;
}
----
4、在双向链表的最后一个元素上插入
else if (i == length) { //在双向链表的最后一个元素上插入
s = new DNode; //生成新结点s
s->data = e; //将结点s数据置为e
DlinkList p = L;
while (p->next)
p = p->next; // 将LinkList p指向双向链表结尾
p->next = s;
s->prior = p; // 将结点*s插入到p的后面，插入到L中
s->next = NULL;
++length;
算法双向链表的插入： 在带头结点的双向链表L中第i个位置之前插入元素e，i的合法值为1<=i<=表长+1。
Status ListInsert_DuL(DlinkList &L, int i, ElenType e) { //算法双向链表的插入
DlinkList s, p;
if (!(p = GetElemP_DuL(L, i))) //在L中确定第i个元素的位置指针p
return ERROR; //p为NULL时，第i个元素不存在
if (i == 1) {//在双向链表的第一个元素上插入
s = new DNode; //生成新结点s
s->data = e; //将结点s数据置为e
DlinkList p = L->next;
L->next = s;
s->prior = L;
s->next = p;//将结点*s插入L中
p->prior = s;
++length;
} else if (i == length) {//在双向链表的最后一个元素上插入
s = new DNode; //生成新结点s
s->data = e; //将结点s数据置为e
DlinkList p = L;
while (p->next)
p = p->next;//将LinkList p指向双向链表结尾
p->next = s;
s->prior = p;//将结点*s插入到p的后面，插入到L中
s->next = NULL;
++length;
} else { // 前插
s = new DNode; //生成新结点*s
s->data = e; //将结点*s数据域置为e
s->prior = p->prior; //将结点*s插入L中，
p->prior->next = s;
s->next = p;
p->prior = s;
++length;
}
return true;
}
1.6 双链表的删除操作：
删除带头结点的双向链表L中第i个位置之前插入的元素e，i的合法值为1<=i<=表长。
【分析】：删除p结点，要解决p的前驱与后继指向问题！！
- 1、在L中确定元素e的位置i，指针p指向第i个位置；
- 2、满足：p的前驱的后继 == p的后继；
- 3、满足：p的后继的前驱 == p的前驱 。
p->prior->next = p->next; // 修改被删结点的前驱结点的后继指针
p->next->prior = p->prior; //修改被删结点的后继结点的前驱指针
delete p; //释放被删结点的空间
--length;
删除带头结点的双向链表L中第i个位置之后插入的元素e，i的合法值为1<=i<=表长。
【分析】：删除p结点的后一个结点q，要解决q的前驱与后继指向问题！！
- 1、在L中确定元素e的位置i，指针p指向第i个位置；
- 2、满足：p下一个结点是q的下一个结点；
- 3、满足：q下一个结点的前驱是p结点。
// 删除p结点的后继结点
bool DeleteNextDNode (DNode *p){
if (!(p = GetElemP_DuL(L, i))) //在L中确定第i个元素的位置指针p
return ERROR; // p为NULL时，第i个元素不存在
DNode *q = p->next; // 找到p的后继结点q
if (q==NULL)
return false; // p没有后继
p->next=q->next;
if (q->next!=NULL) // q结点不是最后一个结点
q->next->prior=p;
free(q); //释放结点空间
return true;
}