链表的介绍
链表的结构一共有八种:带头单向循环链表、带头单向非循环链表、带头双向循环链表、带头双向非循环链表、无头单向循环链表、无头单向非循环链表、无头双向循环链表、无头双向非循环链表。
今天我们来详解带头双向循环链表
带头双向循环链表是一种数据结构,它通过在双向链表的基础上增加循环的特性,并通过一个头结点(带头)来简化操作。这种结构在实际应用中有其独特的优缺点:
优点
- 双向遍历:链表可以从两个方向遍历,即可以向前或向后移动。这使得许多操作,如反转遍历、双端操作等,更为方便和高效。
- 循环特性:由于是循环链表,表尾与表头直接相连。这一特性使得从链表的一端到另一端的访问时间缩短,特别是在需要频繁执行环形遍历的场合(如轮转调度算法)。
- 统一操作:带头结点的链表简化了插入和删除节点的操作,因为不需要单独处理空链表的情况。头结点的存在使得链表始终非空,减少了边界条件的检查。
- 易于管理:头结点提供了一个固定的起点,无论链表是否为空,这使得链表的管理更为统一和方便。
缺点
- 额外的空间消耗:头结点本身不存储有效数据,占用一定的空间。对于内存使用极为严格的应用场景,这种额外消耗可能是一个缺点。
- 实现复杂度:相比单向链表,双向循环链表的实现更复杂。正确管理前驱和后继指针需要更多的注意和精确控制,增加了编程的难度。
- 性能开销:每次插入或删除操作都需要更新两个指针(前驱和后继),这比单向链表的操作稍显复杂,可能会略微增加时间开销。
- 循环错误:如果不正确管理节点的连接和断开,循环链表容易产生逻辑错误,如死循环或访问已删除的节点,这可能导致程序出错或崩溃。
链表详解
1. 链表的定义
实现步骤:
首先,我们还是需要先定义一个结点类型,与单向链表相比,双向链表的结点类型中需要多出一个前驱指针,用于指向前面一个结点,实现双向。
typedef int LTDataType;//存储的数据类型
typedef struct ListNode
{
LTDataType data;//数据域
struct ListNode* front;//前驱指针
struct ListNode* next;//后继指针
}ListNode;
2. 链表节点的创建
实现步骤:
-
内存分配:
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
这行代码通过malloc
函数为一个新的ListNode
结构体分配内存。sizeof(ListNode)
确保分配足够的内存以存放一个ListNode
结构体。 -
内存分配校验:
if (newNode == NULL) { ... }
这个条件判断用来检查malloc
是否成功分配了内存。如果malloc
返回NULL
,表示内存分配失败,可能是因为系统内存不足。这时,函数打印错误消息并返回NULL
,避免后续的空指针操作。 -
初始化节点数据:
newNode->data = value;
这行代码将传入的value
赋值给节点的data
属性。这样新节点就存储了它应该持有的数据。 -
自引用初始化:
newNode->front = newNode;
和newNode->next = newNode;
这两行代码初始化节点的front
和next
指针,使它们指向节点自身。这种初始化方式是为了创建一个独立的循环节点,即该节点在一个循环链表中既是头节点也是尾节点。
// 创建一个新的节点
ListNode* CreateNode(LTDataType value) {
ListNode* newNode = (ListNode*)malloc(sizeof(ListNode));
if (node == NULL) {
printf("Memory allocation failed.\n");
return NULL;
}
newNode->data = value;
newNode->front = newNode;
newNode->next = newNode;
return newNode;
}
3. 链表的初始化
实现步骤:
对双向链表进行初始化,在初始化的过程中,需要申请一个头结点,头结点的前驱和后继指针都指向自己,使得链表一开始便满足循环。
// 初始化带头的双向循环链表
ListNode* InitList() {
ListNode* phead = CreateNode(-1); // 创建头结点,数据通常设置为-1或其他标记值
if (phead != NULL) {
phead->front = phead; // 将头结点的前驱指针指向自身,确保循环链表的闭环性
phead->next = phead; // 将头结点的后继指针指向自身,同样确保循环链表的闭环性
}
return phead; // 返回头结点的指针
}
4. 链表的头插
实现步骤:
- 参数验证:
assert(phead);
这行代码使用assert
函数确保传入的头节点指针phead
不是NULL
。这是一种防御性编程实践,用于避免空指针引用。 - 创建新节点:
ListNode* newNode = CreateNode(value);
这行代码调用CreateNode
函数创建一个新的ListNode
对象,其数据域设置为传入的value
。这个函数返回一个初始化好的新节点,其front
和next
指针指向自己,形成一个独立的小循环。 - 定位第一个节点:
ListNode* Front = phead->next;
这行代码获取头节点后面的第一个节点(我们称之为Front
)。这是为了之后将新节点插入头节点和Front
之间。 - 连接新节点与头节点:
phead->next = newNode;
将头节点的next
指针指向新节点,从而把新节点作为链表的第一个节点。newNode->front = phead;
将新节点的front
指针指向头节点,确保从新节点向前遍历可以回到头节点。 - 连接新节点与原第一个节点:
newNode->next = Front;
将新节点的next
指针指向原第一个节点Front
,这样新节点就正确地插入在头节点和Front
之间。Front->front = newNode;
更新Front
的front
指针指向新节点,确保从Front
向前遍历也可以到达新节点。
void ListPushFront(ListNode* phead, LTDataType value)
{
assert(phead);
ListNode* newNode = CreateNode(value);//申请一个结点,数据域赋值为value
ListNode* Front = phead->next;//记录头结点的后一个结点位置
//建立新结点与头结点之间的双向关系
phead->next = newNode;
newNode->front = phead;
//建立新结点与front结点之间的双向关系
newNode->next = Front; //这时候不能用phead了,因为phead
Front->front = newNode;
}
5. 链表的头删
实现步骤:
-
参数验证:
assert(phead);
使用assert
函数确保传入的头节点指针phead
不是NULL
。这一步防止后续代码在空指针上进行操作,可能导致程序崩溃。assert(phead->next != phead);
确保链表中除头节点外还有其他节点。如果头节点的next
指针指向自己,说明链表为空,此时不能进行删除操作。 -
定位节点:
ListNode* Front = phead->next;
这行代码定位到链表的当前前端节点,即头节点后的第一个节点。ListNode* newFront = Front->next;
获取当前前端节点的下一个节点,这将成为新的前端节点。 -
重建链接:
phead->next = newFront;
更新头节点的next
指针,直接指向newFront
,从而绕过Front
节点。newFront->front = phead;
更新newFront
的front
指针,指向头节点,确保从新的前端节点向前遍历可以回到头节点。 -
释放内存:
free(Front);
释放原前端节点Front
所占的内存。这一步是必须的,以避免内存泄漏。
void ListPopFront(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* Front = phead->next;//记录头结点的后一个结点
ListNode* newFront = front->next;//记录front结点的后一个结点
//建立头结点与newFront结点之间的双向关系
phead->next = newFront;
newFront->front = phead;
free(Front);//释放Front结点
}
6. 链表的尾插
实现步骤:
-
参数验证:
assert(phead);
使用assert
函数确保传入的头节点指针phead
不是NULL
。这个检查是为了防止在空指针上执行操作,这可能会导致程序崩溃。 -
创建新节点:
ListNode* newNode = CreateNode(value);
这行代码调用CreateNode
函数,创建一个新的ListNode
对象,并将value
设置为节点的数据。CreateNode
函数返回一个已经初始化的新节点,它的front
和next
指针指向自己,形成一个独立的小循环。 -
定位尾节点:
ListNode* tail = phead->front;
获取当前的尾节点,即头节点的前一个节点。 -
连接新节点与头节点:
newNode->next = phead;
将新节点的next
指针指向头节点,确保新节点成为链表的最后一个节点,其后继指向头节点。phead->front = newNode;
更新头节点的front
指针指向新节点,从而将新节点正式连接到链表的尾部。 -
连接新节点与原尾节点:
tail->next = newNode;
将原尾节点的next
指针指向新节点,这样原尾节点之后就是新节点了。newNode->front = tail;
将新节点的front
指针指向原尾节点,确保从新节点向前遍历可以到达原尾节点。
void ListPushBack(ListNode* phead, LTDataType value)
{
assert(phead);
ListNode* newNode = CreateNode(value);//申请一个结点,数据域赋值为x
ListNode* tail = phead->front;//记录头结点的前一个结点的位置
//建立新结点与头结点之间的双向关系
newNode->next = phead;
phead->front = newNode;
//建立新结点与tail结点之间的双向关系
tail->next = newNode;
newNode->front = tail;
}
7. 链表的尾删
实现步骤:
-
校验传入的头节点:使用
assert(phead)
确保传入的头节点指针phead
是有效的。这是为了防止空指针引用,确保链表至少被初始化。使用assert(phead->next != phead)
确保链表不是空的(即链表中除了头节点之外还有其他节点)。这个检查是必要的,因为空链表(只有头节点指向自己)无法进行尾部删除操作。 -
定位尾部节点和新尾部节点:使用
ListNode* Tail = phead->front;
定位到当前的尾部节点(即头节点的前一个节点Tail
),这是要被移除的节点。使用ListNode* newTail = Tail->front;
定位到新的尾部节点,即当前尾部节点的前一个节点newTail
。 -
重建头节点与新尾部节点之间的链接:设置新尾部节点的
next
指针指向头节点,即newTail->next = phead;
,这样从新尾部节点向后遍历即可直接到达头节点。设置头节点的front
指针指向新尾部节点,即phead->front = newTail;
,这样从头节点向前遍历即可直接到达新尾部节点。 -
释放原尾部节点的内存:使用
free(Tail);
释放原尾部节点Tail
占用的内存。这一步是必须的,以避免内存泄漏。
void ListPopBack(ListNode* phead)
{
assert(phead);
assert(phead->next != phead);
ListNode* Tail = phead->front;//记录头结点的前一个结点
ListNode* newTail = Tail->front;//记录tail结点的前一个结点
//建立头结点与newtail结点之间的双向关系
newTail->next = phead;
phead->front = newTail;
free(Tail);//释放Tail结点
}
8. 在pos位置插入节点
实现步骤:
-
校验传入的节点指针:使用
assert(pos)
确保传入的节点指针pos
是有效的。这一步骤防止空指针引用,保证程序的健壮性。 -
定位前驱节点:使用
ListNode* before = pos->front;
获取pos
节点的前一个节点before
。这样做是为了接下来将新节点插入到before
和pos
之间。 -
创建新节点:调用
CreateNode(value)
函数创建一个新的节点newNode
,其中value
是新节点的数据值。这个函数应该分配内存并初始化新节点的data
字段和指针字段。 -
建立新节点与前驱节点的关系:设置
before
节点的next
指针指向新节点,即before->next = newNode;
,这样before
和新节点之间的链接就建立了。设置新节点的front
指针指向before
,即newNode->front = before;
,确保新节点能正确链接到链表中。 -
建立新节点与指定位置节点的关系:设置新节点的
next
指针指向pos
,即newNode->next = pos;
,将新节点直接链接到pos
节点前面。设置pos
节点的front
指针指向新节点,即pos->front = newNode;
,完成从pos
节点到新节点的双向链接。
//在指定位置插入结点
void ListInsert(ListNode* pos, LTDataType value)
{
assert(pos);
ListNode* before = pos->front;//记录pos指向结点的前一个结点
ListNode* newNode = CreateNode(value);//申请一个结点,数据域赋值为x
//建立新结点与before结点之间的双向关系
before->next = newNode;
newNode->front = before;
//建立新结点与pos指向结点之间的双向关系
newNode->next = pos;
pos->front = newNode;
}
9. 在pos位置删除节点
实现步骤:
-
检查有效性:使用
assert(pos)
来确保传入的节点指针pos
是有效的,即不为NULL
。这是一个基本的安全检查,防止对空指针进行操作,这样的操作可能导致程序崩溃 -
定位前驱和后继节点:使用
ListNode* before = pos->front;
获取pos
节点的前一个节点,并将其存储在变量before
中。使用ListNode* after = pos->next;
获取pos
节点的后一个节点,并将其存储在变量after
中。 -
重建链接:将
before
节点的next
指针指向after
节点,即before->next = after;
。这步操作是断开before
节点与pos
节点之间的链接,并直接链接到after
节点。 - 将
after
节点的front
指针指向before
节点,即after->front = before;
。这步操作是断开after
节点与pos
节点之间的链接,并直接链接到before
节点。 -
释放内存:使用
free(pos);
释放pos
指针指向的节点所占用的内存。这是清理资源的重要步骤,避免内存泄漏。
//删除指定位置结点
void ListErase(ListNode* pos)
{
assert(pos);
ListNode* before = pos->front;//记录pos指向结点的前一个结点
ListNode* after = pos->next;//记录pos指向结点的后一个结点
//建立before结点与after结点之间的双向关系
before->next = after;
after->front = before;
free(pos);//释放pos指向的结点
}
10. 链表判空
实现步骤:文章来源:https://www.toymoban.com/news/detail-858488.html
-
检查头节点的后继指针:在带头的双向循环链表中,头节点(哨兵节点)不存储数据。链表为空的标准是头节点的
next
指针指向自身。 -
检查头节点的前驱指针:为了确保链表完整性,也应验证头节点的
prev
指针是否也指向自身。
bool isEmpty(ListNode* *phead) {
return (phead->next == phead && head->front == phead);
}
11. 获取链表中的元素个数
实现步骤:文章来源地址https://www.toymoban.com/news/detail-858488.html
- 初始化计数器: 创建一个变量来保存节点的数量。
- 遍历链表: 从链表的头节点开始,遍历每一个节点,直到链表末尾。
- 递增计数器: 每访问一个节点,计数器增加1。
- 返回结果: 遍历完整个链表后,计数器的值即为链表中的元素个数。
//获取链表中的元素个数
int ListSize(ListNode* phead)
{
assert(phead);
int count = 0;//初始化计数器
ListNode* cur = phead->next;//从头节点的后一个结点开始遍历
while (cur != phead)//当cur指向头节点时,遍历完毕,头节点不计入总元素个数
{
count++;
cur = cur->next;
}
return count;//返回元素个数
}
到了这里,关于数据结构 - 链表详解(二)—— 带头双向循环链表的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!