文章目录链表分类双向链表概念结构申请结点创建头节点尾插、头插尾插头插尾删、头删尾删头删指定位置插入、删除结点指定位置插入结点指定位置删除结点查找结点链表打印双链表销毁双链表实现
链表分类链表总共有八种结构如下。 在众多链表结构中，实际中最常用的有这两种结构：单链表和双向带头循环链表(即双链表)。
无头单向非循环链表：结构简单，⼀般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。带头双向循环链表：结构最复杂，⼀般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势。(并且掌握如上两种数据结构的实现，其他种类的链表也能够实现)双向链表概念 这里的head充当什么作用呢？带头链表里的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这里"放哨的"。
结构根据双链表概念，定义结构两个指针分别指向下一个结点和前一个结点的地址，并且每一个结点都能存储数据data。
申请结点
创建头节点根据概念创建一个头结点起到"放哨"的作用，这个结点可随意给值。 为什么用一级指针接收呢？保证哨兵位节点不能被删除(若被删除则不是双链表)，节点的地址也不能发生改变，因此传一级最合适。
尾插、头插尾插首先，通过函数创建一个新节点，并将其数据域设置为输入的值x，得到新节点的指newnode。
设置新结点的指针以插入到尾部。由于这是一个循环链表，尾节点的next指向头节点，所以将新节点newnode的prev指针指向前一个结点。
更新原链表尾节点的指针，使其next指针指向新节点newnode，这样新节点就被正确地链接到链表的末尾。
最后，调整原头节点phead的prev指针，使其指向新节点newnode，确保链表的循环特性仍然保持，即尾节点的next始终指向头节点。
头插头插与尾插的方法类似。
尾删、头删尾删保证双链表有效(即至少有一个哨兵位)。定义结点del保存尾结点，让尾结点的前一个结点的next指向头结点。头结点指向del的前一个结点。释放尾结点del。头删头删与尾删的方法类似。
指定位置插入、删除结点指定位置插入结点指向结点是否有效，若无效则断言。创建新结点，newnode的next指向未更新链表指定位置的下一个结点；newnode的prev指向指定结点。未更新链表指定位置的下一个结点指向newnode结点；指定结点指向newnode结点。指定位置删除结点删除指定结点，想要形参的改变影响到实参，那么传二级指针不是更好吗？ 事实的确如此，那么我们为什么在这里是传一级指针呢？ 目的是为了保证接口一致性。可以发现，我们前面函数的实现大部分都是通过传一级指针实现双链表功能，如果这里突然传二级指针会造成疑惑。 需要注意的是：删除指定结点后，由于形参不能改变实参，因此需要我们手动置指定结点为NULL。
查找结点和单链表一样，我们只需要遍历原链表查找结点，若没找到则返回NULL。
链表打印
双链表销毁定义pcur指向头结点的下一个结点，并遍历双链表。每次释放pcur结点，并让pcur指向下一个结点，直到pcur与头结点phead相遇为止。为了保证接口的一致性，这里同样采用传一级指针，需要手动置双链表的头结点为NULL。双链表实现List.h
#define _CRT_SECURE_NO_WARNINGS 1
#pragma once
#include
#include
#include
typedef int LTDataType;
//定义双向链表节点的结构
typedef struct ListNode
{
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
//声明双向链表中提供的方法
//初始化
//void LTInit(LTNode** phead);
LTNode* LTInit();
//打印双链表
void LTPrint(LTNode* phead);
//哨兵位节点不能被删除，节点的地址也不能发生改变，因此传一级最合适
//尾插
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);
//查找节点
LTNode* LTFind(LTNode* phead, LTDataType x);
//销毁节点
void LTDesTroy(LTNode* phead);
List.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
//申请节点
LTNode* LTBuyNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
perror("malloc fail!");
exit(1);
}
//申请成功
node->data = x;
node->next = node->prev = node;
return node;
}
//初始化
LTNode* LTInit()
{
//创建头结点
//LTNode* phead = (LTNode*)malloc(sizeof(LTNode));
//phead->data = -1;
//phead->next = phead->prev = phead;
//给双向链表创建一个哨兵位
LTNode *phead = LTBuyNode(-1);
}
//打印双链表
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
//phead newnode phead->prev
newnode->prev = phead->prev;
newnode->next = phead;
phead->prev->next = newnode;
phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
//phead newnode prev->next
newnode->prev = phead;
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
}
//尾删
void LTPopBack(LTNode* phead)
{
//链表必须有效且链表不能为空(只有一个哨兵位)
assert(phead && phead->next != phead);
//phead phead->prev->prev phead->prev
//phead del->prev del 让del=phead->prev
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
//释放del节点
free(del);
del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
assert(phead && phead->next != phead);
//phead phead->next phead->next->next
//phead del del->next 让del=phead->next
LTNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
//释放del节点
free(del);
del = NULL;
}
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
//pos newnode pos->next
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
//删除pos节点
void LTErase(LTNode* pos)//二级指针更好
{
assert(pos);
//pos->prev pos pos->next
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}
//查找节点
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
//没有找到
return NULL;
}
//销毁节点
void LTDesTroy(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
//此时pcur指向phead,而phead未被销毁
free(phead);
phead = NULL;
}
test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include"List.h"
void ListTest()
{
//LTNode* plist = NULL;
//LTInit(&plist);
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushFront(plist, 4);
LTPrint(plist);
LTPopBack(plist);
LTPrint(plist);
LTNode* find = LTFind(plist, 1);
//if (find == NULL)
//{
// printf("没有找到\n");
//}
//else {
// printf("找到了\n");
//}
LTInsert(find, 4);
LTPrint(plist);
LTErase(find);
//不传二级(保持接口一致性)
find = NULL;
LTPrint(plist);
LTDesTroy(plist);
plist = NULL;
}
int main()
{
ListTest();
return 0;
}