数据结构 | 带头双向循环链表专题

数据结构 | 带头双向循环链表专题

前言

前面我们学了单链表，我们这次来看一个专题带头的双向循环链表~~

带头双向循环链表的结构

• 注意：这里的“带头”跟前面我们说的“头节点”是两个概念，实际前面的在单链表阶段称呼不严
  谨，但是为了同学们更好的理解就直接称为单链表的头节点。
• 带头链表里的头节点，实际为“哨兵位”，哨兵位节点不存储任何有效元素，只是站在这里“放哨
  的”

哨兵位存在的意义：

• 遍历循环链表避免死循环。

---

• 每个节点有三部分内容：
  • 保存数据的val
  • 保存下一个节点的地址next指针
  • 保存前一个节点的地址prev指针

实现双向链表

我们需要实现以下功能

头文件的定义

List.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>// 带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{LTDataType _val;struct ListNode* _next;struct ListNode* _prev;
}ListNode;//哨兵位初始化
ListNode* ListInit();// 创建返回链表的头结点.
ListNode* ListCreate(LTDataType* x);
// 双向链表销毁
void ListDestory(ListNode* pHead);
// 双向链表打印
void ListPrint(ListNode* pHead);
// 双向链表尾插
void ListPushBack(ListNode* pHead, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* pHead);
// 双向链表头插
void ListPushFront(ListNode* pHead, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* pHead);
// 双向链表查找
ListNode* ListFind(ListNode* pHead, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的节点
void ListErase(ListNode* pos);

---

创建节点

• malloc一个节点，然后让新节点的next和prev赋值为空，将值给了val，最后返回空间

ListNode* ListCreate(LTDataType* x)
{ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));if (newnode == NULL){perror("malloc fail!\n");exit(-1);}newnode->_val = x;newnode->_next = NULL;newnode->_prev = NULL;return newnode;
}

哨兵位初始化

• 这里我们初始化成-1代表是哨兵位，然后让前驱指针和next指针指向自己

ListNode* ListInit()
{ListNode* pHead = ListCreate(-1);pHead->_next = pHead;pHead->_prev = pHead;return pHead;
}

尾插

void ListPushBack(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* tail = pHead->_prev;ListNode* newnode = ListCreate(x);// phead   tail   newnodetail->_next = newnode;newnode->_prev = tail;newnode->_next = pHead;pHead->_prev = newnode;
}

尾删

void ListPopBack(ListNode* pHead)
{assert(pHead);assert(pHead->_next != pHead);ListNode* tail = pHead->_prev;ListNode* tailprev = tail->_prev;free(tail);tailprev->_next = pHead;pHead->_prev = tailprev;
}

头插

void ListPushFront(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur = pHead->_next;ListNode* newnode = ListCreate(x);pHead->_next = newnode;newnode->_prev = pHead;newnode->_next = cur;cur->_prev = newnode;
}

头删

void ListPopFront(ListNode* pHead)
{assert(pHead);assert(pHead->_next != pHead);ListNode* first = pHead->_next;ListNode* second = first->_next;pHead->_next = second;second->_prev = pHead;free(first);first = NULL;
}

打印

void ListPrint(ListNode* pHead)
{ListNode* tail = pHead->_next;printf("哨兵位->");while (tail != pHead){printf("%d->", tail->_val);tail = tail->_next;}printf("NULL\n");
}

查找

ListNode* ListFind(ListNode* pHead, LTDataType x)
{assert(pHead);ListNode* cur = pHead->_next;while (cur != pHead){if (cur->_val == x){return cur;}cur = cur->_next;}return NULL;
}

指定位置前插入

void ListInsert(ListNode* pos, LTDataType x)
{assert(pos);ListNode* newnode = ListCreate(x);ListNode* prev = pos->_prev;prev->_next = newnode;newnode->_prev = prev;pos->_prev = newnode;newnode->_next = pos;
}

删除指定位置

void ListErase(ListNode* pos)
{assert(pos);ListNode* prev = pos->_prev;ListNode* next = pos->_next;prev->_next = next;next->_prev = prev;free(pos);pos = NULL;
}

销毁链表

void ListDestory(ListNode* pHead)
{assert(pHead);ListNode* cur = pHead->_next;while (cur != pHead){ListNode* next = cur->_next;free(cur);cur = next;}free(pHead);pHead = NULL;
}

List.h

#pragma once#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>typedef int LTDataType;typedef struct ListNode {LTDataType val;struct ListNode* next;struct ListNode* prev;
}LTNode;//初始化哨兵位
LTNode* LTInit();
//创建节点
LTNode* LTcreate(LTDataType x);
//销毁
void LTDestroy(LTNode* phead);
//打印
void LTPrint(LTNode* phead);
//判断是否为空
bool LTEmpty(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//尾删
void LTPopBack(LTNode* phead);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//头删
void LTPopFront(LTNode* phead);
//指定位置插入
void LTInsert(LTNode* pos, LTDataType x);
//指定位置删除
LTNode* LTErase(LTNode* pos);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);

List.c

#define _CRT_SECURE_NO_WARNINGS 1#include"List.h"//初始化哨兵位
LTNode* LTInit()
{LTNode* phead = LTcreate(-1);phead->next = phead;phead->prev = phead;return phead;
}
//创建节点
LTNode* LTcreate(LTDataType x)
{LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));if (newnode == NULL){perror("malloc fail!\n");exit(-1);}newnode->next = NULL;newnode->prev = NULL;newnode->val = x;return newnode;
} //销毁
void LTDestroy(LTNode* phead);
//打印
void LTPrint(LTNode* phead)
{assert(phead);printf("哨兵位<->");LTNode* cur = phead->next;while (cur != phead){printf("%d<->", cur->val);cur = cur->next;}printf("\n");
}
//判断是否为空
bool LTEmpty(LTNode* phead)
{assert(phead);return phead->val == 0;
}//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTcreate(x);LTNode* tail = phead->prev;tail->next = newnode;newnode->prev = tail;newnode->next = phead;phead->prev = newnode;
}//尾删
void LTPopBack(LTNode* phead)
{assert(phead);LTNode* tail = phead->prev;LTNode* tailprev = tail->prev;free(tail);tail = NULL;tailprev->next = phead;phead->prev = tailprev;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTcreate(x);LTNode* cur = phead->next;phead->next = newnode;newnode->prev = phead;cur->prev = newnode;newnode->next = cur;
}
//头删
void LTPopFront(LTNode* phead)
{assert(phead);LTNode* first = phead->next;LTNode* second = first->next;free(first);phead->next = second;second->prev = phead;
}//查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{assert(phead);LTNode* cur = phead->next;while (cur != phead){if (cur->val == x){return cur;}cur = cur->next;}return NULL;
}//指定位置的前面插入
void LTInsert(LTNode* pos, LTDataType x)
{assert(pos);LTNode* newnode = LTcreate(x);LTNode* posprev = pos->prev;posprev->next = newnode;newnode->prev = posprev;newnode->next = pos;pos->prev = newnode;}
//指定位置删除
LTNode* LTErase(LTNode* pos)
{assert(pos);LTNode* posprev = pos->prev;LTNode* posnext = pos->next;free(pos);posprev->next = posnext;posprev = posprev;
}

• 顺序表和双向链表的分析

不同点	顺序表	链表（单链表）
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁

好了，双向链表就到这里结束了，有用的话点个赞吧~~