双向链表的定义
双向链表，又称为双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
结构设计
| 指针域 | 数据域 | 指针域 |
|---|---|---|
| 前驱指针 | 存储数据 | 后继指针 |
/* 双向链表结构设计 */
typedef struct Node {
ElemType data; /* 数据域 */
struct Node *prior; /* 前驱指针 */
struct Node *next; /* 后继指针 */
}Node, *LinkList;
双向链表于单向链表最大的区别就是一个节点不仅仅拥有后继指针指向它的下一个结点，而且还拥有一个前驱指针指向它的前一个结点。
基本操作（头结点、C语言）
以下的所有链表包含头结点，但并不是说单向循环链表不支持头结点的存在。
因为单向循环链表中如果使用头结点，遍历会比较麻烦，所以直接使用首元结点
1. 构建
创建一个包含头结点的双向链表。
代码如下：
/* 创建头结点，将结点的前驱指针、后继指针置空，数据设置为-1，其实没有意思 */
Status initList(LinkList *L) {
Node * head = *L;
head = (LinkList)malloc(sizeof(Node));
if (head == NULL) {
return ERROR;
}
head->data = -1;
head->prior = NULL;
head->next = NULL;
*L = head;
return OK;
}
2. 遍历
/* 由于头结点不需要打印，所以从头结点的next开始遍历 */
void traversList(LinkList L) {
Node *head = L->next;
if (head == NULL) {
printf("当前链表为空\n");
return;
}
while (head != NULL) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
3. 插入
在插入结点时，我们需要去判断插入的位置是否是在表尾。
- 在表尾：
- 除表尾外任意位置：
代码如下：
Status insertList(LinkList *L, int index, ElemType e) {
// 判断链表是否为空，插入位置是否合法
if ((*L) == NULL || index < 1) {
return ERROR;
}
// 判断创建新的结点
Node *temp = malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = e;
temp->next = NULL;
temp->prior = NULL;
Node *head = *L;
for (int i = 1; i < index; i++) {
if (head->next == NULL) {
break;;
}
head = head->next;
}
if (head == NULL) {
// 插入位置超过链表长度
return ERROR;
}
if (head->next == NULL) {
// 在尾结点位置插入
// 将head的后继指针指向temp
head->next = temp;
// 将temp的前驱指针指向head
temp->prior = head;
}else {
// 不在尾结点位置插入
// 将head的后继结点的前驱指针指向temp
head->next->prior = temp;
// 将temp的后继指针指向head的后继结点
temp->next = head->next;
// 将head的后继指针指向temp
head->next = temp;
// 将temp的前驱指针指向head
temp->prior = head;
}
return OK;
}
4. 删除
在删除结点时，我们需要去判断删除的位置是否是在表尾。
- 在表尾：
- 除表尾外任意位置：
代码如下：
Status deleteList(LinkList *L, int index) {
// 判断链表是否为空，插入位置是否合法
if ((*L) == NULL || index < 1) {
return ERROR;
}
Node *temp = (*L)->next;
for (int i = 1; i < index; i++) {
if (temp->next == NULL) {
break;;
}
temp = temp->next;
}
printf("删除数据: %d\n", temp->data);
if (temp->next == NULL) {
temp->prior->next = NULL;
free(temp);
}else {
temp->next->prior = temp->prior;
temp->prior->next = temp->next;
free(temp);
}
return OK;
}
双向循环链表的定义
在双向链表的基础上，将尾结点的后继指针，指向头结点；头结点的前驱指针，指向尾结点，构成一个循环链表。
结构设计
在结构上，双向循环链表的结构和双向链表的结构是相同的。
基本操作（C语言）
以下的所有链表同样包含头结点
1. 构建
创建一个包含头结点的双向循环链表。
双向循环链表将双向链表的基础上，将头结点的前驱指针和后继指针指向本身，从而构成了一个循环链表。
代码如下：
/* 创建头结点，将头结点的后继指针和前驱指针都指向自己 */
Status initList(LinkList *L) {
Node * head = *L;
head = (LinkList)malloc(sizeof(Node));
if (head == NULL) {
return ERROR;
}
head->data = -1;
head->prior = head;
head->next = head;
*L = head;
return OK;
}
2. 遍历
void traversList(LinkList L) {
Node *head = L->next;
if (head == L) {
printf("当前链表为空\n");
return;
}
while (head != L) {
printf("%d ", head->data);
head = head->next;
}
printf("\n");
}
3. 插入
在插入结点时，我们需要去判断插入的位置是否是在表尾。
- 在表尾：
- 除表尾外任意位置：
代码如下：
Status insertList(LinkList *L, int index, ElemType e) {
if (*L == NULL || index < 1) {
return ERROR;
}
Node *head = *L;
int i = 1;
while (i < index && head->next != *L) {
head = head->next;
i++;
}
if (i > index) {
return ERROR;
}
Node *temp = malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->data = e;
temp->prior = head;
temp->next = head->next;
head->next = temp;
if (temp->next != *L) {
temp->next->prior = temp;
}else {
(*L)->prior = temp;
}
return OK;
}
4. 删除
代码如下：
Status deleteList(LinkList *L, int index) {
// 判断链表是否为空，插入位置是否合法
if ((*L) == NULL || index < 1) {
return ERROR;
}
Node *temp = (*L)->next;
if (temp->next == *L) {
free(*L);
*L = NULL;
return ERROR;
}
int i = 1;
while (i < index && temp != NULL) {
temp = temp->next;
i++;
}
if (i > index || temp == NULL) {
return ERROR;
}
Node *delete = temp;
printf("删除数据: %d\n", delete->data);
delete->prior->next = delete->next;
delete->next->prior = delete->prior;
free(delete);
return OK;
}