双向链表详解及实现
双向链表作为链表的重要形式,相比单链表增加了前驱指针,使得节点可以双向遍历,在插入、删除等操作上更加灵活。本文将详细讲解双向链表的结构、实现方法,并与顺序表进行对比分析,帮助大家深入理解双向链表。
1. 双向链表的结构
1.1 结构定义
双向链表中最常用的结构是带头双向循环链表。
- 带头:这里的 “头” 是 “哨兵位”(头节点),不存储有效数据,仅用于简化边界条件处理。
- 双向:每个节点包含
prev
(前驱指针)和next
(后继指针),分别指向前后节点。 - 循环:尾节点的
next
指向哨兵位,哨兵位的prev
指向尾节点,形成闭环。
其结构如下:
1.2 组成结构
链表:由节点组成。
节点:由数据+指向下一个节点的指针+指向前一个节点的指针组成。
1.3 哨兵位的意义
哨兵位(头节点)是双向链表的关键设计,其意义在于:
- 避免遍历或操作时出现死循环(循环结构中通过哨兵位判断边界)。
- 简化空链表和非空链表的操作逻辑(无需单独处理头 / 尾节点为
NULL
的情况)。
注意:此处的 “带头” 与单链表中 “头节点”(第一个有效节点)不同。单链表的 “头节点” 是有效数据的第一个节点,而双向链表的 “哨兵位” 不存储有效数据,仅作为边界标记。
1.4 单链表和双向链表为空时的区别
2. 双向链表的实现
2.1 节点结构定义
首先定义双向链表的节点结构,包含前驱指针、后继指针和数据域:
//定义
typedef int LTDataType;
// 数据类型typedef struct ListNode {// 存储的数据LTDataType data;// 指向后一个节点struct ListNode* next; // 指向前一个节点struct ListNode* prev;
} LTNode;
2.2 核心操作实现
双向链表的核心操作包括初始化、销毁、增删查改等,以下是具体实现:
2.2.1 初始化(LTInit)
初始化函数用于创建哨兵位,并构建循环结构:
//申请节点
LTNode* LTBuyNode(LTDataType x)
{LTNode* node = (LTNode*)malloc(sizeof(LTNode));if (node == NULL){perror("malloc fail"); // 内存分配失败exit(1); // 异常退出}node->data = x;node->next = node->prev = node;// 初始化哨兵位:自己指向自己(空链表状态)// 无效数据,仅占位return node;
}//初始化
LTNode* LTInit(LTNode** pphead)
{// 创建哨兵位*pphead = LTBuyNode(-1);
}
初始化哨兵位:自己指向自己(空链表状态),自循环。
初始化时,不可以将哨兵位的next 指针以及prev 指针初始化为NULL。
测试一下:
void ListTest01()
{LTNode* plist = NULL;//初始化测试LTInit(&plist);
}
int main()
{return 0;
}
调试:
2.2.2 尾插(LTPushBack)
在链表尾部插入新节点:
//尾插
void LTPushBack(LTNode* phead, LTDataType x)
{//注意在插入前,要将链表初始化至只有一个头结点的情况assert(phead);// 创建新节点LTNode* newnode = LTBuyNode(x);// 找到尾节点(哨兵位的prev)LTNode* tail = phead->prev;//需要改 头节点phead 尾节点phead->prev 插入节点newnode// newnodenewnode->prev = phead->prev;newnode->next = phead;//phead->nextphead->prev->next = newnode;//pheadphead->prev = newnode;
}
注意在插入前,要将链表初始化至只有一个头结点的情况。
对比一下:
哨兵位节点不能被删除,节点的地址也不发生变化,所以传一级指针即可:
于是进行以下修改:
不可以改变位置。
2.2.3 打印(LTPrint)
打印函数用于输出链表中的有效数据:
//打印
void LTPrint(LTNode* phead)
{assert(phead);printf("哨兵位 <-> ");LTNode* pcur = phead->next;while (pcur != phead) { // 遍历到哨兵位停止printf("%d <-> ", pcur->data);pcur = pcur->next;}printf("哨兵位\n"); // 打印闭环标志
}
测试一下:
//打印插入数据(尾插)测试LTPushBack(plist, 1);LTPrint(plist);LTPushBack(plist, 2);LTPrint(plist);LTPushBack(plist, 3);LTPrint(plist);
2.2.4 头插(LTPushFront)
在链表头部(哨兵位后)插入新节点:
//头插
void LTPushFront(LTNode* phead, LTDataType x)
{assert(phead);LTNode* newnode = LTBuyNode(x);// 需要修改phead newnode phead->next// newnodenewnode->next = phead->next;newnode->prev = phead;// phead->nextphead->next->prev = newnode;phead->next = newnode;
}
这里不可完全交换:
如果要交换,则 phead->next 节点不可以通过哨兵位找,而是 newnode 找。
测试一下:
//头插测试LTPushFront(plist, 1);LTPrint(plist);LTPushFront(plist, 2);LTPrint(plist);LTPushFront(plist, 3);LTPrint(plist);