双向链表详解
一、什么是双向链表？双向链表（Doubly Linked List）是一种链式数据结构，每个节点包罗三个部分：数据域、指向前驱节点的指针（prev）、指向后继节点的指针（next）。与单向链表相比，双向链表可以方便地进行前向和后向遍历，插入和删除操作也更加灵活高效。
图解：
https://i-blog.csdnimg.cn/direct/d29d91b5dc7348699ff5c23f3d8ba1f9.png
二、双向链表的结构定义
在C语言中，双向链表的节点通常定义如下：
// 数据类型定义
typedef int LTDataType;
// 双向链表节点结构体
typedef struct LTNode {
LTDataType data; // 数据域
struct LTNode* prev; // 指向前驱节点
struct LTNode* next; // 指向后继节点
} LTNode; 三、双向链表的基本操作
1. 初始化链表
初始化时，通常创建一个带有哨兵（头结点）的循环双向链表，便于操作。
LTNode* ListInit() {
LTNode* phead = BuyListNode(0); // 头结点数据可设为0或特殊值
phead->next = phead;
phead->prev = phead;
return phead;
} 2. 判断链表是否为空
//判断双链表是否为空
bool ListEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
} 3. 盘算链表长度
//计算双向链表大小
size_t ListSize(LTNode* phead)
{
assert(phead);
size_t n = 0;
LTNode* cur = phead->next;
while (cur != phead)
{
++n;
cur = cur->next;
}
return n;
} 4. 节点的动态申请
// 动态申请一个节点
LTNode* BuyListNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
printf("malloc fail\n");
exit(-1);
}
node->next = NULL;
node->prev = NULL;
node->data = x;
return node;
} 5. 插入操作
尾插
//双向链表尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead, x);
} 头插
//双向链表头插
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead->next, x);
} 在指定位置前插入
图解：
https://i-blog.csdnimg.cn/direct/7e418737bc6e4e2681a9c622644808ad.png
代码实现：
// 在pos之前去插入
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* prev = pos->prev;
// prev newnode pos
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
} 6. 删除操作
尾删
//双向链表尾删
void ListPopBack(LTNode* phead)
{
assert(phead);
assert(!ListEmpty(phead));
//LTNode* tail = phead->prev;
//LTNode* tailPrev = tail->prev;
//free(tail);
//tailPrev->next = phead;
//phead->prev = tailPrev;
ListErase(phead->prev);
} 头删
//双向链表头删
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(!ListEmpty(phead));
ListErase(phead->next);
} 删除指定位置节点
// 删除pos位置
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
free(pos);
pos = NULL;
prev->next = next;
next->prev = prev;
} 7. 查找操作
//双向链表查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
} 8. 打印链表
// 双向链表打印
void ListPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
} 9. 销毁链表
//销毁双向链表
void ListDestroy(LTNode* phead)
{
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
//cur = NULL;
cur = next;
}
free(phead);
//phead = NULL;
// 这里其实置空不置空都可以的，因为处理函数作用，没人能访问phead
// 其次就是phead形参的置空，也不会影响外面的实参
} 四、完备示例
头文件：
#pragma once
#define _CRT_SECURE_NO_WARNINGS 1
#include <stdio.h>
#include <string.h>
#include<stdlib.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
struct ListNode* next;//后继
struct ListNode* prev;//前驱
LTDataType data;
}LTNode;
// 双向链表打印
void ListPrint(LTNode* phead);
// 动态申请一个节点
LTNode* BuyListNode(LTDataType x);
//void ListInit(LTNode** pphead);
//链表初始化
LTNode* ListInit();
//销毁双向链表
void ListDestroy(LTNode* phead);
bool ListEmpty(LTNode* phead);
size_t ListSize(LTNode* phead);
//双向链表尾插
void ListPushBack(LTNode* phead, LTDataType x);
//双向链表头插
void ListPushFront(LTNode* phead, LTDataType x);
//双向链表尾删
void ListPopBack(LTNode* phead);
//双向链表头删
void ListPopFront(LTNode* phead);
//双向链表查找
LTNode* ListFind(LTNode* phead, LTDataType x);
// 删除pos位置
void ListErase(LTNode* pos);
// 在pos之前去插入
void ListInsert(LTNode* pos, LTDataType x); .c文件
#include "List.h"//判断双链表是否为空
bool ListEmpty(LTNode* phead)
{
assert(phead);
return phead->next == phead;
}//计算双向链表大小
size_t ListSize(LTNode* phead)
{
assert(phead);
size_t n = 0;
LTNode* cur = phead->next;
while (cur != phead)
{
++n;
cur = cur->next;
}
return n;
}// 动态申请一个节点
LTNode* BuyListNode(LTDataType x)
{
LTNode* node = (LTNode*)malloc(sizeof(LTNode));
if (node == NULL)
{
printf("malloc fail\n");
exit(-1);
}
node->next = NULL;
node->prev = NULL;
node->data = x;
return node;
}//void ListInit(LTNode** pphead)//{// *pphead = BuyListNode(-1);// (*pphead)->next = *pphead;// (*pphead)->prev = *pphead;//}//链表初始化LTNode* ListInit(){ LTNode* phead = BuyListNode(0); phead->next = phead; phead->prev = phead; return phead;}//销毁双向链表
void ListDestroy(LTNode* phead)
{
LTNode* cur = phead->next;
while (cur != phead)
{
LTNode* next = cur->next;
free(cur);
//cur = NULL;
cur = next;
}
free(phead);
//phead = NULL;
// 这里其实置空不置空都可以的，因为处理函数作用，没人能访问phead
// 其次就是phead形参的置空，也不会影响外面的实参
}//void ListDestroy(LTNode** pphead)//{// LTNode* cur = (*pphead)->next;// while (cur != *pphead)// {// LTNode* next = cur->next;// free(cur);// cur = next;// }//// free(*pphead);// *pphead = NULL;//}// 双向链表打印
void ListPrint(LTNode* phead)
{
assert(phead);
LTNode* cur = phead->next;
while (cur != phead)
{
printf("%d ", cur->data);
cur = cur->next;
}
printf("\n");
}// O(1)//void ListPushBack(LTNode* phead, LTDataType x)//{// assert(phead);//// LTNode* tail = phead->prev;// LTNode* newnode = BuyListNode(x);//// tail->next = newnode;// newnode->prev = tail;// newnode->next = phead;// phead->prev = newnode;//}//双向链表尾插
void ListPushBack(LTNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead, x);
}//双向链表头插
void ListPushFront(LTNode* phead, LTDataType x)
{
assert(phead);
ListInsert(phead->next, x);
}//双向链表尾删
void ListPopBack(LTNode* phead)
{
assert(phead);
assert(!ListEmpty(phead));
//LTNode* tail = phead->prev;
//LTNode* tailPrev = tail->prev;
//free(tail);
//tailPrev->next = phead;
//phead->prev = tailPrev;
ListErase(phead->prev);
}//双向链表头删
void ListPopFront(LTNode* phead)
{
assert(phead);
assert(!ListEmpty(phead));
ListErase(phead->next);
}//双向链表查找
LTNode* ListFind(LTNode* phead, LTDataType x)
{
LTNode* cur = phead->next;
while (cur != phead)
{
if (cur->data == x)
{
return cur;
}
cur = cur->next;
}
return NULL;
}// 删除pos位置
void ListErase(LTNode* pos)
{
assert(pos);
LTNode* prev = pos->prev;
LTNode* next = pos->next;
free(pos);
pos = NULL;
prev->next = next;
next->prev = prev;
}// 在pos之前去插入
void ListInsert(LTNode* pos, LTDataType x)
{
assert(pos);
LTNode* newnode = BuyListNode(x);
LTNode* prev = pos->prev;
// prev newnode pos
prev->next = newnode;
newnode->prev = prev;
newnode->next = pos;
pos->prev = newnode;
} 测试文件：
#include"List.h"
void test()
{
LTNode* plist = ListInit();
ListPushBack(plist, 1);
ListPushBack(plist, 2);
ListPushBack(plist, 3);
ListPushBack(plist, 4);
ListPrint(plist);
}
int main()
{
test();
return 0;
} 五、注意事项与常见错误
[*] 内存管理：每次malloc后都要free，防止内存走漏。
[*] 断言与空指针查抄：操作前应查抄指针有效性。
[*] 循环链表优势：带头结点的循环双向链表能简化插入、删除等边界情况的处置惩罚。
[*] 插入与删除的O(1)特性：只要已知节点指针，插入和删除操作时间复杂度均为O(1)。
六、总结
双向链表是链表家族中非常重要的一员，适合需要频仍在两端或中心插入、删除元素的场景。掌握其实现原理和常见操作，有助于更好地理解数据结构的本质和C语言的指针操作。
免责声明：如果侵犯了您的权益，请联系站长，我们会及时删除侵权内容，谢谢合作！更多信息从访问主页：qidao123.com:ToB企服之家，中国第一个企服评测及商务社交产业平台。
页:
[1]