定义
在单向链表的元素中，添加一个指向前驱元素(也就是前一个元素)的指针域。元素中既有指向前驱元素的指针，又有指向后继元素的指针。这种形式的链表叫做双向链表。
其存储结构如下：
typedef int ElementType;
typedef struct DouNode{
ElementType data;
struct DouNode *next;
struct DouNode *prior;
}DouNode;
typedef struct DouNode * linkList;
双向链表
初始化双向链表
TStatus InItDoubleLinkList(LinkList *dl) {
(*dl) = (LinkList)malloc(sizeof(DouNode));
if (*dl == NULL) {
return T_ERROR;
}
(*dl)->data = -1;
(*dl)->next = NULL;
(*dl)->prior = NULL;
return T_OK;
}
双向插入.png
插入双向链表的元素
双向链表由于存在两个指针域，所以插入的时候需要对其进行处理。
在第i个位置插入元素，大概步骤如下：
- 创建新结点
q - 遍历链表，找到需要插入的位置的前一个元素
p - 将新元素
q的前驱指向p，后继指向p->next - 将
p->next的前驱指向新元素q - 将
p的后继指向新元素q
TStatus InsertElement(LinkList *dl, int i, ElementType e) {
if (*dl == NULL) {
return T_ERROR;
}
LinkList p = (*dl);
int j = 1;
while (p && j < i) {
p = p->next;
j += 1;
}
if (p == NULL || j > i) {
return T_ERROR;
}
// 新插入的元素
LinkList q = (LinkList)malloc(sizeof(DouNode));
q->data = e;
// q的指向
q->next = p->next;
q->prior = p;
// q后继元素的指向
if (p->next != NULL) {
p->next->prior = q;
}
// p的指向
p->next = q;
return T_OK;
}
删除双向链表的元素
双向删除.png
删除第i个位置的元素，大概步骤如下：
- 遍历链表，找到想要删除的位置的前一个元素
p - 创建新结点
q，将要删除的元素赋值给p - 将
p->next指向q->next，将q->next的前驱指向p - 释放
q
TStatus DeleteElement(LinkList *dl, int i, ElementType *e) {
if (*dl == NULL) {
return T_ERROR;
}
LinkList p = (*dl);
int j = 1;
// 1234
while (p && j < i) {
p = p->next;
j += 1;
}
if (p == NULL || j > i) {
return T_ERROR;
}
LinkList delQ = p->next;
*e = delQ->data;
p->next = delQ->next;
if (delQ->next != NULL) {
delQ->next->prior = p;
}
free(delQ);
return T_OK;
}
也可以通过数据来删除具有相同的数据的元素，此处我们只考虑链表中最多只有一个元素数据为传入的数据。
TStatus DeleteElementWithData(LinkList *dl, ElementType e) {
if (*dl == NULL) {
return T_ERROR;
}
LinkList p = (*dl);
while (p != NULL) {
if (p->data == e) {
break;
}
p = p->next;
}
if (p == NULL) {
return T_ERROR;
}
// 要删除的前一个元素
LinkList preQ = p->prior;
preQ->next = p->next;
if (p->next != NULL) {
p->next->prior = preQ;
}
free(p);
return T_OK;
}
获取元素
获取双向链表第i个位置的元素。
- 遍历链表找到第
i个位置前一个位置的元素p - 容错判断
- 返回
p->next
TStatus GetElement(LinkList *dl, int i, ElementType *e) {
if (*dl == NULL || i < 1) {
return T_ERROR;
}
LinkList p = (*dl);
int j = 1;
while (p && j < i) {
p = p->next;
j += 1;
}
if (p->next == NULL && j > i) {
return T_ERROR;
}
*e = p->next->data;
return T_OK;
}
整表创建
采用尾插法整表创建双向链表:
- 初始化链表
- 遍历传入的数据，循环创建结点，加到链表的尾部
TStatus createDoubleLinkList(LinkList *dl, int arr[], int size) {
*dl = (LinkList)malloc(sizeof(DouNode));
if (*dl == NULL) {
return T_ERROR;
}
(*dl)->data = -1;
(*dl)->prior = NULL;
(*dl)->next = NULL;
LinkList r = (*dl);
LinkList p;
for (int i = 0; i < size; i++) {
int e = arr[i];
p = (LinkList)malloc(sizeof(DouNode));
if (p == NULL) {
return T_ERROR;
}
p->data = e;
p->prior = r;
p->next = NULL;
r->next = p;
r = p;
}
return T_OK;
}
双向循环链表
双向循环链表的概念其实和单向循环链表类似，也是将链表中最后一个结点的next针由空指针改为指向头指针指向的元素，不同的是我们还需要将头指针指向的元素的前驱指针prior指向最后一个结点，这样链表就形成了一个环。
双向循环.png
初始化双向循环链表
初始化双向循环链表的时候，需要将自己的next和prior都指向自己。
TStatus InItDoubleLinkList(LinkList *dl) {
(*dl) = (LinkList)malloc(sizeof(DouNode));
if (*dl == NULL) {
return T_ERROR;
}
(*dl)->data = -1;
(*dl)->next = (*dl);
(*dl)->prior = (*dl);
return T_OK;
}
双向循环链表删除元素
TStatus DeleteElement(LinkList *dl, int i, ElementType *e) {
if (*dl == NULL) {
return T_ERROR;
}
LinkList p = (*dl);
int j = 1;
// 找到需要删除的位置的前一个位置
while (p && j < i && p->next != (*dl)) {
p = p->next;
j += 1;
}
if (p->next == NULL || j > i) {
return T_ERROR;
}
LinkList delQ = p->next;
*e = delQ->data;
delQ->prior = p;
p->next = delQ->next;
free(delQ);
return T_OK;
}
可以看出来，双向循环链表和双向链表的操作类似，只是多了循环的相关处理。
线性表总结
- 线性表是零个或者多个具有相同类型的数据元素的有限序列。
- 线性表的存储结构：
- 顺序存储结构
- 链式存储结构
- 单链表
- 静态链表
- 循环链表
- 双向链表
