初阶数据结构之双向链表详解

目录

一：双向链表的概念

1.什么是双向链表？

2.双向链表的优点

3.双向链表的结构

二：双向链表的实现

1.定义链表结点

2.初始化双向链表

3.添加结点

4.尾插

5.头插

6.打印双向链表

7.查找链表结点

8.在指定结点后插入新结点

9.删除指定链表结点

10.头删

11.尾删

12.销毁双向链表

三：代码综合

1.List.h:

2.List.c

3.test.c

---

开门见山，直接开始讲解。

如果内容对你有所帮助，不妨点个赞再走。（如果有错误请指出，一定改正）

                     

一：双向链表的概念

1.什么是双向链表？

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表，因此，本节的双向链表也是双向循环链表。

2.双向链表的优点

1、双向性：双链表支持在每个节点上存储前驱节点和后继节点的指针，使得在任何节点上都可以方便地找到其前驱节点和后继节点。而单链表只能通过遍历整个链表来查找特定节点的下一个节点或上一个节点，效率较低。

2、插入和删除操作更高效：由于双链表支持双向链接，因此在插入和删除操作中，双链表只需要重新调整相关的指针即可，而不需要像单链表那样需要遍历整个链表。这使得双链表的插入和删除操作更高效。

3、内存利用率更高：双向链表每个节点存储了前驱节点和后继节点的指针，因此可以更充分地利用内存空间。相比之下，单链表每个节点只存储了一个指向下一个节点的指针，内存利用率相对较低。

3.双向链表的结构

图示：

头结点head的prev的指针指向d3，d3的next指针指向head。

同时，无头单向非循环链表和带头双向循环链表也是我们平时最常用的链表结构。

接下来，我们来聊聊双向链表的实现

二：双向链表的实现

在进行链表的实现时，我们把函数的声明放在List.h中，在List.c中实现，在test.c中调用。

1.定义链表结点

在List.h中定义链表结点，data的类型设为DataType,方便以后使用其他类型的数据。

typedef int DataType;
typedef struct ListNode
{
	DataType data;
	struct ListNode* prev;
	struct ListNode* next;
 
}ListNode;

2.初始化双向链表

初始化链表就是为链表设置一个头结点，头结点内不存储有效数据，只在链表中充当哨兵位的作用，然后把头结点的的prev指针和next指针都指向自己。

传递二级指针的原因是需要把头结点指针的指向改为指向新开辟空间的地址，因为是对地址进行操作，因此要传递二级指针。

//双向链表初始化
void InitList(ListNode** head)
{
	*head = (ListNode*)malloc(sizeof(ListNode));
	if (*head == NULL)
	{
		perror("malloc");
		exit(1);
	}
	(*head)->data = 1;
	(*head)->prev = *head;
	(*head)->next = *head;
}

 运行结果：

3.添加结点

添加链表结点添加链表结点其实就是把非结点结构的数据转换为结点类型的数据，在链表插入新节点时使用。

//添加结点
ListNode* BuyNode(DataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->prev = newnode;
	newnode->next = newnode;
	return newnode;
}

4.尾插

代码展示：

//尾插
void PushBack(ListNode* head, DataType x)
{
	ListNode* newnode = BuyNode(x);
	newnode->next = head;
	newnode->prev = head->prev;
	head->prev->next = newnode;
	head->prev = newnode;
}

当传过来的x为2时，运行结果：

5.头插

代码展示：

//头插
void PushFront(ListNode* head, DataType x)
{
	ListNode* newnode = BuyNode(x);
	newnode->next = head->next;
	newnode->prev = head;
	head->next->prev = newnode;
	head->next = newnode;
 
}

6.打印双向链表

代码展示：

//打印双向链表
void PrintList(ListNode* head)
{
	assert(head && head->next);//判断链表的哨兵位和下一个结点是否为空
	ListNode* tail = head->next;
	while (tail != head)
	{
		printf("%d->", tail->data);
		tail = tail->next;
	}
	printf("\n");
}

 在上面我们已经进行过尾插和头插的操作，让我们打印出来此时链表中的内容为：

7.查找链表结点

//查找结点
ListNode* FindNode(ListNode* head, DataType x)
{
	assert(head && head->next);
	ListNode* tail = head->next;
	while (tail != head)
	{
		if (tail->data == x)
		{
			return tail;
		}
		tail = tail->next;
	}
}

8.在指定结点后插入新结点

需要先使用FindNode函数查找指定结点，再把x转换为链表类型，最后插入。

//在指定结点后面插入结点
void InsertNode(ListNode* head, DataType a, DataType x)
{
	assert(head && head->next);
	ListNode* pos = FindNode(head,a);
	ListNode* newnode = BuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}

假设a为3，x为6时，运行结果为：

9.删除指定链表结点

删除链表结点要先用FindNode查找结点的地址,然后再进行删除。

//删除指定结点
void DelNode(ListNode* head, DataType x)
{
	assert(head && head->next);
	ListNode* pos = FindNode(head,x);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}

假设删除的数据x为3，则运行结果为：

事实证明，我们删除成功了。

10.头删

代码展示：

//头删
void DelFront(ListNode* head)
{
	assert(head && head->next);
	ListNode* first = head->next;
	first->next->prev = head;
	head->next = first->next;
	free(first);
	first = NULL;
}

运行结果：

 头删成功。

11.尾删

