数据结构-双链表(图解)

目录

双链表（Double-Linked List）的概念与基本特性

一、双链表的基本组成

二、双链表的主要特性

三、双链表的操作 

代码展示

malloc开辟函数

解析

初始化

解析

头插

解析

尾插

解析

头删

解析

尾删

解析

pos之后插入

解析

pos删除

解析

打印

解析

全部代码展示

main.c

text.c

text.h

---

双链表（Double-Linked List）的概念与基本特性

双链表是一种常用且重要的线性数据结构，它在计算机科学和软件工程中扮演着不可或缺的角色。相较于单链表，双链表的每个节点包含两个指针，分别指向其前驱节点（previous node）和后继节点（next node），这一特性使得双链表在数据操作上具有更高的灵活性。

一、双链表的基本组成

双链表中的每一个元素称为节点（Node），每个节点通常包含三个部分：

1. 数据域（Data Field）：用于存储实际数据，可以是任何类型的数据。
2. 前驱指针（Previous Pointer/Backward Pointer）：指向当前节点的前一个节点。
3. 后继指针（Next Pointer/Forward Pointer）：指向当前节点的下一个节点。

二、双链表的主要特性

1. 双向遍历：由于每个节点都有前后两个指针，因此可以在列表中双向遍历，无需像单链表那样只能从头节点开始向前遍历。
2. 插入与删除的便捷性：在双链表中插入或删除一个节点时，只需改变相应节点的前后节点的指针指向即可，操作相对简单高效。

三、双链表的操作 

常见的双链表操作包括创建、插入（包括头部插入、尾部插入和指定位置插入）、删除（包括头部删除、尾部删除和指定节点删除）、查找以及遍历等。

代码展示

malloc开辟函数

