首页 计算机科学 数据结构 线性表

# 双向链表

1. 概念

在双向链表中，每个结点有两个指针域，一个指向后继
结点，另一个指向直接前驱结点。

判空：

L->next==Null  &&  L->prior==Null

2. 定义

typedef struct DuLNode {
    DataType data;
    struct DuLNode *prior;
    struct DuLNode *next;
}DuLNode, *DuLinkList;
// 定义头指针： DuLinkList L;
// 定义工作指针： DuLNode *p;
双向链表具有对称性：
p->prior->next=p=p->next->prior
3. 操作
1) 插入
//在P后面插入：
s->next = p->next;
s->prior = p;
p->next->prior = s;
p->next = s;

//在P前面插入：
s->next = p;
s->prior = p->prior;
p->prior->next = s;
p->prior = s;

//插入P：
p->next = q->next;
p->prior = q;
q->next->prior = p;
q->next = p;

2) 删除
// 删除 P 后边的结点
q = p->next;
q->next->prior = p;
p->next = q->next;
free(q);
// 删除 P 前边的结点
q = p->prior;
q->prior->next = p;
p->prior = q->prior;
free(q);
// 删除 P
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
-->