//尾删
void DelBack(ListNode* head)
{
	assert(head && head->next);
	ListNode* back = head->prev;
	back->prev->next = head;
	head->prev = back->prev;
}

运行结果：

此时我们的链表中已经没有任何数据了。

12.销毁双向链表

销毁双向链表我们也要传递二级指针，因为在函数操作中也会改变头结点的地址。

//销毁双向链表
void DelList(ListNode** head)
{
	assert(head && *head);
	ListNode* phead = (*head)->next;
	while (phead!=*head)
	{
		ListNode* next = phead->next;创建next指针用来存储下一个结点的地址
		free(phead);
		phead = next;
	}
    free(*head);
	*head=NULL;
}

至此，双向链表的实现全部完成。

三：代码综合

1.List.h:

#pragma once
#include<stdio.h>
#include<stdlib.h>
#include<assert.h>
 
typedef int DataType;
typedef struct ListNode
{
	DataType data;
	struct ListNode* prev;
	struct ListNode* next;
 
}ListNode;
 
//双向链表初始化
void InitList(ListNode** head);
 
//添加结点
ListNode* BuyNode(DataType x);
 
//尾插结点
void PushBack(ListNode*head,DataType x);
 
//头插结点
void PushFront(ListNode* head, DataType x);
 
//打印双向链表
void PrintList(ListNode* head);
 
//查找结点
ListNode* FindNode(ListNode* head, DataType x);
 
//指定结点后面插入结点
void InsertNode(ListNode* head,DataType a, DataType x);
 
//删除指定结点
void DelNode(ListNode* head, DataType);
 
//头删
void DelFront(ListNode* head);
 
//尾删
void DelBack(ListNode* head);
 
//销毁双向链表
void DelList(ListNode** head);

2.List.c

#include"List.h"
 
//双向链表初始化
void InitList(ListNode** head)
{
	*head = (ListNode*)malloc(sizeof(ListNode));
	if (*head == NULL)
	{
		perror("malloc");
		exit(1);
	}
	(*head)->data = 1;
	(*head)->prev = *head;
	(*head)->next = *head;
}
 
//添加结点
ListNode* BuyNode(DataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc");
		return NULL;
	}
	newnode->data = x;
	newnode->prev = newnode;
	newnode->next = newnode;
	return newnode;
}
 
//尾插
void PushBack(ListNode* head, DataType x)
{
	ListNode* newnode = BuyNode(x);
	newnode->next = head;
	newnode->prev = head->prev;
	head->prev->next = newnode;
	head->prev = newnode;
 
}
 
//头插
void PushFront(ListNode* head, DataType x)
{
	ListNode* newnode = BuyNode(x);
	newnode->next = head->next;
	newnode->prev = head;
	head->next->prev = newnode;
	head->next = newnode;
 
}
 
//打印双向链表
void PrintList(ListNode* head)
{
	assert(head && head->next);
	ListNode* tail = head->next;
	while (tail != head)
	{
		printf("%d->", tail->data);
		tail = tail->next;
	}
	printf("\n");
}
 
//查找结点
ListNode* FindNode(ListNode* head, DataType x)
{
	assert(head && head->next);
	ListNode* tail = head->next;
	while (tail != head)
	{
		if (tail->data == x)
		{
			return tail;
		}
		tail = tail->next;
	}
}
 
//在指定结点后面插入结点
void InsertNode(ListNode* head, DataType a, DataType x)
{
	assert(head && head->next);
	ListNode* pos = FindNode(head,a);
	ListNode* newnode = BuyNode(x);
	newnode->next = pos->next;
	newnode->prev = pos;
	pos->next->prev = newnode;
	pos->next = newnode;
}
 
//删除指定结点
void DelNode(ListNode* head, DataType x)
{
	assert(head && head->next);
	ListNode* pos = FindNode(head,x);
	pos->prev->next = pos->next;
	pos->next->prev = pos->prev;
	free(pos);
	pos = NULL;
}
 
//头删
void DelFront(ListNode* head)
{
	assert(head && head->next);
	ListNode* first = head->next;
	first->next->prev = head;
	head->next = first->next;
	free(first);
	first = NULL;
}
 
//尾删
void DelBack(ListNode* head)
{
	assert(head && head->next);
	ListNode* back = head->prev;
	back->prev->next = head;
	head->prev = back->prev;
}
 
//销毁双向链表
void DelList(ListNode** head)
{
	assert(head && *head);
	ListNode* phead = (*head)->next;
	while (phead!=*head)
	{
		ListNode* next = phead->next;
		free(phead);
		phead = next;
	}
	free(*head);
	*head =NULL;
}

3.test.c

#include"List.h"
int main()
{
	ListNode* head=NULL;
	//初始化
	InitList(&head);
 
	//尾插
	PushBack(head, 2);
	printf("%d", head->next->data);
 
	//头插
	PushFront(head, 3);
	printf("%d\n", head->next->data);
 
	//打印链表
	PrintList(head);
 
	//查找结点
	ListNode* node = FindNode(head, 3);
 
	//指定结点后面插入新节点
	InsertNode(head, 3, 6);
	PrintList(head);
 
	//删除指定结点
	DelNode(head, 3);
	PrintList(head);
 
	//头删
	DelFront(head);
	PrintList(head);
 
	//尾删
	DelBack(head);
	PrintList(head);
 
	//销毁双向链表
	DelList(&head);
	PrintList(head);
 
}

完结撒花。