目录
一、什么是带头双向循环链表
二、带头双向循环链表的实现
1、创建一个动态头结点
2、双向链表初始化
3、打印双向链表
4、双向链表尾插
5、双向链表尾删
6、双向链表头插
7、双向链表头删
8、双向链表查找
9、双向链表在pos的前面进行插入x
10、双向链表删除pos位置的结点
11、销毁链表
12、双向链表的长度
13、判空
三、源代码
1、DList.h
2、DList.c
3、test.c
四、顺序表和链表的优缺点
一、什么是带头双向循环链表
带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带 来很多优势，实现反而简单了。可以说是一种完美的链表，既可以向前也可以向后。
-
链表的声明
-
typedef
struct ListNode
-
{
-
struct ListNode* next;
-
struct ListNode* prev;
-
LTDataType data;
-
}LTNode;
二、带头双向循环链表的实现
1、创建一个动态头结点
首先先创建一个动态节点以便后面在插入时候的使用。
-
LTNode* BuyListNode(LTDataType x)
-
{
-
LTNode* node = (LTNode*)malloc(
sizeof(LTNode));
-
if (node == NULL)
-
{
-
perror(
"malloc fail");
-
exit(
-1);
-
}
-
node->data = x;
-
node->next = NULL;
-
node->prev = NULL;
-
return node;
-
}
2、双向链表初始化
带头双向循环链表是带有头节点的，所以开辟一个头节点，然后让这个头节点的前后指针域都指向自己，就实现了初始化。
-
LTNode* ListInit()
-
{
-
LTNode* phead = BuyListNode(
-1);
-
phead->next = phead;
-
phead->prev = phead;
-
return phead;
-
}
3、打印双向链表
这里需要另外一个指针cur去遍历一遍链表，当回到头节点的时候就结束。
-
void ListPrint(LTNode* phead)
-
{
-
assert(phead);
-
LTNode* cur = phead->next;
-
while (cur != phead)
-
{
-
printf(
"%d ", cur->data);
-
cur = cur->next;
-
}
-
printf(
"\n");
-
}
4、双向链表尾插
逻辑如下图，图只要画出来就比较清晰。
-
void ListPushBcak(LTNode* phead, LTDataType x)
-
{
-
assert(phead);
-
LTNode* newnode = BuyListNode(x);
-
LTNode* tail = phead->prev;
-
-
tail->next = newnode;
-
newnode->prev = tail;
-
newnode->next = phead;
-
phead->prev = newnode;
-
}
5、双向链表尾删
逻辑如下，根据下图就可以表示出尾删。
-
void ListPopBcak(LTNode* phead)
-
{
-
assert(phead);
-
LTNode* tail = phead->prev;
-
LTNode* tailPrev = tail->prev;
-
tailPrev->next = phead;
-
phead->prev = tailPrev;
-
free(tail);
-
}
6、双向链表头插
逻辑如下，根据下图就可以表示出头插。
-
void ListPushFront(LTNode* phead, LTDataType x)
-
{
-
assert(phead);
-
LTNode* newnode = BuyListNode(x);
-
LTNode* first = phead->next;
-
//phead newnode first
-
//顺序无关
-
phead->next = newnode;
-
newnode->prev = phead;
-
newnode->next = first;
-
first->prev = newnode;
-
}
7、双向链表头删
逻辑如下：
-
void ListPopFront(LTNode* phead)
-
{
-
assert(phead);
-
assert(phead->next != phead);
//是否为空
-
LTNode* first = phead->next;
-
LTNode* second = first->next;
-
free(first);
-
phead->next = second;
-
second->prev = phead;
-
}
8、双向链表查找
从链表的头结点的后面结点开始逐一匹配，直到找到值相同的结点进行返回，若当查找结点一直后到头结点时意味着没有该结点，就返回NULL。
-
LTNode* ListFind(LTNode* phead, LTDataType x)
-
{
-
assert(phead);
-
LTNode* cur = phead->next;
-
while (cur != phead)
-
{
-
if (cur->data == x)
-
{
-
return cur;
-
}
-
cur = cur->next;
-
}
-
return NULL;
-
}
9、双向链表在pos的前面进行插入x
逻辑如下图：
-
void ListInsert(LTNode* pos, LTDataType x)
-
{
-
assert(pos);
-
LTNode* prev = pos->prev;
-
LTNode* newnode = BuyListNode(x);
-
//prev newnode pos
-
prev->next = newnode;
-
newnode->prev = prev;
-
newnode->next = pos;
-
pos->prev = newnode;
-
}
10、双向链表删除pos位置的结点
逻辑如下图：
-
void ListErase(LTNode* pos)
-
{
-
assert(pos);
-
LTNode* prev = pos->prev;
-
LTNode* next = pos->next;
-
free(pos);
-
prev->next = next;
-
next->prev = prev;
-
}
11、销毁链表
双向链表和单链表一样，逐个遍历，逐个销毁。
-
void ListDestory(LTNode* phead)
-
{
-
assert(phead);
-
LTNode* cur = phead->next;
-
while (cur != phead)
-
{
-
LTNode* next = cur->next;
-
free(cur);
-
cur = next;
-
}
-
free(phead);
-
}
12、双向链表的长度
-
size_t ListSize(LTNode* phead)
-
{
-
assert(phead);
-
size_t size =
0;
-
LTNode* cur = phead->next;
-
while (cur != phead)
-
{
-
++size;
-
cur = cur->next;
-
}
-
return size;
-
}
13、判空
-
bool ListEmpty(LTNode* phead)
-
{
-
assert(phead);
-
return phead->next == phead;
-
}
三、源代码
1、DList.h
-
#pragma once
-
-
#include <stdio.h>
-
#include <assert.h>
-
#include <stdlib.h>
-
#include <stdbool.h>
-
-
typedef
int LTDataType;
-
typedef
struct ListNode
-
{
-
struct ListNode* next;
-
struct ListNode* prev;
-
LTDataType data;
-
}LTNode;
-
-
-
//创建一个动态头结点
-
LTNode* BuyListNode(LTDataType x);
-
//初始化
-
LTNode* ListInit();
-
-
//打印链表
-
void ListPrint(LTNode* phead);
-
-
//双向链表尾插
-
void ListPushBcak(LTNode* phead, LTDataType x);
-
//双向链表尾删
-
void ListPopBcak(LTNode* phead);
-
-
//双向链表头插
-
void ListPushFront(LTNode* phead, LTDataType x);
-
//双向链表头删
-
void ListPopFront(LTNode* phead);
-
-
//双向链表查找
-
LTNode* ListFind(LTNode* phead, LTDataType x);
-
-
//双向链表在pos的前面进行插入
-
void ListInsert(LTNode* pos, LTDataType x);
-
//双向链表删除pos位置的结点
-
void ListErase(LTNode* pos);
-
-
//判空
-
bool ListEmpty(LTNode* phead);
-
-
size_t ListSize(LTNode* phead);
-
-
//销毁链表
-
void ListDestory(LTNode* phead);
2、DList.c
-
#include "DList.h"
-
-
//创建一个动态头结点
-
LTNode* BuyListNode(LTDataType x)
-
{
-
LTNode* node = (LTNode*)malloc(
sizeof(LTNode));
-
if (node == NULL)
-
{
-
perror(
"malloc fail");
-
exit(
-1);
-
}
-
node->data = x;
-
node->next = NULL;
-
node->prev = NULL;
-
return node;
-
}
-
//初始化
-
LTNode* ListInit()
-
{
-
LTNode* phead = BuyListNode(
-1);
-
phead->next = phead;
-
phead->prev = phead;
-
return phead;
-
}
-
-
//打印链表
-
void ListPrint(LTNode* phead)
-
{
-
assert(phead);
-
LTNode* cur = phead->next;
-
while (cur != phead)
-
{
-
printf(
"%d ", cur->data);
-
cur = cur->next;
-
}
-
printf(
"\n");
-
}
-
//双向链表尾插
-
void ListPushBcak(LTNode* phead, LTDataType x)
-
{
-
assert(phead);
-
LTNode* newnode = BuyListNode(x);
-
LTNode* tail = phead->prev;
-
-
tail->next = newnode;
-
newnode->prev = tail;
-
newnode->next = phead;
-
phead->prev = newnode;
-
}
-
//双向链表尾删
-
void ListPopBcak(LTNode* phead)
-
{
-
assert(phead);
-
LTNode* tail = phead->prev;
-
LTNode* tailPrev = tail->prev;
-
tailPrev->next = phead;
-
phead->prev = tailPrev;
-
free(tail);
-
}
-
-
//双向链表头插
-
void ListPushFront(LTNode* phead, LTDataType x)
-
{
-
assert(phead);
-
-
LTNode* newnode = BuyListNode(x);
-
LTNode* first = phead->next;
-
//phead newnode first
-
//顺序无关
-
phead->next = newnode;
-
newnode->prev = phead;
-
newnode->next = first;
-
first->prev = newnode;
-
}
-
//双向链表头删
-
void ListPopFront(LTNode* phead)
-
{
-
assert(phead);
-
assert(phead->next != phead);
//是否为空
-
LTNode* first = phead->next;
-
LTNode* second = first->next;
-
free(first);
-
phead->next = second;
-
second->prev = phead;
-
}
-
-
//双向链表查找
-
LTNode* ListFind(LTNode* phead, LTDataType x)
-
{
-
assert(phead);
-
LTNode* cur = phead->next;
-
while (cur != phead)
-
{
-
if (cur->data == x)
-
{
-
return cur;
-
}
-
cur = cur->next;
-
}
-
return NULL;
-
}
-
-
//双向链表在pos的前面进行插入x
-
void ListInsert(LTNode* pos, LTDataType x)
-
{
-
assert(pos);
-
LTNode* prev = pos->prev;
-
LTNode* newnode = BuyListNode(x);
-
//prev newnode pos
-
prev->next = newnode;
-
newnode->prev = prev;
-
newnode->next = pos;
-
pos->prev = newnode;
-
}
-
-
//双向链表删除pos位置的结点
-
void ListErase(LTNode* pos)
-
{
-
assert(pos);
-
LTNode* prev = pos->prev;
-
LTNode* next = pos->next;
-
free(pos);
-
prev->next = next;
-
next->prev = prev;
-
}
-
-
//判空
-
bool ListEmpty(LTNode* phead)
-
{
-
assert(phead);
-
return phead->next == phead;
-
}
-
-
size_t ListSize(LTNode* phead)
-
{
-
assert(phead);
-
size_t size =
0;
-
LTNode* cur = phead->next;
-
while (cur != phead)
-
{
-
++size;
-
cur = cur->next;
-
}
-
return size;
-
}
-
-
//销毁链表
-
void ListDestory(LTNode* phead)
-
{
-
assert(phead);
-
LTNode* cur = phead->next;
-
while (cur != phead)
-
{
-
LTNode* next = cur->next;
-
free(cur);
-
cur = next;
-
}
-
free(phead);
-
}
3、test.c
-
void TestList1()
-
{
-
LTNode* phead = ListInit();
-
ListPushBcak(phead,
1);
-
ListPushBcak(phead,
2);
-
ListPushBcak(phead,
3);
-
ListPushBcak(phead,
4);
-
ListPushBcak(phead,
5);
-
ListPrint(phead);
-
-
ListPopBcak(phead);
-
ListPrint(phead);
-
ListPopBcak(phead);
-
ListPrint(phead);
-
-
ListPushFront(phead,
10);
-
ListPushFront(phead,
20);
-
ListPushFront(phead,
30);
-
ListPrint(phead);
-
-
ListPopFront(phead);
-
ListPrint(phead);
-
LTNode* pos = ListFind(phead,
2);
-
if (pos)
-
{
-
pos->data *=
100;
-
}
-
ListPrint(phead);
-
ListDestory(phead);
-
phead = NULL;
-
}
-
int main()
-
{
-
TestList1();
-
return
0;
-
}
四、顺序表和链表的优缺点
1、顺序表优点：尾插，尾删方便，下标的随机访问快。缓存利用率高。
2、顺序表缺点：空间不足时需要扩容（扩容要付出相应代价），插入删除数据需要挪动数据。
3、链表优点：插入删除方便，按需申请释放小块结点内存。
4、链表缺点：不能随机访问下标。缓存利用率低。
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定连续 |
| 随机访问 | 支持O(1) | 不支持：O(N) |
| 任意位置插入或者删除 元素 | 可能需要搬移元素，效率低 O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
本文要是有不足的地方，欢迎大家在下面评论，我会在第一时间更正。
老铁们，记着点赞加关注哦!!!
转载：https://blog.csdn.net/m0_63198468/article/details/128526548
查看评论