【初阶数据结构】线性表之双链表

文章目录

目录

一、双链表的概念

二、双链表的实现

1.初始化

2.尾插

3.头插

4.打印

5.判断双链表是否为空

6.尾删

7.头删

8.查找

9.在指定的位置之后插入数据

10.删除指定位置的数据

11.销毁

三、完整源码

总结

---

一、双链表的概念

链表的结构非常多样，以下情况组合起来就有8种链表结构，分为带头，不带头，单向，双向，循环，不循环。

今天我们要了解的是带头双向循环链表，即双链表。

二、双链表的实现

双链表的定义

在实现双链表前，先简单了解三个指针：

1. pcur：当前结点
2. prev：指向当前结点的前一个结点，简称前驱结点
3. next：指向当前结点的后一个结点，简称后继结点

//定义双链表结构体
typedef int LTDatatype;
typedef struct ListNode {LTDatatype data;struct ListNode* next;//指向下一个结点，即后继结点struct ListNode* prev;//指向上一个结点，即前驱结点
}LTNode;

1.初始化

代码解析：

初始化链表就需要开辟空间，在堆上申请一个结点的空间，用函数buyNode来进行实现，初始时让next,prev指向自己，并返回头结点

LTNode* buyNode(LTDatatype x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("NULL");exit(1);}node->data = x;node->next = node->prev = node;return node;
}//初始化
LTNode* LTInit()
{LTNode* phead = buyNode(-1);return phead;
}

注：在双链表中，phead会自己指向自己，不会在指向下一个结点时而丢失，next、prev的指向的变化不会影响当前结点，即地址不会发生改变，所以实现双链表的函数都用一级指针。

2.尾插

代码解析：因为要新插入一个数据，所以开辟一个结点的空间(要插入几个结点，就开辟几个结点的空间)。先设置新结点，把新结点的位置插入到当前链表中，让newnode->prev指向尾结点(phead->prev)，newnode->next指向头结点(phead)；再更新原链表的指向，把尾结点(phead->prev)的next指向newnode，头结点(phead)的prev指向newnode.

//尾插
void LTPushBack(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = buyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}

3.头插

代码解析：

和尾插一样需要开辟一个结点大小的空间。先设置新结点，把新结点的位置插入到当前链表中，让newnode->next指向d1(phead->next)，newnode->prev指向头结点(phead)；再改变链表中d1(phead->next)的位置，让d1->prev指向newnode,头结点(phead)的next指向newnode

//头插
void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = buyNode(x);newnode->next = phead->next;//phead->next为d1newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}

注：把newnode插在d1前面是头插，但插在头结点phead前面是尾插

4.打印

代码解析：通过遍历链表来打印结点

//打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d ->", pcur->data);pcur = pcur->next;}printf("\n");
}

5.判断双链表是否为空

代码解析：

用bool函数判断头结点是否指向自己，是指向自己就为空

//bool类型判断
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}

6.尾删

代码解析：

先判断链表是否为空，不为空就对最后一个结点进行删除。创建新指针del先保存当前结点(即尾结点phead->prev)，避免变成野指针；让d2(del->prev)的next指向头结点，phead->prev指向d2->prev；最后对尾结点进行释放并置为NULL

//尾删
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;//phead del->prev deldel->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}

7.头删

代码解析：

和尾删一样，先判断链表是否为空，不为空就对第一个结点进行删除。这里第一个结点不是头结点是d1。创建新指针del保存当前结点d1(phead->next)，改变链表中的位置，让d2(del->next)的prev指向头结点，头结点的next指向d2(del->next)

//头删
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;//phead del del->nextdel->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}

8.查找

代码解析：

遍历链表中的结点，找到需要查找的结点就返回当前的结点，找不到就返回NULL

//查找
LTNode* LTFind(LTNode* phead, LTDatatype x)
{LTNode* pcur = phead->next;while (pcur){if (pcur->data = x){return pcur;}}return NULL;
}

9.在指定的位置之后插入数据

代码解析：

在指定的位置之后插入数据之前，需要用函数LTFind对其进行查找，避免出错。和前面尾插 头插一样需要申请一个结点空间的大小。先设置新结点，把新结点的位置插入到当前链表中，比如在d2的后面插入一个结点，d2=pos，让newnode->next指向d2->next，newnode->prev指向d2；再改变链表结点的位置，让d3(d2->next)的prev指向newnode,d3指向newnode.

void LTInsert(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode = buyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}

10.删除指定位置的数据

代码解析：

先断言当前结点是否为空，不为空对其进行删除。比如删除d2,d2=pos,让d2->prev的next指向d2->nxet，在让d2->next的prev指向d2->prev.

