双链表（数据结构）——C语言
目录
1 概念与结构
（注：这里面的“节点”和“结点”是同一个意思）
双链表，既有指向前一个节点的指针，也有指向后一个节点的指针，而且还是循环的，最后一个结点的后一个节点为头指针，头结点的前一个指针为最后一个结点，带头链表⾥的头结点，实际为“哨兵位”，哨兵位结点不存储任何有效元素，只是站在这⾥“放哨的”
注意：这⾥的“带头”跟前⾯单链表说的“头结点”是两个概念，单链表阶段称呼不严谨。
2 实现双向链表
创建三个文件，List.c,List.h,test.c,分别为实现函数的文件，头文件，测试文件
List.c
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int DataType;
typedef struct ListNode
{
DataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
LTNode* LTInit();
void LTDestory(LTNode* phead);
LTNode* BuyNode(DataType x);
LTNode* LTFind(LTNode* phead, DataType x);
bool LTEmpty(LTNode* phead);
void LTPrint(LTNode* phead);
void LTPushBack(LTNode* phead,DataType x);
void LTPushFront(LTNode* phead,DataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
void LTInsert(LTNode* pos, DataType x);
void LTErase(LTNode* pos);包括了结构体LTNode表示结点，这里有一个结构体自引用，用来找到下一个结点位置，以及实现的各种函数这里typedef的SLDataType，便于后续修改数据类型，这里以int类型为例。
申请节点BuyNode
LTNode* BuyNode(DataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = newnode->prev = newnode;
return newnode;
}申请节点，所以这里函数返回值为结构体指针LTNode，这里利用malloc函数，申请空间，将值赋给newnode->data，注意这里满足双链表循环的特点，所以下一个结点，和前一个结点这里不能置为空，都要指向自己。
判断双链表是否为空LTEmpty
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}这里判断结果返回bool类型，当头结点指向自己说明为空。
打印双链表LTPrint
void LTPrint(LTNode* phead)
{
assert(!LTEmpty(phead));
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}打印双链表中所有的data，这里和单链表一样，需要遍历链表，先定义一个指向有效节点的指针（即头结点的next），但是这里要注意循环截止的条件，根据循环双链表的特点，尾结点的next指向头结点，所以截止的条件当pcur==phead。
创建双链表LTInit()
LTNode* LTInit()
{
LTNode* node = BuyNode(-1);
return node;
}创建双链表即创建头结点(哨兵位)，调用申请节点的函数。
尾插LTPushBack
void LTPushBack(LTNode* phead,DataType x)
{
assert(phead);
LTNode* newnode = BuyNode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}
从尾部插入，双链表不用像单链表一样遍历去寻找尾结点，直接通过头结点的prev找到尾结点，在通过改变指针的指向完成插入，申请节点，先改变newnode的指针，newnode的prev指向尾结点（即head->prev），newnode的next指向头结点，再改变原来尾结点的next，指向newnode，最后改变head的prev为newnode，注意最后两步的代码位置不能交换。
头插LTPushFront
void LTPushFront(LTNode* phead, DataType x)
{
assert(phead);
LTNode* newnode =BuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
注意这里头插，不是在头结点之前插入（头结点之前插入这样的话，就是尾插），而是在头结点之后插入，先申请节点，再改指针指向，newnode的next指向head->next，newnode的prev则指向head，再改变原来第一个有效节点的prev，指向newnode，最后改变head的next指向newnode，同理这里注意最后两步的代码位置不能交换。
尾删LTPopBack
void LTPopBack(LTNode* phead)
{
assert(!LTEmpty(phead));
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}
断言链表是否为空，从尾部删除，可以先定义删除的结点del，增加代码的可读性，这里只需要改变新的尾结点的next（即del->prev->next）指向头结点，再改变头结点的prev指向新的尾结点（即phead->=del->prev），再将原来的尾结点释放掉即可。
头删LTPopFront
void LTPopFront(LTNode* phead)
{
assert(!LTEmpty(phead));
LTNode* del = phead->next;
del->next->prev = phead;
phead->next = del->next;
free(del);
del = NULL;
}
断言链表是否为空，这里和头插相同，删除的是头结点之后的结点，还是先定义del，改变新的第一个有效节点的prev指向头结点（即del->next->prev = phead），再改变头结点的next，指向新的第一个有效节点（即phead->next = del->next），最后释放删除的节点。
查找指定节点LTFind
LTNode* LTFind(LTNode* phead, DataType x)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}和单链表一样，先定义一个指向第一个有效节点的指针（即phead->next）要遍历双链表，依次对比pcur->data是否等于x，找到后直接返回pcur，这里还是注意循环截止的条件（pcur==phead），未找到返回NULL。
指定位置插入LTInsert
void LTInsert(LTNode* pos, DataType x)
{
assert(pos);
LTNode* newnode = BuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
断言pos为存在的位置，这里和尾插一样只是在pos的后面插入，的先找到pos的next节点，然后先改变newnode指针的指向，先改变newnode的next指向d2，即（pos->next），和newnode的prev指向pos，再改变原来pos->next结点prev的指向newnode（即pos->next->prev = newnode），最后改变pos->next指向新节点newnode。
指定位置删除LTErase
void LTErase(LTNode* pos)
{
assert(pos);
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos=NULL;
}
断言pos位置有效，这里删除只需要改变pos->next结点的指向，和pos->prev的指向，先改变pos->next结点的prev指向pos->prev,再改变pos->prev的next节点指向pos->next,最后将pos节点释放掉。
销毁双链表LTDestory
void LTDestory(LTNode* phead)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}先定义一个指向第一个有效节点的指针（即phead->next）要遍历双链表，这里销毁要向将pcur的next保存，再删除pcur以免丢失pcur结点（即无法找到pos->next），截止到pcur==phead，最后将头结点也释放掉。
3.整体代码
List.h
#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int DataType;
typedef struct ListNode
{
DataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
LTNode* LTInit();
void LTDestory(LTNode* phead);
LTNode* BuyNode(DataType x);
LTNode* LTFind(LTNode* phead, DataType x);
bool LTEmpty(LTNode* phead);
void LTPrint(LTNode* phead);
void LTPushBack(LTNode* phead,DataType x);
void LTPushFront(LTNode* phead,DataType x);
void LTPopBack(LTNode* phead);
void LTPopFront(LTNode* phead);
void LTInsert(LTNode* pos, DataType x);
void LTErase(LTNode* pos);List.c
#include"List.h"
LTNode* BuyNode(DataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->next = newnode->prev = newnode;
return newnode;
}
LTNode* LTFind(LTNode* phead, DataType x)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
bool LTEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
void LTPrint(LTNode* phead)
{
assert(!LTEmpty(phead));
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
LTNode* LTInit()
{
LTNode* node = BuyNode(-1);
return node;
}
void LTPushBack(LTNode* phead,DataType x)
{
assert(phead);
LTNode* newnode = BuyNode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}
void LTPushFront(LTNode* phead, DataType x)
{
assert(phead);
LTNode* newnode =BuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
void LTPopBack(LTNode* phead)
{
assert(!LTEmpty(phead));
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}
void LTPopFront(LTNode* phead)
{
assert(!LTEmpty(phead));
LTNode* del = phead->next;
del->next->prev = phead;
phead->next = del->next;
free(del);
del = NULL;
}
void LTInsert(LTNode* pos, DataType x)
{
assert(pos);
LTNode* newnode = BuyNode(x);
newnode->next = pos->next;
newnode->prev = pos;
pos->next->prev = newnode;
pos->next = newnode;
}
void LTErase(LTNode* pos)
{
assert(pos);
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
}
void LTDestory(LTNode* phead)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}原文地址：https://blog.csdn.net/2401_83456040/article/details/143080849
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！