带头双向循环链表
1.双向链表的结构
注意:
这里的“带头”跟前⾯我们说的“头节点”是两个概念,实际前面的在单链表阶段称呼不严谨,但是为了们更好的理解就直接称为单链表的头节点。
带头链表里的头节点,实际为“哨兵位”,哨兵位节点不存储任何有效元素,只是站在这里“放哨的”
“哨兵位”存在的意义: 遍历循环链表避免死循环。
2. 双向链表的各种函数实现
首先,我们先定义一个双向链表的结构体
typedef int LTDataType;
//定义双向链表的结构
typedef struct ListNode
{
LTDataType data;
struct ListNode* prev;//指针保存前⼀个节点的地址
struct ListNode* next;//指针保存下⼀个节点的地址
}LTNode;
打印双向循环链表
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
注意:
这里的链表是带有哨兵位的,所以,我们应该从头节点的下一个开始打印,并且因为链表是循环的,所以打印的终止条件应该是pcur != phead。
申请一个节点
LTNode* LTBuyNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->data = x;
newnode->next = newnode->prev = newnode;
return newnode;
}
这里也可以把newnode->next = newnode->prev = NULL;,但是注意不要忘记把初始化函数的phead->next = phead->prev = NULL;,这样才符合双向循环链表的结构。
初始化链表
LTNode* LTInit()
{
LTNode* phead = LTBuyNode(-1);
return phead;
}
双向链表尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
LTNode* tail = phead->prev;
newnode->next = phead;
newnode->prev = tail;
tail->next = newnode;
phead->prev = newnode;
}
双向链表的头插
void LTPushFornt(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
LTNode* next = phead->next;
newnode->next = next;
newnode->prev = phead;
next->prev = newnode;
phead->next = newnode;
}
双向链表的尾删
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* del = phead->prev;
LTNode* prev = del->prev;
prev->next = phead;
phead->prev = prev;
free(del);
del = NULL;
}
双向链表的头删
void LTPopFornt(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* del = phead->next;
LTNode* next = del->next;
next->prev = del;
phead->next = next;
free(del);
del = NULL;
}
双向链表查找
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
双向链表在pos的前面进行插入
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
LTNode* next = pos->next;
newnode->next = next;
newnode->prev = pos;
next->prev = pos;
pos->next = newnode;
}
双向链表删除pos位置的结点
void LTErase( LTNode* pos)
{
assert(pos);
LTNode* next = pos->next;
LTNode* prev = pos->prev;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
双向链表销毁
void LTDestory(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}
3. 全部代码实现
List.h
#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int LTDataType;
//定义双向链表的结构
typedef struct ListNode
{
LTDataType data;
struct ListNode* prev;
struct ListNode* next;
}LTNode;
//注意:双向链表是带有哨兵位的,插入数据之前必须要初始化一个哨兵位
//void LTInit(LTNode** pphead);
LTNode* LTInit();
void LTPushBack(LTNode* phead, LTDataType x);
void LTPrint(LTNode* phead);
void LTPushFornt(LTNode* phead, LTDataType x);
void LTPopBack(LTNode* phead);
void LTPopFornt(LTNode* phead);
LTNode* LTFind(LTNode* phead, LTDataType x);
void LTInsert(LTNode* pos, LTDataType x);
void LTErase(LTNode* pos);
void LTDestory(LTNode* phead);
List.c
#define _CRT_SECURE_NO_WARNINGS
#include "List.h"
LTNode* LTBuyNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail");
exit(1);
}
newnode->data = x;
newnode->next = newnode->prev = newnode;
return newnode;
}
LTNode* LTInit()
{
LTNode* phead = LTBuyNode(-1);
return phead;
}
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
LTNode* tail = phead->prev;
newnode->next = phead;
newnode->prev = tail;
tail->next = newnode;
phead->prev = newnode;
}
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d->", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
void LTPushFornt(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
LTNode* next = phead->next;
newnode->next = next;
newnode->prev = phead;
next->prev = newnode;
phead->next = newnode;
}
void LTPopBack(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* del = phead->prev;
LTNode* prev = del->prev;
prev->next = phead;
phead->prev = prev;
free(del);
del = NULL;
}
void LTPopFornt(LTNode* phead)
{
assert(phead);
assert(phead->next != phead);
LTNode* del = phead->next;
LTNode* next = del->next;
next->prev = del;
phead->next = next;
free(del);
del = NULL;
}
LTNode* LTFind(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
if (pcur->data == x)
{
return pcur;
}
pcur = pcur->next;
}
return NULL;
}
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
LTNode* next = pos->next;
newnode->next = next;
newnode->prev = pos;
next->prev = pos;
pos->next = newnode;
}
void LTErase( LTNode* pos)
{
assert(pos);
LTNode* next = pos->next;
LTNode* prev = pos->prev;
prev->next = next;
next->prev = prev;
free(pos);
pos = NULL;
}
void LTDestory(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = next;
}
free(phead);
phead = NULL;
}
test.c
#include "List.h"
int main()
{
LTNode* plist = LTInit();
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
LTNode* ret = LTFind(plist, 1);
if (ret == NULL)
{
printf("找不到\n");
}
else
{
printf("找到了\n");
}
LTDestory(plist);
plist = NULL;
return 0;
}
运行结果如图:
4.顺序表和链表的区别
不同点 | 顺序表 | 链表 |
---|---|---|
存储空间上 | 物理上一定连续 | 逻辑上连续,但物理上不一定连续 |
随机访问 | 支持O(1) | 不支持:O(N) |
任意位置插入或者删除元素 | 可能需要搬移元素,效率低O(N) | 只需修改指针指向 |
插入 | 动态顺序表,空间不够时需要扩容 | 没有容量的概念 |
应用场景 | 元素高效存储+频繁访问 | 任意位置插入和删除频繁 |
缓存利用率 | 高 | 低 |
备注:缓存利用率参考存储体系结构 以及局部原理性。