//内存开辟
listcode* inaugurate(LTDataType x) {
	listcode* list = (listcode*)malloc(sizeof(listcode));
	if (list == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//初始值
	list->val = x;
	list->next = list->prev = NULL;
 
	return list;
}

解析

listcode* inaugurate(LTDataType x)`
 函数定义：`inaugurate`是一个函数，接收一个参数`x`，类型为`LTDataType`。这个函数返回一个指向`listcode`结构体类型的指针。
`listcode* list = (listcode*)malloc(sizeof(listcode));`
- 动态内存分配：使用`malloc`函数动态地在堆内存中分配一块大小等于`listcode`结构体所占用空间的连续区域，并将其地址赋值给`listcode`类型的指针变量`list`。如果内存分配失败，`malloc`将返回NULL。
 
if (list == NULL)
{
    perror("malloc");
    exit(1);
}

• 错误处理：检查list是否为空（即内存分配是否成功）。若list为NULL，则说明内存分配失败，调用perror输出错误信息（"malloc"），然后调用exit(1)终止程序执行。

list->val = x;

• 初始化节点数据：将传入的参数x赋值给新创建节点的val字段，这里假设val是listcode结构体中用于存储数据的成员变量。

list->next = list->prev = NULL;

• 初始化节点指针：将新创建节点的next和prev指针都初始化为NULL，表示这是链表中的一个独立节点，目前既没有前驱也没有后继节点。

最后，函数返回初始化后的节点指针list，这样就可以进一步将此节点添加到现有的双链表中或者其他相关操作。

phead->next = phead;
phead->prev = phead;

---

初始化

//初始化
listcode* initialize() {
	listcode* phead = inaugurate(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}

解析

`listcode* initialize()`
- 函数定义：`initialize`函数无参数，其功能是初始化一个循环双链表，并返回链表的头节点。
listcode* phead = inaugurate(0);

• 创建头节点：调用上面解释的inaugurate函数初始化并创建一个新的listcode节点，并将一个默认值0赋给节点的val字段。并将新创建的节点指针赋值给phead。

phead->next = phead;
phead->prev = phead;

• 构造循环结构：将头节点的next指针和prev指针都指向自己（即phead），从而形成一个循环结构。在这种情况下，尽管链表中只有一个节点，但它既是头节点也是尾节点，并形成了一个自引用的循环，这样在后续对链表进行操作时（例如插入或删除节点）可以简化边界条件的处理。

最后，函数返回初始化完成的头节点指针phead，标志着一个空的循环双链表已经创建完成。当向这个链表中添加新的节点时，新节点可以被插入到phead节点的前面或后面，同时维护循环双链表的特性。

---

头插

//头插
void List_Header(listcode* phead, LTDataType x) {
	assert(phead);
	//申请一个节点
	listcode* newnode = inaugurate(x);
 
	//先讲新节点的链接(prev  next)
	newnode->next = phead->next;
	newnode->prev = phead;
	//再讲其他与newnode链接
	phead->next->prev = newnode;
	phead->next = newnode;
}

解析

List_Header函数用于在已知的循环双链表phead的头部插入一个新节点，新节点的数据值为x。具体步骤如下：

1. 首先，通过调用inaugurate(x)函数创建一个新节点，并将其数据域设置为输入的值x，得到新节点的指针newnode。

2. 接下来，设置新节点的指针。由于要将新节点插入到头节点之前成为新的头节点，因此将新节点newnode的next指针指向原头节点phead的下一个节点（即原本的头节点之后的第一个节点），将newnode的prev指针指向原头节点phead。

3. 然后更新原链表节点的指针以适应新节点的插入。首先，原头节点的下一个节点（即phead->next）的prev指针应改为指向新节点newnode，这样就完成了新节点与原链表中第二个节点之间的连接。

4. 最后，修改原头节点phead的next指针，使其指向新节点newnode，这样新节点就成为了整个循环双链表的新头节点。

---

尾插

//尾插
void List_Tail(listcode* phead, LTDataType x) {
	assert(phead);
	//申请节点
	listcode* newnode = inaugurate(x);
	//先讲新节点的链接(prev  next)
	newnode->prev = phead->prev;
	newnode->next = phead;
	//改变最后一个节点
	phead->prev->next = newnode;
	//改变头节点
	phead->prev = newnode;
}

解析

List_Tail函数用于在已知的循环双链表phead的尾部插入一个新节点，新节点的数据值为x。以下是详细的文字解析：

1. 首先，通过调用inaugurate(x)函数创建一个新节点，并将其数据域设置为输入的值x，得到新节点的指针newnode。

2. 设置新节点的指针以插入到尾部。由于这是一个循环链表，尾节点的next指向头节点，所以将新节点newnode的prev指针指向原头节点phead的前一个节点（即原本的尾节点），将newnode的next指针指向原头节点phead。

3. 更新原链表尾节点的指针，使其next指针指向新节点newnode，这样新节点就被正确地链接到链表的末尾。

4. 最后，调整原头节点phead的prev指针，使其指向新节点newnode，确保链表的循环特性仍然保持，即尾节点的next始终指向头节点。

---

头删

void List_Header_del(listcode* phead) {
	assert(phead && phead->next != phead);//phead->next != null代表我们的链表就只有哨兵
 
	//存储一下我们的第一个有效位
	listcode* tmp = phead->next;
	//改变第二个有效位(prev)
	tmp->next->prev = phead;
	//改变哨兵(next)
	phead->next = tmp->next;
	free(tmp);
	tmp = NULL;
}

解析

List_Header_del函数用于删除循环双链表phead头部的有效节点（非哨兵节点）。以下是详细的文字解析：

1. 首先，通过assert语句确认phead不为空并且phead->next不等于phead。这实际上是在验证链表中至少存在一个有效节点，因为phead->next等于phead仅在链表为空或者只包含一个哨兵节点时成立。

2. 定义一个临时指针tmp，用来保存待删除的头节点（第一个有效节点）的地址，即tmp = phead->next。

3. 更新待删除节点后面的节点（即第二个有效节点），使其prev指针指向原头节点phead，这样维持了链表的连贯性。

4. 修改原头节点phead的next指针，让它指向待删除节点（原头节点后的一个节点），这样新的头节点就变成了原来头节点的下一个节点。

5. 使用free(tmp)释放掉不再需要的原头节点的内存空间，防止内存泄漏。

6. 将临时指针tmp置为NULL，虽然在这个函数内部不是必须的，但在某些编程习惯中，为了清晰地表示tmp不再指向有效的内存区域，也会进行这样的操作。

---

尾删

//尾删
void List_Tail_del(listcode* phead) {
	assert(phead && phead->next != phead);
 
	listcode* tmp = phead->prev;
	
	tmp->prev->next = phead;
	phead->prev = tmp->prev;
 
	free(tmp);
	tmp = NULL;
}

解析

List_Tail_del函数用于删除循环双链表phead尾部的有效节点（非哨兵节点）。以下是详细的文字解析：

1. 首先，通过assert语句确认phead不为空并且phead->next不等于phead，确保链表中至少有一个有效节点存在。

2. 定义一个临时指针tmp，指向当前尾节点，即tmp = phead->prev。

3. 更新尾节点前一个节点（即倒数第二个节点），使其next指针指向原头节点phead，这样切断了原尾节点与链表的连接，并使新的尾节点成为原尾节点的前一个节点。

4. 调整原头节点phead的prev指针，使其指向原尾节点的前一个节点（现在的新尾节点），保持链表的循环特性。

5. 使用free(tmp)释放原尾节点的内存空间，避免内存泄漏。

6. 将临时指针tmp置为NULL，同样是为了在某些编程风格中清晰地表示tmp不再指向有效的内存区域。

---

pos之后插入

//pos之后插入
void Pos_tail_del(listcode* pos, LTDataType x) {
	assert(pos);
	listcode* newnode = inaugurate(x);
 
	//改变newnode指向
	newnode->next = pos->next;
	newnode->prev = pos;
	//改变pos指向
	pos->next->prev = newnode;//pos的下一个节点的prev
	pos->next = newnode;
 
}

解析

Pos_tail_del函数名称似乎有误，应该是Pos_insert，表示在某个特定位置pos之后插入新节点。以下是详细的文字解析：

1. 首先，通过assert语句确认pos不为空，确保我们有一个合法的位置来插入新节点。

2. 调用inaugurate(x)函数创建一个新节点，并将其数据域设置为输入的值x，得到新节点的指针newnode。

3. 设置新节点的指针以便插入到pos节点之后。将新节点newnode的next指针指向pos节点的下一个节点，将newnode的prev指针指向pos节点。

4. 更新原链表中pos节点的下一个节点，将其prev指针指向新节点newnode，建立新节点与pos节点后继节点间的连接。

5. 最后，修改pos节点的next指针，使其指向新节点newnode，完成新节点在链表中的插入操作。

---

pos删除

//pos删除
void Pos_del(listcode* pos) {
	assert(pos);
 
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}

解析

Pos_del函数用于删除循环双链表中指定位置的节点pos。以下是详细的文字解析：

1. 首先，通过assert语句确认pos不为空，确保我们试图删除的是一个存在的节点。

2. 更新pos节点的后继节点，使其prev指针指向pos节点的前驱节点，这样就断开了pos节点与其后继节点之间的连接。

3. 同样地，更新pos节点的前驱节点，使其next指针指向pos节点的后继节点，这样就完成了pos节点与其前驱节点之间的连接调整。

4. 使用free(pos)释放pos指向的节点内存，防止内存泄漏。

5. 将pos指针设为NULL，虽然在这段代码中并非必要操作，但在某些编程实践中，这样做有助于明确标识pos不再指向有效的内存地址，以免后续误用。

---

打印

 
//打印
void List_print(listcode* phead) {
	assert(phead);
	listcode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->val);
		pcur = pcur->next;
	}
	printf("\n");
}

解析

List_print函数用于打印循环双链表中所有节点的数据值，以下是详细的文字解析：

1. 首先，通过assert语句确认phead不为空，确保链表存在。

2. 初始化一个指向当前节点的指针pcur，将其设置为头节点的下一个节点（因为头节点可能是哨兵节点，我们需要从第一个有效数据节点开始打印）。

3. 使用while循环遍历链表，直到再次回到头节点为止。在循环体内，每次迭代都会打印当前节点pcur的数据值，这里通过printf("%d->", pcur->val);实现。

4. 在每次循环迭代结束后，将pcur指针移动到下一个节点，即pcur = pcur->next;。

5. 当pcur再次指向头节点时，循环结束，此时所有的节点数据值已经按照顺序打印完毕。

6. 循环结束后，打印换行符\n，使得输出结果更易于阅读。

---

全部代码展示

main.c

 
#define _CRT_SECURE_NO_WARNINGS 1
#include"text.h"
 
int main() {
	listcode* p = initialize();//初始化了一个哨兵位
	//listcode* p = NULL;//初始化了一个哨兵位
	//initialize(&p);
	/*List_Header(p,1);
	List_print(p);
	List_Header(p,2);
	List_print(p);
	List_Header(p, 3);
	List_print(p);*/
	///*List_Header(p, 4);
	//List_print(p);
	//List_Tail(p, 10);
	//List_print(p);*/
	//List_Header_del(p);
	//List_print(p);
	//List_Header_del(p);
	//List_print(p);
 
	/*List_Tail(p, 1); 
	List_Tail(p, 2); */
	//List_Tail(p, 3);
	//List_print(p);
	List_Tail(p, 2);
	List_Tail(p, 2);
	List_Tail(p, 2);
	List_print(p);
	/*List_Tail_del(p);
	List_print(p);*/
	listcode* pos = find(p, 2);
	Pos_tail_del(pos, 10);
	List_print(p);
	Pos_del(pos);
	pos = NULL;
		List_print(p);
}

text.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"text.h"
 
//内存开辟
listcode* inaugurate(LTDataType x) {
	listcode* list = (listcode*)malloc(sizeof(listcode));
	if (list == NULL)
	{
		perror("malloc");
		exit(1);
	}
	//初始值
	list->val = x;
	list->next = list->prev = NULL;
 
	return list;
}
 
 
 
//初始化
listcode* initialize() {
	listcode* phead = inaugurate(0);
	phead->next = phead;
	phead->prev = phead;
	return phead;
}
 
//void initialize(listcode** phead) {
//
//	*phead = inaugurate(0);
//}
 
//头插
void List_Header(listcode* phead, LTDataType x) {
	assert(phead);
	//申请一个节点
	listcode* newnode = inaugurate(x);
 
	//先讲新节点的链接(prev  next)
	newnode->next = phead->next;
	newnode->prev = phead;
	//再讲其他与newnode链接
	phead->next->prev = newnode;
	phead->next = newnode;
}
 
//尾插
void List_Tail(listcode* phead, LTDataType x) {
	assert(phead);
	//申请节点
	listcode* newnode = inaugurate(x);
	//先讲新节点的链接(prev  next)
	newnode->prev = phead->prev;
	newnode->next = phead;
	//改变最后一个节点
	phead->prev->next = newnode;
	//改变头节点
	phead->prev = newnode;
}
 
//头删
void List_Header_del(listcode* phead) {
	assert(phead && phead->next != phead);//phead->next != null代表我们的链表就只有哨兵
 
	//存储一下我们的第一个有效位
	listcode* tmp = phead->next;
	//改变第二个有效位(prev)
	tmp->next->prev = phead;
	//改变哨兵(next)
	phead->next = tmp->next;
	free(tmp);
	tmp = NULL;
}
 
//尾删
void List_Tail_del(listcode* phead) {
	assert(phead && phead->next != phead);
 
	listcode* tmp = phead->prev;
	
	tmp->prev->next = phead;
	phead->prev = tmp->prev;
 
	free(tmp);
	tmp = NULL;
}
 
//查找函数
listcode* find(listcode* phead, LTDataType x) {
 
	listcode* pcur = phead->next;
	while (pcur != phead)
	{
		if (pcur->val == x) {//直接遍历比较
			return pcur;
		}
		pcur = pcur->next;
	}
	return NULL;
}
 
//pos之后插入
void Pos_tail_del(listcode* pos, LTDataType x) {
	assert(pos);
	listcode* newnode = inaugurate(x);
 
	//改变newnode指向
	newnode->next = pos->next;
	newnode->prev = pos;
	//改变pos指向
	pos->next->prev = newnode;//pos的下一个节点的prev
	pos->next = newnode;
 
}
//pos删除
void Pos_del(listcode* pos) {
	assert(pos);
 
	pos->next->prev = pos->prev;
	pos->prev->next = pos->next;
	free(pos);
	pos = NULL;
}
 
//打印
void List_print(listcode* phead) {
	assert(phead);
	listcode* pcur = phead->next;
	while (pcur != phead)
	{
		printf("%d->", pcur->val);
		pcur = pcur->next;
	}
	printf("\n");
}
 
 
 
void List_Destroyed(listcode* phead) {
	assert(phead);
	listcode* pcur = phead->next;
	
	while (pcur != phead) {
		listcode* tmp = pcur->next;
		free(pcur);
		pcur = tmp;
	}
	free(phead);
	phead = NULL;
}

text.h

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
//#include<vld.h>
 
typedef int LTDataType;
//创建链表结构
typedef struct liatcode
{
	LTDataType val;//内容
	struct liatcode* next;//指向下一个元素
	struct liatcode* prev;//指向上一个元素
}listcode;
 
 
 
  
//初始化
listcode* initialize();
//头插
void List_Header(listcode* phead, LTDataType x);
//尾插
void List_Tail(listcode* phead, LTDataType x);
//头删
void List_Header_del(listcode* phead);
//尾删
void List_Tail_del(listcode* phead);
//pos之后插入
void Pos_tail_del(listcode* pos, LTDataType x);
//pos删除
void Pos_del(listcode* pos);
//打印
void List_print(listcode* phead);
 
//销毁
void List_Destroyed(listcode* phead);
 
listcode* find(listcode* phead, LTDataType x);

总结来说，双链表作为一种灵活、高效的线性数据结构，通过引入前驱和后继指针，极大地提升了数据操作的便利性和效率，是程序设计中不可或缺的一部分。在编写代码实现时，理解和掌握双链表的工作原理及其相关操作至关重要。