【数据结构】单链表和双向循环链表_单链表双向链表循环链表 二级指针

前言

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表
中的指针链接次序实现的，结构如图所示：

注意:
①从上图可看出，链式结构在逻辑上是连续的，但是在物理上不一定连续
②现实中的结点一般都是从堆上申请出来的
③从堆上申请的空间，是按照一定的策略来分配的。两次申请的空间可能连续，也可能不连续

与此同时，链表种类也有很多，包括单链表和双向链表、带头结点的链表或不带头结点的链表、循环链表和非循环链表，其中最常用的就是单链表和双向循环链表，原因如下：
①无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
②带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单。下面开始讲解这两种链表结构：

单链表

单链表的功能接口如下：

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
#include <stdbool.h>
typedef int SLTDataType;
typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode;

void SListPrint(SLTNode* phead);//打印

void SListDestroy(SLTNode** pphead);//销毁

SLTNode* BuySLTNode(SLTDataType x);//申请一个新结点

void SListPushHead(SLTNode** pphead, SLTDataType x);//头插

void SListPushBack(SLTNode** pphead, SLTDataType x);//尾插

void SListPopHead(SLTNode** pphead);//头删

void SListPopTail(SLTNode** pphead);//尾删

SLTNode* SListFind(SLTNode* phead, SLTDataType x);//表面是查找功能，其实还可以充当修改数据的接口

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);//插入接口，在头尾插入时可借助头插or尾插接口

void SListInsertBack(SLTNode** pphead, SLTNode* pos, SLTDataType x);//尾部插入，由于单链表的尾插效率较低，因此单独写一个接口实现功能

void SListEraseBack(SLTNode** pphead, SLTNode* pos);//删除接口，实现后可根据参数改变实现头删和尾删

//由于单链表在为空时只有一个空指针，因此并没有链表初始化的接口。
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

单链表打印