void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}

11.销毁

代码解析：

创建新指针pcur，让pcur从phead->next开始销毁。循环遍历，又创建一个新指针next,让next从pcur->next开始走，保证next走在pcur前面，对下一个结点pcur->next进行保存，避免删除当前结点pcur时出现野指针的情况；保存好pcur->next就对当前pcur进行释放，让pcur继续往后走pcur=next，一直循环释放，只剩头结点就跳出循环。最后对头结点进行释放并置为空。

void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

三、完整源码

List.h

#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>//定义双链表结构体
typedef int LTDatatype;
typedef struct ListNode {LTDatatype data;struct ListNode* next;struct ListNode* prev;
}LTNode;//初始化
LTNode* LTInit();//打印
void LTPrint(LTNode* phead);
//bool类型判断
bool LTEmpty(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDatatype x);//尾插
void LTPushBack(LTNode* phead, LTDatatype x);//头插
void LTPushFront(LTNode* phead, LTDatatype x);//尾删
void LTPopBack(LTNode* phead);//头删
void LTPopFront(LTNode* phead);//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDatatype x);//删除pos位置数据
void LTErase(LTNode* pos);//销毁
void LTDesTroy(LTNode* phead);

List.c

#include"List.h"LTNode* buyNode(LTDatatype x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("NULL");exit(1);}node->data = x;node->next = node->prev = node;return node;
}//初始化
LTNode* LTInit()
{LTNode* phead = buyNode(-1);return phead;
}//打印
void LTPrint(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){printf("%d ->", pcur->data);pcur = pcur->next;}printf("\n");
}//bool类型判断
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->next == phead;
}//尾插
void LTPushBack(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = buyNode(x);//phead phead->prev newnodenewnode->prev = phead->prev;newnode->next = phead;phead->prev->next = newnode;phead->prev = newnode;
}//头插
void LTPushFront(LTNode* phead, LTDatatype x)
{assert(phead);LTNode* newnode = buyNode(x);newnode->next = phead->next;//phead->next为d1newnode->prev = phead;phead->next->prev = newnode;phead->next = newnode;
}//尾删
void LTPopBack(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->prev;//phead del->prev deldel->prev->next = phead;phead->prev = del->prev;free(del);del = NULL;
}//头删
void LTPopFront(LTNode* phead)
{assert(!LTEmpty(phead));LTNode* del = phead->next;//phead del del->nextdel->next->prev = phead;phead->next = del->next;free(del);del = NULL;
}//查找
LTNode* LTFind(LTNode* phead, LTDatatype x)
{LTNode* pcur = phead->next;while (pcur){if (pcur->data = x){return pcur;}}return NULL;
}//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDatatype x)
{assert(pos);LTNode* newnode = buyNode(x);//pos newnode pos->nextnewnode->next = pos->next;newnode->prev = pos;pos->next->prev = newnode;pos->next = newnode;
}//删除pos位置数据
void LTErase(LTNode* pos)
{assert(pos);//pos->prev pos pos->nextpos->prev->next = pos->next;pos->next->prev = pos->prev;free(pos);pos = NULL;
}//销毁
void LTDesTroy(LTNode* phead)
{LTNode* pcur = phead->next;while (pcur != phead){LTNode* next = pcur->next;free(pcur);pcur = next;}free(phead);phead = NULL;
}

Test.c

#include"List.h"void test()
{//LTNode* plist = NULL;//LTInit(&plist);//尾插LTNode* plist = LTInit();LTPushBack(plist, 1);LTPushBack(plist, 2);LTPushBack(plist, 3);LTPushBack(plist, 4);LTPrint(plist);//头插//LTNode* plist = LTInit();//LTPushFront(plist, 1);//LTPushFront(plist, 2);//LTPushFront(plist, 3);//LTPushFront(plist, 4);//LTPrint(plist);//尾删//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//LTPopBack(plist);//LTPrint(plist);//头删//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//LTPopFront(plist);//LTPrint(plist);//在pos位置之后插入数据//LTNode* find = LTFind(plist, 4);//if (find == NULL)//{//	printf("无\n");//}//else {//	printf("有\n");//}//LTInsert(find, 77);//LTErase(find);//LTPrint(plist);//销毁LTDesTroy(plist);plist = NULL;}int main()
{test();return 0;
}

---

总结

非常感谢大家阅读完这篇博客。希望这篇文章能够为您带来一些有价值的信息和启示。如果您有任何问题或建议，欢迎在评论区留言，我们一起交流学习。