一、什么是双向链表？
双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。
image.png
1.双向链表的创建
我们通常利用哨兵作为头结点，可以简化操作
1.创建一个头结点；
2.可以利用尾插法初始化一些数据（可不写）
Status createLinkList(LinkList *L) {
//创建哨兵节点简化操作
*L = (LinkList)malloc(sizeof(Node));
if (*L == NULL) {
return ERROR;
}
(*L)->data = -1;
(*L)->prior = NULL;
(*L)->next = NULL;
//创建一个临时指针，指向最后一个节点；
LinkList p = *L;
for (int i = 0; i<100; i++) {
//创建一个临时节点
LinkList temp = (LinkList)malloc(sizeof(Node));
if (L == NULL) {
return ERROR;
}
temp->data = i;
temp->prior = NULL;
temp->next=NULL;
p->next = temp;
temp->prior = p;
p = p->next;
}
return OK;
}
2.双向链表的插入
1.创建新节点
2.找到插入节点的前一个节点；
3.判断插入位置是否为尾节点；
4.尾：前一节点的next指向新节点，新节点的prior指向前一节点，让temp->next = NULL;
5.非尾：过程如下图：
image.png
Status ListInsert(LinkList *L, int i, ElemType data){
//1判断位置
if (i<1) {
return ERROR;
}
//2新建节点
LinkList temp = (LinkList)malloc(sizeof(Node));
if (temp == NULL) {
return ERROR;
}
temp->next = NULL;
temp->prior = NULL;
temp->data = data;
//3将p指向头结点
LinkList p = (*L);
//4找到插入位置的前一个节点
for (int j = 1; j<i&&p; j++,p = p->next);
//5如果超过本身长度
if (p == NULL) {
return ERROR;
}
//6判断是否插入尾部
if (p->next == NULL) {
p->next = temp;
temp->prior = p;
}else {
//1 将p->next 结点的前驱prior = temp
p->next->prior = temp;
//2 将temp->next 指向原来的p->next
temp->next = p->next;
//3 p->next 更新成新创建的temp
p->next = temp;
//4 新创建的temp前驱 = p
temp->prior = p;
}
return OK;
}
3.删除
1.找到删除节点的前一节点p，与删除节点temp;
2.p->next指向temp->next;
3.temp->next->prior指向p;
4.释放p;
image.png
Status ListDelete(LinkList *L, int i, ElemType *e){
int k = 1;
LinkList p = *L;
if (*L == NULL) {
return ERROR;
}
//找到删除位置的前一个节点
for (k=1; k<i && p; k++,p=p->next);
LinkList delTemp;
if (p==NULL&&k>i) {
return ERROR;
}
delTemp = p->next;
*e = delTemp->data;
//这里如果是尾结点，那么delTemp->next = NULL，同时p->next = NULL;
p->next = delTemp->next;
//如果是不是尾结点，让 delTemp下一个节点的前驱指向p
if (delTemp->next != NULL) {
delTemp->next->prior = p;
}
free(delTemp);
return OK;
}
//删除指定元素，找到当前节点p
Status LinkListDeletVAL(LinkList *L, int data){
LinkList p = *L;
while (p) {
if (p->data == data) {
p->prior->next = p->next;
p->next->prior = p->prior;
free(p);
break;
}
p = p->next;
}
return OK;
}
4.双向链表的查找
通过循环找到位置即可
int selectElem(LinkList L,ElemType elem){
LinkList p = L->next;
int i = 1;
while (p) {
if (p->data == elem) {
return i;
}
p = p->next;
i++;
}
return -1;
}
5.更新
1.通过循环找到index位置
2.修改值
Status replaceLinkList(LinkList *L,int index,ElemType newElem){
LinkList p = (*L)->next;
for (int i = 1; i < index; i++) {
p = p->next;
}
p->data = newElem;
return OK;
}
二、双向循环链表
即在双向链表的基础上，尾结点的next指向首节点，首节点的prior指向尾结点
1.空的双向循环链表
image.png
2.非空的双向循环链表
image.png
2.1双向循环链表的初始化
和双向链表不同的是要将尾结点的next指向首节点，首节点的prior指向尾结点
Status creatLinkList(LinkList *L){
*L = (LinkList)malloc(sizeof(Node));
if (*L == NULL) {
return ERROR;
}
(*L)->next = (*L);
(*L)->prior = (*L);
//创建临时节点p
LinkList p = *L;
for(int i=0; i < 10;i++){
LinkList temp = (LinkList)malloc(sizeof(Node));
temp->data = i;
p->next = temp;
temp->prior = p;
temp->next = *L;
(*L)->prior = temp;
p = p->next;
}
return OK;
}
2.2双向循环链表的插入
- 找到插入位置的前一个节点
-
和双向链表的插入不同的是，因为尾结点的next指向的是首节点，可以不用删除的是判断尾结点
3.释放temp
image.png
Status LinkListInsert(LinkList *L, int index, ElemType e){
//1. 创建指针p,指向双向链表头
LinkList p = (*L);
int i = 1;
//2.双向循环链表为空,则返回error
if(*L == NULL) return ERROR;
//3.找到插入前一个位置上的结点p
while (i < index && p->next != *L) {
p = p->next;
i++;
}
//4.如果i>index 则返回error
if (i > index) return ERROR;
//5.创建新结点temp
LinkList temp = (LinkList)malloc(sizeof(Node));
//6.temp 结点为空,则返回error
if (temp == NULL) return ERROR;
//7.将生成的新结点temp数据域赋值e.
temp->data = e;
temp->prior = p;
temp->next = p->next;
p->next = temp;
temp->next->prior = temp;
return OK;
}
2.3双向循环链表的删除
和双向链表的删除类似
1.因为有前驱和后继，所以找到要删除的节点
- temp->prior->next = temp->next;
temp->next->prior = temp->prior;
3.释放temp;
//删除
Status LinkListDelete(LinkList *L,int index,ElemType *e){
int i = 1;
LinkList temp = (*L)->next;
if (*L == NULL) {
return ERROR;
}
//删除的是首元结点，将*L释放置空
if (temp->next == *L) {
free(*L);
*L = NULL;
return OK;
}
//当前要删除的节点temp;
while (i<index) {
i++;
temp = temp->next;
}
*e = temp->data;
temp->prior->next = temp->next;
temp->next->prior = temp->prior;
free(temp);
return OK;
}
2.4双向循环链表的查找与修改
//查找
int selectElem(LinkList L,ElemType elem){
LinkList p = L->next;
int i = 1;
while (p!=L) {
if (p->data == elem) {
return i;
}
i++;
p = p->next;
}
return -1;
}
// 在双向链表中更新结点
Status replaceLinkList(LinkList *L,int index,ElemType newElem){
LinkList p = (*L)->next;
if (index<1)return ERROR;
for (int i = 1; i < index && p != *L; i++) {
p = p->next;
}
if (p == *L) return ERROR;
p->data = newElem;
return OK;
}
