在之前我们已经讲过< 单链表 >了,单链表查找上一个结点的时间复杂度为O（n），尾插时也要遍历一次链表也是O（n），因为我们每次都要从头开始遍历找,为了克服这单向性的缺点，我们就有了双向链表.
如果要提高链表的查找，尾插等效率，那双向链表（双链表）无疑是首选。
双向链表的概念及结构
双向链表是一种常用的数据结构，它允许我们在O(1)时间内对链表的头尾进行元素的添加和删除操作，同时也支持双向遍历。
双向链表是在单链表的每个结点中，再设置一个指向其前驱结点的指针域，所以在双向链表中的结点都有两个指针域，一个指向直接后继，另一个指向直接前驱。
双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。
双向链表的结构：双向链表的每个节点包含了三个基本元素，分别是元素值、指向前一个节点的指针和指向下一个节点的指针。
- 双向链表存储结构
struct SListNode
{
int data; //节点存储数据
struct SListNode* next; //指向前驱节点
struct SListNode* prev; //指向后驱节点
};
- 注意:
双向链表头指针是一个虚拟头节点，不存储任何有效数据，他的前驱节点与后驱节点都是指向自己的，头指针节点相当于是一个削兵。用来站岗的。方便链接前后指针.文章来源：https://www.toymoban.com/news/detail-475279.html
双向链表接口的实现
申请节点空间
- 链表添加一个节点数据时候，每次都要写一段代码，这样做是不是太繁琐了，我们可以封装一个函数来解决问题，每次添加一个节点时，将结点存放的数据置为需要存放的值，在将结构体存放节点的地址置为NULL, 需要增加节点时调用一下改函数即可。
//申请节点空间
LTNode* BuyList(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL) //判断是否申请成功
{
perror("malloc fail");
}
else //申请成功
{
newnode->data = x; //将结点存放的数据置为需要存放的值
newnode->next = NULL; //节点的地址置为NULL
newnode->prev = NULL; //节点的地址置为NULL
return newnode;
}
}
双向链表的初始化
- 其实在双向链表操作中，我们只需要一级指针接收就能修改链表的指向了，但在初始化时候我们要修改头节点指针，需要二级指针来接收修改头节点，为了后面统一用一级指针，所以我们在初始化时候不传参，直接申请一个节点，然后返回，该指点的前驱指针与后驱指针都是指向自己。节点数据不存储有效数据
LTNode* LTInit()
{
LTNode* phead = BuyLTNode(-11111);//节点数据不存储有效数据
//前驱指针与后驱指针都是指向自己
phead->next = phead;
phead->prev = phead;
return phead; //返回该节点
}
双向链表打印数据
- 双向链表是通过结构体存储的头指针下一个指针开始遍历链表的，当遍历的指针指向头指针则遍历完毕。
void LTPrint(LTNode* phead)
{
assert(phead); //断言：判断是否为空
printf("guard<==>");
LTNode* cur = phead->next; //从头指针的next开始遍历
while (cur != phead)
{
printf("%d<==>", cur->data); // 打印数据
cur = cur->next; //迭代指向下一个
}
printf("\n");
}
双向链表是否为空
- 如果phead->next为自己，则链表为空，返回真，反之返回假.
bool LTEmpty(LTNode* phead)
{
assert(phead); //断言 判断是否为空指针
return phead->next == phead;
}
双向链表尾插
- 双向链表尾插步骤
- 创建一个新节点 ,将新节点的数据填充为要插入的数据。
- 使用phead->prev找到当前双向链表的尾节点tail。
- 将tail节点的next指针指向新的待插入节点newnode
- 将待插入节点newnode的prev指针指向原尾节点tail
- 将待插入节点newnode的next指针指向链表的头节点phead。
- 将链表头节点phead的prev指针指向插入的新节点newnode。
// 双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead); //断言：判断是否为空
LTNode* tail = phead->prev; //使用phead->prev找到当前双向链表的尾节点tail。
LTNode* newnode = BuyLTNode(x); //创建一个新节点
tail->next = newnode; //将tail节点的next指针指向新的待插入节点newnode
newnode->prev = tail; //将待插入节点newnode的prev指针指向原尾节点tail
newnode->next = phead; //将待插入节点newnode的next指针指向链表的头节点phead。
phead->prev = newnode; //将链表头节点phead的prev指针指向插入的新节点newnode。
}
双向链表头插
- 双向链表头插步骤
- 创建一个新节点 ,将新节点的数据填充为要插入的数据。
- 使用phead->next找到当前双向链表的头节点，用first保存.
- 将链表头节点phead的next指针指向新插入的节点newnode
- 将待插入节点newnode的prev指针指向链表的头节点phead。
- 将待插入节点newnode的next指针指向原头节点first。
- 将原头节点first的prev指针指向插入的新节点newnode。
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead); //断言 判断是否为空
LTNode* newnode = BuyLTNode(x); //创建一个新节点 ,将新节点的数据填充为要插入的数据
LTNode* first = phead->next; //使用phead->next找到当前双向链表的头节点
phead->next = newnode; //将链表头节点phead的next指针指向新插入的节点newnode
newnode->prev = phead; //将待插入节点newnode的prev指针指向链表的头节点phead。
newnode->next = first; //将待插入节点newnode的next指针指向原头节点first。
first->prev = newnode; //将原头节点first的prev指针指向插入的新节点newnode。
}
双向链表尾删
- 双向链表尾删步骤
- 判断链表是否为空，如果为空，则无法进行删除操作
- 使用phead->prev找到当前双向链表的尾节点.(用一个临时变量tail来记录)
- 使用tail->prev找到当前尾节点的前一个节点。(用一个临时变量tailPrev来记录)
- 释放尾节点tail的内存空间
- 将tailPrev的next指针指向链表头节点phead。
- 将链表头节点phead的prev指向tailPrev
void LTPopBack(LTNode* phead)
{
assert(phead); //判断头指针是否为空
assert(!LTEmpty(phead)); //断言：判断链表是否为空，如果为空，则无法进行删除操作
LTNode* tail = phead->prev; //使用phead->prev找到当前双向链表的尾节点.
LTNode* tailPrev = tail->prev; //使用tail->prev找到当前尾节点的前一个节点
free(tail); //释放尾节点tail的内存空间
tailPrev->next = phead; //将tailPrev的next指针指向链表头节点phead
phead->prev = tailPrev; //将链表头节点phead的prev指向tailPrev
}
双向链表头删
- 双向链表头删步骤
- 判断链表是否为空，如果为空，则无法进行删除操作
- 使用phead->next找到当前双向链表的头节点下一个。(用一个临时变量first来记录)
- 使用first->next找到当前头节点的下一个节点(用一个临时变量second来记录)
- 将链表头节点phead的next指针指向second节点。
- 将second节点的prev指针指向链表头节点phead。
- 释放头节点first的内存空间,进行头删.
void LTPopFront(LTNode* phead)
{
assert(phead); 判断头指针是否为空
assert(!LTEmpty(phead)); 断言：判断链表是否为空，如果为空，则无法进行删除操作
LTNode* first = phead->next; //使用phead->next找到当前双向链表的头节点的下一个
LTNode* second = first->next; //使用first->next找到当前头节点的下一个节点
phead->next = second; //将链表头节点phead的next指针指向second节点
second->prev = phead; //将second节点的prev指针指向链表头节点phead
free(first); //进行头删
}
双向链表的查找
- 获得链表某个节点的数据思路也较简单
- 从头节点的下一个节点开始，依次遍历链表中的每个节点。
- 在每个节点的数据域中查找节点的值是否为x，如果是则返回该节点的指针
- 如果遍历完整个链表都没有找到节点的值为x，则返回NULL。
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead); ///判断头指针是否为空
LTNode* cur = phead->next; //从头节点的下一个节点开始，依次遍历链表中的每个节点。
while (cur != phead)
{
if (cur->data == x) //在每个节点的数据域中查找节点的值是否为x，如果是则返回该节点的指针
{
return cur;
}
cur = cur->next; //迭代 指向下一个
}
return NULL; //如果遍历完整个链表都没有找到节点的值为x，则返回NULL。
}
双向链表在指定位置前插入数据
- 双向链表插入数据不用像单链表一样从头查找，双向链表只需原地动数据就可。具体步骤如下：
- 获取pos节点的前一个节点(使用一个临时变量tmp来保存)
- 创建一个新的待插入节点newnode
- 将tmp节点的next指向待插入节点newnode
- 将待插入节点newnode的prev指针指向tmp节点
- 将待插入节点newnode的next指针指向pos节点
- 将pos节点的prev指针指向待插入节点newnode
// 在pos之前插入
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);//节点pos不为空
LTNode* tmp = pos->prev; //获取pos节点的前一个节点
LTNode* newnode = BuyLTNode(x); //创建一个新的待插入节点newnode
tmp->next = newnode; //将tmp节点的next指向待插入节点newnode
newnode->prev = tmp; //将待插入节点newnode的prev指针指向tmp节点
newnode->next = pos; //将待插入节点newnode的next指针指向pos节点
pos->prev = newnode; //将pos节点的prev指针指向待插入节点newnode
}
双向链表删除指定位置的值
- 删除指定位置的具体逻辑步骤
- 获取pos节点的前一个节点和后一个节点。（用posprev和posnext临时变量来记录）
- 将posPrev节点的next指向posNext节点
- 将posNext节点的prev指向posPrev节点
- 释放要删除的节点pos的内存空间。
void LTErase(LTNode* pos)
{
assert(pos); //节点pos不为空
//获取pos节点的前一个节点和后一个节点
LTNode* posPrev = pos->prev;
LTNode* posNext = pos->next;
posPrev->next = posNext; //将posPrev节点的next指向posNext节点
posNext->prev = posPrev; //将posNext节点的prev指向posPrev节点
free(pos); //释放要删除的节点pos的内存空间。
}
双向链表的销毁
- 当我们不打算使用这个单链表时，我们需要把它销毁，其实也就是在内存中将它释放掉，以便于留出空间给其他程序或软件使用。释放内存具体步骤如下:
- 使用一个指针变量遍历整个链表在循环中，对于当前遍历到的节点，将其保留下一个节点的指针，以便于在释放当前指针后，指向的节点时能够顺利找到下一个节点.
- 先从头指针的下一个节点开始释放，最后在释放头指针.
void LTDestroy(LTNode* phead)
{
assert(phead); //断言:头指针不能为空
LTNode* cur = phead->next;//先指向有效位置头指针的下一个节点
while (cur != phead)
{
LTNode* next = cur->next; //保存下一个指针
free(cur); //释放cur节点占用的内存空间，
cur = next; //迭代
}
free(phead); //释放头指针
}
总结
- 双向链表相对于单向链表的优点在于它可以支持双向遍历，即从链表头或尾部开始遍历，因此它可以在某些情况下更加高效。同时，双向链表也支持在任意位置进行链表节点的插入和删除操作，这是单向链表不支持的。因此，双向链表更加灵活，可以满足更多场景下的需求。
- 相对于单链表，双向链表的节点需要额外存储一个指针，即指向前面节点的指针，因此相对于单链表会占用更多的内存空间。
总之，双向链表是一种值得掌握的重要数据结构，掌握了它的基本操作和应用场景，可以大大提高算法和数据结构等领域的编程水平。文章来源地址https://www.toymoban.com/news/detail-475279.html
到了这里，关于【数据结构】从头到尾全解析双向链表的文章就介绍完了。如果您还想了解更多内容，请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章，希望大家以后多多支持TOY模板网！