void SListPrint(SLTNode* phead)
{
	//assert(phead);不用断言，链表中头指针可能为空。
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->",cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11

由于链表可能为空，因此打印函数处的指针不用断言非空，然后判断cur指针是否为NULL进行打印即可，最后在加上NULL指针使打印出来的链表更加直观。

单链表销毁

void SListDestroy(SLTNode** pphead)
{
	assert(pphead);
	SLTNode* cur = *pphead;
	while (cur)
	{
		SLTNode* next = cur->next;
		free(cur);
		cur = next;
	}
	*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

这里我们将链表指针的地址传入以进行操作。
先创建一个指针指向链表头，在他非空的条件下进行循环头删，最后将头指针置空完成销毁。

申请单链表结点

SLTNode* BuySLTNode(SLTDataType x)
{
	SLTNode* newnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;

	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

这里的返回类型为结点指针，因此我们要将申请的结点返回回去，所以要在堆上申请节点。然后将准备好的数值植入新结点中，将其next指针置空并返回该结点。（记得判断malloc函数是否申请空间成功哦~）

单链表头插

void SListPushHead(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
1
2
3
4
5
6
7
8

在单链表的头部操作还是比较方便的，我们先申请一个结点，将其next指针指向第一个结点，然后再将其本身改为第一个结点即可实现头插。注意，这里我们也是使用了二级指针，访问头结点时要记得解引用。

单链表尾插

void SListPushBack(SLTNode** pphead, SLTDataType x)
{
	assert(pphead);

	SLTNode* newnode = BuySLTNode(x);

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

我们先申请好新结点，然后判断当前链表是否为空，如果为空，则该结点为第一个结点，将*pphead指向它，当前链表若不为空相对来说就比较麻烦，需要先通过头指针进行遍历找到链表最后一个结点，然后使最后一个结点的next指向新结点。而且我们在创建新结点是，其next指针默认就是指向空的，因此不需要再管新结点的next指针。

单链表头删

void SListPopHead(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* tmp = *pphead;
	*pphead = (*pphead)->next;
	free(tmp);
	tmp = NULL;
}
1
2
3
4
5
6
7
8
9

因为要删除，所以要先断言链表不为空，然后定义一个替身指针将其指向要删除的结点，然后使头结点指向其下一个节点，free掉替身结点，即可完成单链表头删。不难看出，单链表的头部操作相对而言还是比较简单的。

单链表尾删

void SListPopTail(SLTNode** pphead)
{
	assert(pphead && *pphead);

	SLTNode* tmp1 = *pphead;
	SLTNode* tmp2 = (*pphead)->next;
	if (tmp2 == NULL)
	{
		*pphead = NULL;
		free(tmp1);
	}
	else
	{
		while (tmp2->next != NULL)
		{
			tmp1 = tmp1->next;
			tmp2 = tmp2->next;
		}
		tmp1->next = NULL;
		free(tmp2);
		tmp2 = NULL;
	}
	
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

断言链表不为空后，创建两个指针，分别指向头结点及其下一个节点，若第二个指针为空，说明当前链表中只有一个元素，删除后链表变为空指针；若不满足第二个指针为空，则两个指针一起向后移动，直至满足第二个指针为空为止，然后将第一个指针的next指针指向NULL，free掉第二个指针指向的结点，即可完成尾删。

单链表查找元素

SLTNode* SListFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

其实就是遍历单链表，寻找只是为后续某些操作做铺垫的，例如删除或修改元素。

单链表在pos位置前插入元素

void SListInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && pos);
	if (pos == *pphead)
	{
		SListPushHead(pphead, x);
	}
	else
	{
		SLTNode* tmp = *pphead;
		while (tmp->next != pos)
		{
			tmp = tmp->next;
		}

		SLTNode* newnode = BuySLTNode(x);
		newnode->next = pos;
		tmp->next = newnode;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

插入前先判断是否为头插，若为头插，就直接调用头插接口。否则创建一个tmp变量寻找pos位置，而后对pos进行头插。

单链表在pos位置后尾插

void SListInsertBack(SLTNode** pphead, SLTNode* pos, SLTDataType x)
{
	assert(pphead && pos);

	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6
7
8

在这里我们是默认链表中最少有一个元素的，然后申请新结点将其插入pos之后。

单链表删除pos位置后面的一个元素

void SListEraseBack(SLTNode** pphead, SLTNode* pos)
{
	assert(pphead && pos);
	assert(pos->next);
	SLTNode* tmp = pos->next;
	pos->next = pos->next->next;
	free(tmp);
	tmp = NULL;
}
1
2
3
4
5
6
7
8
9

顾名思义，我们还要先保证pos位置之后是有元素的，所以我们断言一下。然后就是尾删过程，用一个指针变量记录要删除的元素，使pos指向它的下下个，free掉要删除的结点。

双向循环链表

双向循环链表的功能接口如下：

#pragma once
#include <stdio.h>
#include <assert.h>
#include <stdlib.h>
#include <stdbool.h>

typedef int LTDataType;

typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType data;
}LTNode;

//void ListInit(LTNode** pphead);
LTNode* ListInit();//为保证类型一致，初始化链表时我们选择返回一个空链表，而不再传入二级指针进行初始化
void ListDestory(LTNode* phead);//链表销毁

void ListPrint(LTNode* phead);//链表打印

void ListPushBack(LTNode* phead, LTDataType x);//链表尾插

void ListPushFront(LTNode* phead, LTDataType x);//链表头插

void ListPopBack(LTNode* phead);//链表尾删

void ListPopFront(LTNode* phead);//链表头删

bool ListEmpty(LTNode* phead);//链表判空

size_t ListSize(LTNode* phead);//链表长度，因为是循环链表，判断比较特殊

LTNode* ListFind(LTNode* phead, LTDataType x);//链表元素查找

// pos前插入
void ListInsert(LTNode* pos, LTDataType x);
// pos位置删除
void ListErase(LTNode* pos);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

链表初始化

LTNode* ListInit()
{
	LTNode* guard = (LTNode*)malloc(sizeof(LTNode));
	if (guard == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	guard->next = guard;
	guard->prev = guard;

	return guard;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

因为双向循环链表是带有头结点的，因此初始化就是申请一个头结点，将头结点的next指针指向他本身，prev指针也指向其本身。

链表新结点创建

LTNode* BuyListNode(LTDataType x)
{
	LTNode* node = (LTNode*)malloc(sizeof(LTNode));
	if (node == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	node->next = NULL;
	node->prev = NULL;
	node->data = x;
	return node;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

与单链表类似，只是多一个prev指针需要初始化。

链表打印

void ListPrint(LTNode* phead)
{
	assert(phead);
	printf("phead<=>");
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		printf("%d<=>", cur->data);
		cur = cur->next;
	}
	printf("\n");
}
1
2
3
4
5
6
7
8
9
10
11
12

因为此链表为循环链表，因此遍历的结束条件不能是NULL，而是要从头结点的下一个开始遍历，直至cur指针指向头结点位置算完成一次遍历。

链表尾插

void ListPushBack(LTNode* phead, LTDataType x)
{
	assert(phead);

	/*LTNode* newnode = BuyListNode(x);
	LTNode* tail = phead->prev;

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;*/

	ListInsert(phead, x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

因为双向循环且有头结点，因此可以直接找到插入位置的前一个结点，也就是phead->prev，然后将新结点插入并修改指针即可，在完成了插入元素接口的实现后，可直接调用插入接口并传入头结点。（因为insert函数是在pos位置前插入，由于链表是循环结构，头结点的前一个就是链表的尾）

链表头插

void ListPushFront(LTNode* phead, LTDataType x)
{
	assert(phead);

	// 先链接newnode 和 phead->next节点之间的关系
	/*LTNode* newnode = BuyListNode(x);
	newnode->next = phead->next;
	phead->next->prev = newnode;

	phead->next = newnode;
	newnode->prev = phead;*/

	ListInsert(phead->next, x);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

头插就是在phead和phead->next之间插入节点，如果不准备备用指针的话，要先连接新结点和非中心结点直接的指针，在连接新结点和中心结点的指针。（中心结点就是指你要在谁的前面或者谁的后面插入，这个要求中围绕的指针即为中心指针）

链表尾删

void ListPopBack(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));

	//LTNode* tail = phead->prev;
	//LTNode* prev = tail->prev;

	//prev->next = phead;
	//phead->prev = prev;
	//free(tail);
	//tail = NULL;

	ListErase(phead->prev);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

删前先判断链表是否为空，然后创建两个指针分别指向要删除的结点和该结点的前一个结点，后续操作和单链表相同，但最大的区别就是找删除结点的前一个结点比单链表容易得多。

链表头删

void ListPopFront(LTNode* phead)
{
	assert(phead);
	assert(!ListEmpty(phead));
	/*LTNode* first = phead->next;
	LTNode* second = first->next;

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

	free(first);
	first = NULL;*/
	ListErase(phead->next);
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

头删也很简单，注意判断链表非空就好。

链表判空

bool ListEmpty(LTNode* phead)
{
	assert(phead);
	return phead->next == phead;
}
1
2
3
4
5

一行代码，若phead的next指向自己，表达式为1，链表为空，否则表达式为0，链表非空。

链表长度

size_t ListSize(LTNode* phead)
{
	assert(phead);

	size_t n = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		++n;
		cur = cur->next;
	}

	return n;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

和打印一样，要从头结点的下一个开始遍历，直至遍历一遍回到头结点，求出链表长度。

查找链表中元素

LTNode* ListFind(LTNode* phead, LTDataType x)
{
	assert(phead);

	size_t n = 0;
	LTNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->data == x)
		{
			return cur;
		}

		cur = cur->next;
	}

	return NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

在链表pos位置前插入元素

void ListInsert(LTNode* pos, LTDataType x)
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* newnode = BuyListNode(x);

	// prev newnode pos;
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

老规矩，先和pos位置的前一个结点建立联系，再连接newnode和pos位置结点。

删除pos位置的元素

void ListErase(LTNode* pos)
{
	assert(pos);

	LTNode* prev = pos->prev;
	LTNode* next = pos->next;

	prev->next = next;
	next->prev = prev;
	free(pos);
	//pos = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12

链表销毁

void ListDestory(LTNode* phead)
{
	assert(phead);

	LTNode* cur = phead->next;
	while (cur != phead)
	{
		LTNode* next = cur->next;
		free(cur);
		cur = next;
	}

	free(phead);
	//phead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

结语

以上就是关于单链表和双向循环链表的实现方式，如有不足或遗漏之处还请大家指正，笔者感激不尽；同时也欢迎大家在评论区进行讨论，一起学习，共同进步！