数据结构——双链表

我宁愿靠自己的力量，打开我的前途，而不愿求有力者垂青 

文章目录

双线向链表各接口函数名或变量名 

双向链表接口实现源码

快速索引【头文件及函数声明】

双向链表接口实现

双向链表的构造分析

双向链表的定义及初始化

双向链表的插入和删除

往期回顾：

数据结构——单链表

数据结构——顺序表

  大家好，我是纪宁。

  这篇文章向大家介绍一种相对单链表性能更优的链表——双向链表，它能更高效的实现数据的插入、删除和查找等。

  文章前半段是双向链表对应名称和源码，文章后半段是对双向链表实现的具体解释。

双线向链表各接口函数名或变量名 

双向链表接口实现源码

快速索引【头文件及函数声明】

#include
#include
#include
typedef int LTDataType;//重命名typedef struct ListNode
{LTDataType Data;struct ListNode* next;struct ListNode* prev;
}LTNode;
LTNode* BuyLTNode(LTDataType x); //创建一个新节点
LTNode* LTInit(); //哨兵位的头结点
void LTPrint(LTNode*phead);//打印双链表
void LTPushBack(LTNode* phead, LTDataType x);//尾插
void LTPopBack(LTNode* phead);//尾删
void LTPushFront(LTNode* phead, LTDataType x);//头插
void LTPopFront(LTNode* phead);//头删
LTNode* LTFind(LTNode* phead, LTDataType x);//寻找结点
void LTInsert(LTNode*phead,LTNode* pos, LTDataType x); //在pos之前插入结点

双向链表接口实现

LTNode* BuyLTNode(LTDataType x)
{LTNode* nownode =(LTNode*)malloc(sizeof(LTNode));if (nownode == NULL){perror("malloc fail");}nownode->Data = x;nownode->next = NULL;nownode->prev = NULL;return nownode;
}LTNode* LTInit()
{LTNode* phead = BuyLTNode(0);phead->next = phead;phead->prev = phead;return phead;
}void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* tail = phead->prev;LTNode* nownode = BuyLTNode(x);nownode->next = phead;nownode->prev = tail;tail->next = nownode;phead->prev = nownode;
}void LTPrint(LTNode* phead)
{assert(phead);printf("phead<=>");LTNode* cur = phead;while (cur->next!=phead){printf("%d<=>", cur->next->Data);cur = cur->next;}printf("\n");
}void LTPopBack(LTNode* phead)
{assert(phead);assert(phead->next != phead);//只有哨兵位的时候不能删LTNode* tail = phead->prev;LTNode* tailPrev = tail->prev;tailPrev->next = tail->next;phead->prev = tailPrev;free(tail);
}
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* first = phead->next;LTNode* nownode = BuyLTNode(x);nownode->next = first;nownode->prev = phead;phead->next = nownode;first->prev = nownode;
}void LTPopFront(LTNode* phead)
{assert(phead);assert(phead->next != phead);//只有哨兵位的时候不能删除LTNode* first = phead->next;LTNode* second = first->next;phead->next = second;second->prev = phead;free(first);
}LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead;while (cur->next != phead){if (cur->next->Data == x)return  cur->next;cur = cur->next;}return NULL;
}void LTInsert(LTNode* phead, LTNode* pos, LTDataType x)
{assert(phead);assert(pos);LTNode* cur = phead;while (cur->next != pos){cur = cur->next;}LTNode*nownode = BuyLTNode(x);nownode->next = pos;nownode->prev = cur;cur->next = nownode;pos->prev = nownode;
}void LTErase(LTNode* phead, LTNode* pos)
{assert(pos&&phead);assert(pos->next != pos);assert(phead->next != phead);LTNode* cur = phead;LTNode* posNext = pos->next;while (cur->next != pos){cur = cur->next;}cur->next = posNext;posNext->prev = cur;free(pos);
}

双向链表的构造分析

  双向链表，相对于单链表不同的是双向链表的节点有两个指针域，一个指向后一个节点，另一个指向前一个节点，默认双向链表都是有带哨兵位的头节点，哨兵位的头节点中储存着第一个有效节点的地址（phead->next）和最后一个有效节点的地址（phead->prev）。

单双链表逻辑图对比

单双链表物理图对比

双向链表的定义及初始化

  双向链表中有一个数据域和两个指针域，一个指针指向下一个节点的地址，一个指针指向上一个节点的地址，将这个双链表的结构再重命名。

  双向链表在新开辟节点的时候，要先开辟一个节点大小的空间，将它的 next 和 NULL 指向空，然后将它的数据域值赋为 x。

双向链表的插入和删除

  双向链表的删除，首先要要明确的一点是不能删除哨兵位这个头节点，因为它是整个双向链表的结构支撑。删除的时候，要找到即将删除节点的上一个节点和下一个节点，将上一个节点的 next 指针指向下一个节点，将下一个节点的 prev 指针指向 上一个节点。最后，将删除的节点空间释放。

  双向链表的插入，在插入的时候，理论上在任何位置都是可以插入节点的。因为在初始化的时候，定义新创建节点的指针域都为空。所以在插入的时候，要改变插入节点的两个指针域，将它的next 指针指向下一个节点，将它的 prev 指针指向上一个节点。同样，将上一个节点的 next 指针指向这个新节点，将下一个指针的 prev 指针指向这个新节点。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！