双向链表---C语言实现

【Linux】常用指令详解一（mkdir -p、mkdir、cd +[目录名]、pwd）-腾讯云开发者社区-腾讯云 作者：池央

文章介绍了Linux中常见指令的一些应用，是适合Linux初学者学习的一篇优质好文。

一、双向链表的介绍

上文我们实现了单链表，本文我们来实现带头双向循环链表，简称双向链表。带头双向循环中的带头指的是带头结点，也就是带哨兵位，双向链表中的哨兵位不存储任何有效数据，哨兵位后的第一个结点才是第一个有效节点；双向指的是既可以从前往后遍历链表，也可以从后往前遍历链表；循环指的是链表是头尾相连的。如图：

二、双向链表的实现

2.1定义双向链表节点的结构

双向链表的结点由三个部分组成，一个部分用来保存当前节点存储的数据，一个部分用来保存下一个结点的地址，即next指针，还有一个部分用来保存前一个节点的地址，即prev指针。有了next指针和prev指针，我们才能实现双向和循环。

typedef int LTDataType;

typedef struct ListNode

{

LTDataType data;//当前节点存储的数据

struct ListNode* next;//指向前一个节点的指针

struct ListNode* prev;//指向下一个节点的指针

}LTNode;

2.3双向链表的初始化

当单链表为空时，头指针指向为空，而当双向链表为空时，头指针指向头结点，所以创建双向链表需要初始化一个哨兵位。创建双向链表需要先初始化一个哨兵位，才能在链表中执行增删查改等操作。由于哨兵位不存储有效的值，所以我们初始化一个-1。

LTNode* LTInit()

{

//定义一个指针作为哨兵位，然后返回哨兵位结点

LTNode* phead = LTBuyNode(-1);//定义哨兵位

return phead;

}

2.4双向链表结点的申请

需要注意的是，初始化链表时调用了LTBuyNode函数，所以在对节点的next指针和prev指针赋值时，不能让next指针和prev指针指向为空，要让next指针和prev指针指向自己，因为如果指向为空的话，链表就不循环了。

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;

}

2.5双向链表的尾插

对于新插入的结点newnode，我们要让newnode的prev指针指向原来的尾结点d3，再让newnode的prev指针指向头结点。接下来我们要修改原来尾结点的next指针和头结点的prev指针。原来尾结点的next指针指向头结点，现在我们要让它指向newnode；哨兵位的prev指针原来指向d3，现在我们要让它指向newnode。需要注意的是，phead->prev->next = newnode和phead->prev = newnode不能交换位置。如果先执行phead->prev = newnode，那么在执行第二步phead->prev->next = newnode时就变成了newnode->next = newnode，这样就会出现问题。

void LTPushBack(LTNode* phead, LTDataType x)

{

assert(phead);

//哨兵位不能为空，如果哨兵位为空，说明这不是一个有效的双向链表

LTNode* newnode = LTBuyNode(x);

newnode->prev = phead->prev;

newnode->next = phead;

//这两行代码不能交换位置

phead->prev->next = newnode;

phead->prev = newnode;

}

2.6双向链表的头插

头插是指在哨兵位之后，第一个有效节点之前插入。对于头插，我们要使newnode的prev指针指向哨兵位，使newnode的next指针指向d1结点。还要修改哨兵位的next指针和d1结点的prev指针，让它们指向newnode。

void LTPushFront(LTNode* phead, LTDataType x)

{

assert(phead);

LTNode* newnode = LTBuyNode(x);

newnode->next = phead->next;

newnode->prev = phead;

//不能交换这两行代码

//若交换，就不能通过phead找到找到d1节点了

phead->next->prev = newnode;

phead->next = newnode;

}

2.8双向链表的头删

头删指的是删除第一个有效节点。对于头删，我们要使phead的next指针指向del的下一个结点，使del的下一个结点的prev指针指向哨兵位，再释放第一个有效节点。

void LTPopFront(LTNode* phead){

assert(phead);

assert(phead->next != phead);

LTNode* del = phead->next;

phead->next = del->next;

del->next->prev = phead;

free(del);

del = NULL;

}

2.9双向链表的查找

LTNode* LTFind(LTNode* phead, LTDataType x)

{

LTNode* pcur = phead->next;//从第一个有效节点开始遍历链表

while (pcur != phead)

{

if (pcur->data == x) {

return pcur;//找到要查找的结点就返回该节点

}

pcur = pcur->next;

}

return NULL;//找不到就返回空

}

2.10在pos位置之后插入数据

在指定位置之后插入数据，需要使newnode的prev指针指向pos，使newnode的next指针指向pos的下一个结点，再使pos的next指针和pos的下一个结点的prev指针指向newnode。

void LTInsert(LTNode* pos, LTDataType x)

{

assert(pos);

LTNode* newnode = LTBuyNode(x);

newnode->next = pos->next;

newnode->prev = pos;

pos->next->prev = newnode;

pos->next = newnode;

}

2.11删除pos节点

删除pos节点，需要把pos后一个结点的prev指针指向pos的前一个结点，把pos前一个结点的next指针指向pos的后一个节点，再释放pos结点。需要注意的是，函数的形参接受的是一级指针，形参的改变无法影响实参，也就是说，虽然我们在函数里把pos置为空了，但实参还没有置为空，因此，在调用完这个函数之后，还需要手动把实参置为空，否则实参就会成为一个野指针。

void LTErase(LTNode* pos)

{

assert(pos);

pos->next->prev = pos->prev;

pos->prev->next = pos->next;

free(pos);

pos = NULL;

}

2.12销毁链表

对于动态开辟的空间，我们需要执行销毁操作。链表的每个结点是动态开辟的，所以我们要销毁链表。函数的形参是一级指针，与删除pos节点相同，在调用完销毁链表这个函数之后，我们还需要手动把实参置为空。

void LTDesTroy(LTNode* phead)

{

//销毁链表，链表可以为空

assert(phead);

LTNode* pcur = phead->next;

while (pcur != phead)

{

LTNode* next = pcur->next;//定义一个指针保存下一个节点的地址

free(pcur);//释放当前节点

pcur = next;//pcur走到下一个结点

}

//出了循环之后，哨兵位还没有被销毁

free(phead);

phead = NULL;

}

邀请人：池央