数据结构——双向链表（附图文讲解 | 超详细）
·
文章目录
一、前言
这篇博客将从全面讲解数据结构中的双向链表链表（带头双向循环链表）
二、双向链表
2.1 定义
双向链表主要表现就是拥有头节点，链表永不为空，不需要二级指针；可以通过一个节点找到上一个或者下一个节点；头尾相连呈环状。
它主要结构是由prev、next、data，这三个结构组成，通过prev找到前一个结点，next找下一个结点，data储存链表数据
如图所示
2.2 双向链表的实现
1.创建一个双向链表
//创建双向链表
typedef int LTDataType;
typedef struct ListNode {
LTDataType data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
2.双向链表的初始化
创建一个哨兵位，让他自己变成一个环形链表
只需要让它自己指向自己就可以
//双向链表的初始化
LTNode* LTBuyNode(LTDataType x)
{
LTNode* newnode = (LTNode*)malloc(sizeof(LTNode));
if (newnode == NULL)
{
perror("malloc fail!");
exit(1);
}
newnode->data = x;
newnode->prev = newnode->next = newnode;
return newnode;
}
LTNode* LTInit()
{
LTNode* phead = LTBuyNode(-1);
return phead;
}
2.双向链表的打印
//双向链表的打印
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
3.双向链表的尾插
先将newnode->next和newnode->prev分别指向phead和phead->prev（尾插之前的最后一个结点）再将phead->prev->next和phead->prev指向newnode
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}
4.双向链表的头插
先将newnode->next和newnode->prev分别指向phead->next和phead，再将phead->next->prev和phead->next指向newnode
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
5.判断链表是否为空
只有一个头结点的情况下，双向链表为空
//只有一个头结点的情况下，双向链表为空
bool LTEmptpy(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
6.双向链表的尾删
del:最后一个结点；
先将del->prev->next和phead->prev分别指向phead和del->prev，再将del结点销毁
//尾删
void LTPopBack(LTNode* phead)
{
assert(!LTEmptpy(phead));
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}
7.双向链表的头删
del:第一个结点
先将phead->next和del->next->prev分别指向del->next和phead，再将del销毁
//头删
void LTPopFront(LTNode* phead)
{
assert(!LTEmptpy(phead));
LTNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
free(del);
del = NULL;
}
8.查找
//查找
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;
}
9.在指定位置之后插入结点
pos:指定位置
先将newnode->prev和newnode->next分别指向pos和pos->next，再将pos->next和pos->next->prev指向newnode，在指定位置之前插入结点也是同理
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = LTBuyNode(x);
newnode->prev = pos;
newnode->next = pos->next;
pos->next = newnode;
pos->next->prev = newnode;
}
10.删除指定位置的结点
pos:指定位置
先将pos->next->prev和pos->prev->next分别指向pos->prev和pos->next，再将pos销毁
//删除pos位置的结点
void LTErase(LTNode* pos)
{
assert(pos);
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}
10.双向链表的销毁
//销毁
void LTDesTroy(LTNode* phead)
{
LTNode* pcur = phead->next;
while (pcur != phead)
{
LTNode* next = pcur->next;
free(pcur);
pcur = 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 data;
struct ListNode* next;
struct ListNode* prev;
}LTNode;
//双向链表的初始化
// void LTInit(LTNode** pphead);
LTNode* LTInit();
//双向链表的打印
void LTPrint(LTNode* phead);
//尾插
void LTPushBack(LTNode* phead, LTDataType x);
//头插
void LTPushFront(LTNode* phead, LTDataType x);
//只有一个头结点的情况下，双向链表为空
bool LTEmptpy(LTNode* phead);
//尾删
void LTPopBack(LTNode* phead);
//头删
void LTPopFront(LTNode* phead);
//查找
LTNode* LTFind(LTNode* phead, LTDataType x);
//在pos位置之后插入数据
void LTInsert(LTNode* pos, LTDataType x);
//删除pos位置的结点
void LTErase(LTNode* pos);
//销毁链表
void LTDesTroy(LTNode* phead);
List.c
#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->prev = newnode->next = newnode;
return newnode;
}
LTNode* LTInit()
{
LTNode* phead = LTBuyNode(-1);
return phead;
}
//双向链表的打印
void LTPrint(LTNode* phead)
{
assert(phead);
LTNode* pcur = phead->next;
while (pcur != phead)
{
printf("%d -> ", pcur->data);
pcur = pcur->next;
}
printf("\n");
}
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = phead;
newnode->prev = phead->prev;
phead->prev->next = newnode;
phead->prev = newnode;
}
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
LTNode* newnode = LTBuyNode(x);
newnode->next = phead->next;
newnode->prev = phead;
phead->next->prev = newnode;
phead->next = newnode;
}
//只有一个头结点的情况下，双向链表为空
bool LTEmptpy(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}
//尾删
void LTPopBack(LTNode* phead)
{
assert(!LTEmptpy(phead));
LTNode* del = phead->prev;
del->prev->next = phead;
phead->prev = del->prev;
free(del);
del = NULL;
}
//头删
void LTPopFront(LTNode* phead)
{
assert(!LTEmptpy(phead));
LTNode* del = phead->next;
phead->next = del->next;
del->next->prev = phead;
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);
newnode->prev = pos;
newnode->next = pos->next;
pos->next = newnode;
pos->next->prev = newnode;
}
//删除pos位置的结点
void LTErase(LTNode* pos)
{
assert(pos);
pos->next->prev = pos->prev;
pos->prev->next = pos->next;
free(pos);
pos = NULL;
}
void LTDesTroy(LTNode* 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"
void test01()
{
LTNode* plist = LTInit();
//尾插
// LTPushBack(plist, 1);
// LTPushBack(plist, 2);
// LTPushBack(plist, 3);
// LTPrint(plist);
// LTPushBack(plist, 4);
// LTPrint(plist);
//头插
// LTPushBack(plist, 1);
// LTPushBack(plist, 2);
// LTPushBack(plist, 3);
// LTPrint(plist);
// LTPushFront(plist, 4);
// LTPrint(plist);
//尾删
// LTPushBack(plist, 1);
// LTPushBack(plist, 2);
// LTPushBack(plist, 3);
// LTPushBack(plist, 4);
// LTPrint(plist);
// LTPopBack(plist);
// LTPrint(plist);
//头删
// LTPushBack(plist, 1);
// LTPushBack(plist, 2);
// LTPushBack(plist, 3);
// LTPushBack(plist, 4);
// LTPrint(plist);
// LTPopFront(plist);
// LTPrint(plist);
//在pos位置之后插入数据
// LTPushBack(plist, 1);
// LTPushBack(plist, 2);
// LTPushBack(plist, 3);
// LTPushBack(plist, 4);
// LTNode* find = LTFind(plist, 2);
// if (find == NULL)
// {
// printf("没找到\n");
// }else{
// printf("找到了\n");
// }
// LTInsert(find, 100);
// LTPrint(plist);
//删除pos位置的结点
LTPushBack(plist, 1);
LTPushBack(plist, 2);
LTPushBack(plist, 3);
LTPushBack(plist, 4);
LTPrint(plist);
LTNode* find = LTFind(plist, 2);
if (find == NULL)
{
printf("没找到\n");
}else{
printf("找到了\n");
}
LTErase(find);
LTPrint(plist);
LTDesTroy(plist);
plist = NULL;
}
int main()
{
test01(); //测试
return 0;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
26
0- 0
已为社区贡献1条内容
所有评论(0)