本文主要将双链表的定义、创建、插入、删除以及查询。另外，为了修改双向链表方便，本篇的所有例子都是带头节点的。
双向链表的含义
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。
在双向链表中第一个节点的前驱以及最后一个节点的后继指向NULL
双向链表的结构：
//双向链表
typedef struct SXNode{
ElementType data;
struct SXNode *prior;//前驱
struct SXNode *next;//后继
}SXNode;
双向链表存储结构图：
image.png
image.png
双向链表的创建，依然使用尾插法创建：
//双向链表创建
Status createSXLinkList(SXLinkList *node){
*node = malloc(sizeof(SXNode));
if (*node == NULL)
return ERROR;
(*node)->prior = NULL;
(*node)->next = NULL;
(*node)->data = -1;
//采用尾插法，记录最后节点的位置
SXLinkList p = *node;
for (int i = 1; i < 10; i++) {
SXLinkList temp = malloc(sizeof(SXNode));
if (temp == NULL)
return ERROR;
temp->next = NULL;
temp->prior = p;
temp->data = i;
p->next = temp;
//记录最后一个节点，其实使用p = temp也是一样
//p = p->next;
p = temp;
}
return OK;
}
双向链表的插入：
1.找到要插入位置的前一个节点p
2.新建节点q，使得q->next = p->next;q->prior = p;
1）如果q是最尾节点节点，它的下一个节点的前驱是不存在的
2）if (p->next) p->next->prior = q;
3.p->next = p;
//双向链表的插入
Status insertSXLinkList(SXLinkList *node,int place, ElementType e){
if (*node == NULL)
return ERROR;
if (place < 1)
return ERROR;
SXLinkList p = *node;
int i = 1;
while (i < place && p) {
i++;
p = p->next;
}
if (p == NULL)
return ERROR;
SXLinkList temp = malloc(sizeof(SXNode));
if (temp == NULL)
return ERROR;
temp->data = e;
temp->next = p->next;
temp->prior = p;
if (p->next) {//如果是尾节点
p->next->prior = temp;
}
p->next = temp;
return OK;
}
双向链表的删除
1.找到要插入位置的前一个节点p
2.记录删除节点q，使得q = p->next; p->nex = q->next;
1）如果q是最尾节点节点，它的下一个节点的前驱是不存在的
2）if (q->next) q->next->prior = p;
3.删除q节点
//双向链表的删除
Status deleteSXLinkList(SXLinkList *node,int place, ElementType *e){
if (*node == NULL)
return ERROR;
if (place < 1)
return ERROR;
SXLinkList p = (*node);
int i = 1;
while (i < place && p) {
i++;
p = p->next;
}
if (i > place || !p || !p->next)//超出范围
return ERROR;
SXLinkList temp = p->next;
p->next = temp->next;
if (temp->next)//当我们删除尾节点时，不会有前驱
temp->next->prior = p;
*e = temp->data;
free(temp);
return OK;
}
// 删除双向链表指定的元素
Status deleteElemFromSXList(SXLinkList* node,ElementType elem){
SXLinkList p = *node;
while (p) {
if (p->data == elem) {//找到要删除的节点
//该节点的前一个节点的后继指向删除节点的后继
p->prior->next = p->next;
if (p->next) {//如果是尾节点，该节点没有没有后继
//删除节点的后继的前驱是删除节点的前驱
p->next->prior = p->prior;
}
free(p);
return OK;
}
//没有找到，继续下一个节点
p = p->next;
}
return ERROR;
}
// 在双向链表中查找元素
int findElemFromSXList(SXLinkList node,ElementType elem){
SXLinkList p = node->next;
int i = 1;
while (p) {
if (p->data == elem) {
return i;
}
i++;
p = p->next;
}
return -1;
}
双向循环链表
双向循环链表与双向链表的区别是，每一个节点都有前驱后继
双向循环链表创建
Status createSXCycleLinkList(SXLinkList *node){
*node = malloc(sizeof(SXNode));
if (*node == NULL)
return ERROR;
(*node)->prior = *node;
(*node)->next = *node;
(*node)->data = -1;
//采用尾插法，记录最后节点的位置
SXLinkList p = *node;
for (int i = 1; i < 3; i++) {
SXLinkList temp = malloc(sizeof(SXNode));
if (temp == NULL)
return ERROR;
//数据域赋值
temp->data = i;
//尾节点的后继指向头节点
temp->next = *node;
temp->prior = p;
p->next = temp;
//更新头节点的前驱
(*node)->prior = temp;
//记录最后一个节点，其实使用p = temp也是一样
p = p->next;
//p = temp;
}
return OK;
}
双向循环链表插入
1.查找要插入的位置的前一个位置p
3.新建节点q，使得q->next = p->next;q->prior=p;
4.如果插入的位置是尾节点，则需要更新头节点的前驱:(*node)->prior = q
5.如果插入的位置不是尾节点，p->next->prior = q
6.p->next = q;
Status insertSXCycleLinkList(SXLinkList *node,int place, ElementType e){
if (*node == NULL)
return ERROR;
if (place < 1)
return ERROR;
SXLinkList p = *node;
int i = 1;
//查找插入位置
while (i < place && p) {
i++;
p = p->next;
}
if (p == NULL)
return ERROR;
SXLinkList temp = malloc(sizeof(SXNode));
if (temp == NULL)
return ERROR;
//给数据域赋值
temp->data = e;
//新建节点的后继是p->next
temp->next = p->next;
//新建节点的前驱是p
temp->prior = p;
if (p->next != *node) {//如果不是尾节点
p->next->prior = temp;
}else{//如果是尾节点，需要更新头节点的前驱
(*node)->prior = temp;
}
//p的后继是新建节点
p->next = temp;
return OK;
}
双向循环链表删除
1.如果只有一个节点，先释放，再将链表置为空
2.如果有多个节点，先找到要删除的节点
3.修改该节点前后节点的前驱后继
Status deleteSXCycleLinkList(SXLinkList *node,int place, ElementType *e){
if (*node == NULL)
return ERROR;
if (place < 1)
return ERROR;
SXLinkList p = (*node)->next;
if (p->next == (*node)) {//如果只有一个节点，删除之后，链表置空
free(*node);
free(p);
*node = NULL;
return OK;
}
int i = 1;
//找到删除的节点
while (i < place && p != (*node)) {
i++;
p = p->next;
}
if (i<=place && p == (*node))//超出范围
return ERROR;
p->prior->next = p->next;
p->next->prior = p->prior;
*e = p->data;
free(p);
return OK;
}
网友评论