数据结构3——双向链表
在上篇文章数据结构2——单链表中，我们了解了什么是链表，以及单链表的实现，接着上篇文章，本篇文章介绍一下比单链表更常用的链表——双向循环链表。
目录
1.双向链表的实现
1.1节点
单链表的节点存的有数据域和一个指向下一个节点后继指针，因此单链表只能单向遍历。
要想实现双向遍历，就需要在节点里增加一个指向前一个节点的前驱指针。
typedef int DLTDataType;
typedef struct DListNode
{
DLTDataType data;
struct DListNode* prev;//前继指针
struct DListNode* next;//后继指针
}DLTNode;
1.2 初始化节点
//初始化节点函数实现
DLTNode* DLTInit()
{
DLTNode* phead = BuyDLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}1.3 动态开辟新节点
//开辟新节点函数实现
DLTNode* BuyDLTNode(DLTDataType x)
{
DLTNode* node = (DLTNode*)malloc(sizeof(DLTNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->data = x;
node->next = NULL;
node->prev = NULL;
return node;
}
1.4 遍历链表
void DLTPrint(DLTNode* phead)
{
assert(phead);
printf("phead <-> ");
DLTNode* cur = phead->next;
while (cur != phead)
{
printf("%d <-> ", cur->data);
cur = cur->next;
}
printf("\n");
}1.5 查找
//查找
DLTNode* DLTFind(DLTNode* phead, DLTDataType x)
{
assert(phead);
DLTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
1.6 插入
1.尾插
//尾插函数实现
void DLTPushBack(DLTNode* phead, DLTDataType x)
{
assert(phead);
//①常规写法
DLTNode* tail = phead->prev;
DLTNode* newnode = BuyDLTNode(x);
newnode->prev = tail;
tail->next = newnode;
newnode->next = phead;
phead->prev = newnode;
//②复用 DLTInsert
//DLTInsert(phead, x);
}2. 头插
//头插函数实现
void DLTPushFront(DLTNode* phead, DLTDataType x)
{
assert(phead);
//①常规写法
DLTNode* newnode = BuyDLTNode(x);
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
//②复用DLTInsert
//DLTInsert(phead->next, x);
}3.在pos之前插入
//在pos之前插入
void DLTInsert(DLTNode* pos, DLTDataType x)
{
assert(pos);
DLTNode* posPrev = pos->prev;
DLTNode* newnode = BuyDLTNode(x);
posPrev->next = newnode;
newnode->prev = posPrev;
newnode->next = pos;
pos->prev = newnode;
}1.7 删除
1. 尾删
//尾删函数实现
void DLTPopBack(DLTNode* phead)
{
assert(phead);
assert(phead->next != phead);//检查链表是否为空
//①常规写法
DLTNode* tail = phead->prev;
DLTNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;
//②复用DLTErase
//DLTErase(phead->prev);
}2. 头删
//头删函数实现
void DLTPopFront(DLTNode* phead)
{
assert(phead);
assert(phead->next != phead);
//①常规写法
DLTNode* first = phead->next;
DLTNode* second = first->next;
free(first);
phead->next = second;
second->prev = phead;
//②复用DLTErase
//DLTErase(phead->next);
}3.删除pos位置
//删除pos位置
void DLTErase(DLTNode* pos)
{
assert(pos);
DLTNode* posPrev = pos->prev;
DLTNode* posNext = pos->next;
free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}1.8 其他函数
1. 链表长度
//链表长度
int DLTSize(DLTNode* phead)
{
assert(phead);
int size = 0;
DLTNode* cur = phead->next;
while (cur != phead)
{
++size;
cur = cur->next;
}
return size;
}2. 销毁链表
//销毁函数
void DLTDestory(DLTNode* phead)
{
assert(phead);
DLTNode* cur = phead->next;
while (cur != phead)
{
DLTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}1.9 测试
int main()
{
DLTNode* plist = DLTInit();
DLTPushBack(plist, 1);
DLTPushBack(plist, 2);
DLTPushBack(plist, 3);
DLTPushBack(plist, 4);
DLTPushBack(plist, 5);
DLTPrint(plist);
DLTPushFront(plist, 10);
DLTPushFront(plist, 11);
DLTPushFront(plist, 12);
DLTPrint(plist);
DLTDestory(plist);
plist = NULL;
return 0;
}
2.顺序表和链表的比较
| 不同点 | 顺序表 | 链表 |
| 存储空间上 | 物理上一定连续 | 逻辑上连续，但物理上不一定 连续 |
| 随机访问 | 支持O(1) | 不支持O(N) |
| 任意位置插入或者删除元素 | 可能需要搬移元素，效率低 O(N) | 只需修改指针指向 |
| 插入 | 动态顺序表，空间不够时需要 扩容 | 没有容量的概念 |
| 应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
| 缓存利用率 | 高 | 低 |
*源代码
DLish.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int DLTDataType;
typedef struct DListNode
{
DLTDataType data;
struct DListNode* prev;//前继指针
struct DListNode* next;//后继指针
}DLTNode;
//开辟新节点函数声明
DLTNode* BuyDLTNode(DLTDataType x);
//初始化节点函数声明
DLTNode* DLTInit();
//遍历函数声明
void DLTPrint(DLTNode* phead);
//尾插函数声明
void DLTPushBack(DLTNode* phead, DLTDataType x);
//头插函数声明
void DLTPushFront(DLTNode* phead, DLTDataType x);
//尾删函数声明
void DLTPopBack(DLTNode* phead);
//头删函数声明
void DLTPopFront(DLTNode* phead);
//链表长度
int DLTSize(DLTNode* phead);
//查找
DLTNode* DLTFind(DLTNode* phead, DLTDataType x);
//在pos之前插入
void DLTInsert(DLTNode* pos, DLTDataType x);
//删除pos位置
void DLTErase(DLTNode* pos);
//销毁函数
void DLTDestory(DLTNode* phead);DLish.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "DList.h"
//开辟新节点函数实现
DLTNode* BuyDLTNode(DLTDataType x)
{
DLTNode* node = (DLTNode*)malloc(sizeof(DLTNode));
if (node == NULL)
{
perror("malloc fail");
exit(-1);
}
node->data = x;
node->next = NULL;
node->prev = NULL;
return node;
}
//初始化节点函数实现
DLTNode* DLTInit()
{
DLTNode* phead = BuyDLTNode(-1);
phead->next = phead;
phead->prev = phead;
return phead;
}
//遍历函数实现
void DLTPrint(DLTNode* phead)
{
assert(phead);
printf("phead <-> ");
DLTNode* cur = phead->next;
while (cur != phead)
{
printf("%d <-> ", cur->data);
cur = cur->next;
}
printf("\n");
}
//尾插函数实现
void DLTPushBack(DLTNode* phead, DLTDataType x)
{
assert(phead);
//①常规写法
DLTNode* tail = phead->prev;
DLTNode* newnode = BuyDLTNode(x);
newnode->prev = tail;
tail->next = newnode;
newnode->next = phead;
phead->prev = newnode;
//②复用 DLTInsert
//DLTInsert(phead, x);
}
//头插函数实现
void DLTPushFront(DLTNode* phead, DLTDataType x)
{
assert(phead);
//①常规写法
DLTNode* newnode = BuyDLTNode(x);
newnode->next = phead->next;
phead->next->prev = newnode;
phead->next = newnode;
newnode->prev = phead;
//②复用DLTInsert
//DLTInsert(phead->next, x);
}
//尾删函数实现
void DLTPopBack(DLTNode* phead)
{
assert(phead);
assert(phead->next != phead);//检查链表是否为空
//①常规写法
DLTNode* tail = phead->prev;
DLTNode* tailPrev = tail->prev;
free(tail);
tailPrev->next = phead;
phead->prev = tailPrev;
//②复用DLTErase
//DLTErase(phead->prev);
}
//头删函数实现
void DLTPopFront(DLTNode* phead)
{
assert(phead);
assert(phead->next != phead);
//①常规写法
DLTNode* first = phead->next;
DLTNode* second = first->next;
free(first);
phead->next = second;
second->prev = phead;
//②复用DLTErase
//DLTErase(phead->next);
}
//链表长度
int DLTSize(DLTNode* phead)
{
assert(phead);
int size = 0;
DLTNode* cur = phead->next;
while (cur != phead)
{
++size;
cur = cur->next;
}
return size;
}
//查找
DLTNode* DLTFind(DLTNode* phead, DLTDataType x)
{
assert(phead);
DLTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}
//在pos之前插入
void DLTInsert(DLTNode* pos, DLTDataType x)
{
assert(pos);
DLTNode* posPrev = pos->prev;
DLTNode* newnode = BuyDLTNode(x);
posPrev->next = newnode;
newnode->prev = posPrev;
newnode->next = pos;
pos->prev = newnode;
}
//删除pos位置
void DLTErase(DLTNode* pos)
{
assert(pos);
DLTNode* posPrev = pos->prev;
DLTNode* posNext = pos->next;
free(pos);
posPrev->next = posNext;
posNext->prev = posPrev;
}
//销毁函数
void DLTDestory(DLTNode* phead)
{
assert(phead);
DLTNode* cur = phead->next;
while (cur != phead)
{
DLTNode* next = cur->next;
free(cur);
cur = next;
}
free(phead);
}test.c
#define _CRT_SECURE_NO_WARNINGS 1
#include "DList.h"
int main()
{
DLTNode* plist = DLTInit();
DLTPushBack(plist, 1);
DLTPushBack(plist, 2);
DLTPushBack(plist, 3);
DLTPushBack(plist, 4);
DLTPushBack(plist, 5);
DLTPrint(plist);
DLTPushFront(plist, 10);
DLTPushFront(plist, 11);
DLTPushFront(plist, 12);
DLTPrint(plist);
DLTDestory(plist);
plist = NULL;
DLTPrint(plist);
return 0;
}原文地址：https://blog.csdn.net/weixin_73629886/article/details/142493926
免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！