[数据结构]——链表详解

[数据结构]——链表详解

1.什么是链表？链表的概念及结构

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

注意：

1.链式结构在逻辑上是连续的，但在物理上不一定连续

2.现实中的结点一般都是从堆上申请出来的

3.从堆上申请的空间，是按照一定的策略来分配的，两次申请的空间可能连续，也可能不连续

2.链表的分类

实际中链表的结构非常多样，以下的情况组合起来就有8种链表结构

1.单向或者双向

2.带头或者不带头

3.循环或者非循环

虽然有这么多的链表的结构，但是我们实际中最常用的还是两种结构

1.无头单向非循环链表

2.带头双向循环链表

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了。

3.单链表的实现（增删查改）

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

void SLNodePrint(SLNode* phead);

SLNode* BuySLNode(SListNodeType x);

void SLNodePushFront(SLNode* pphead, SListNodeType x);

void SLNodePushBack(SLNode** pphead, SListNodeType x);

void SLNodePopBack(SLNode** pphead);

void SLNodePopFront(SLNode** pphead);

void SListDestory(SLNode** pphead);

SLNode* SListFind(SLNode* phead, SListNodeType x);

void SListInsert(SLNode** pphead, SLNode* pos, SListNodeType x);

void SListInsertAfter(SLNode* pos, SListNodeType x);
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

1）链表的初始化

void SLNodeInit(SLNode* phead)
{
    phead->data=0;
    phead->next=NULL;
}
1
2
3
4
5

2）动态申请一个结点

//新创建一个结构体空间，存放新输入的数据
SLNode* BuySLNode(SListNodeType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	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

3）单链表尾插

//在链表最后端插入一个数据
void SLNodePushBack(SLNode** pphead, SListNodeType x)
{
	SLNode* newnode = BuySLNode(x);
	/*1.整个链表为空*/
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	/*2.链表不为空*/
	else
	{
		SLNode* cur = *pphead;
		while (cur->next != NULL)
		{
			cur = cur->next;
		}
		newnode = cur->next;
	}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

4）单链表头插

//在链表最前端插入一个数据
void SLNodePushFront(SLNode** pphead, SListNodeType x)
{
	assert(pphead);
	SLNode* newnode=BuySLNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
1
2
3
4
5
6
7
8

5）单链表尾删

//删除链表最后端的数据
void SLNodePopBack(SLNode** pphead)
{
	/*1.链表为空*/
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	/*2.链表不为空*/
	else
	{
		SLNode* cur = *pphead;
		SLNode* prev = NULL;
		while (cur->next != NULL)
		{
			prev = cur;
			cur = cur->next;
		}
		prev->next = NULL;
		free(cur);
		cur = 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

6）单链表头删

//删除链表最前端的数据
void SLNodePopFront(SLNode** pphead)
{
	assert(pphead);
	SLNode* det = *pphead;
	*pphead = (*pphead)->next;
	free(det);
	det = NULL;
}
1
2
3
4
5
6
7
8
9

7）单链表查找

//在链表中查找某个数据
SLNode* SListFind(SLNode* phead, SListNodeType x)
{
	SLNode* 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
14

8）在单链表中某个位置前插入数据

//在pos前插入一个数据
void SListInsert(SLNode** pphead, SLNode* pos, SListNodeType x)
{
	assert(pphead);
	assert(pos);
	if (pos == *pphead)
	{
		SLNodePushFront(*pphead, x);
	}
	else
	{
		SLNode* cur = *pphead;
		SLNode* newnode = BuySLNode(x);
		while (cur->next != pos)
		{
			cur = cur->next;
		}
		cur->next=newnode;
		newnode->next = pos;
	}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

9）在单链表中某个位置后插入数据

// 在pos后面插入
void SListInsertAfter(SLNode* pos, SListNodeType x)
{
	assert(pos);
	SLNode* newnode = BuySLNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6
7
8

10）销毁单链表

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

4.双向链表的实现

双向链表的原理与单链表类似，双向链表需要两个指针来链接，一个指向前面的，一个指向后面的。同时需要一个head，头链表，方便操作。

#pragma once
#include<stdlib.h>
#include<stdio.h>
#include<assert.h>
#include<stdbool.h>
typedef int LTDataType;
typedef struct ListNode
{
	LTDataType data;
	struct ListNode* prev;
	struct ListNode* next;
}ListNode;

ListNode* ListInit();

ListNode* BuyListNode(LTDataType x);

void ListPushBack(ListNode* phead, LTDataType x);

void ListPushFront(ListNode* phead, LTDataType x);

void ListNodePopBack(ListNode* phead);

void ListNodePopFront(ListNode* phead);

bool ListNodeEmpty(ListNode* phead);

size_t ListNodeSize(ListNode* phead);

void ListNodeInsert(ListNode* pos, LTDataType x);

ListNode* ListNodeFInd(ListNode* phead, LTDataType x);

void ListNodeErase(ListNode* pos);

void ListNodeDestory(ListNode* phead);
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

1）双向链表的初始化

ListNode* ListInit()
{
	ListNode* Guard=(ListNode*)malloc(sizeof(ListNode));
	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

2）动态申请一个结点

ListNode* BuyListNode(LTDataType x)
{
	ListNode* newnode = (ListNode*)malloc(sizeof(ListNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}
	newnode->data = x;
	newnode->next = NULL;
	newnode->prev = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

3）双向链表的尾插

void ListPushBack(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* tail = phead->prev;

	tail->next = newnode;
	newnode->prev = tail;
	newnode->next = phead;
	phead->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10
11

4）双向链表的头插

void ListPushFront(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* newnode = BuyListNode(x);
	ListNode* cur = phead->next;
	phead->next = newnode;
	newnode->prev = phead;
	newnode->next = cur;
	cur->prev= newnode;
}
1
2
3
4
5
6
7
8
9
10

5）双向链表的尾删

void ListNodePopBack(ListNode* phead)
{
	assert(phead);
	assert(!ListNodeEmpty(phead));
	ListNode* tail = phead->prev;
	ListNode* cur = tail->prev;
	cur->next = phead;
	phead -> prev = cur;
	free(tail);
	tail = NULL;
}
1
2
3
4
5
6
7
8
9
10
11

6）双向链表的头删

void ListNodePopFront(ListNode* phead)
{
	assert(phead);
	assert(!ListNodeEmpty(phead));
	ListNode* cur = phead->next;
	ListNode* pe = cur->next;
	phead->next = pe;
	pe->prev = phead;
	free(cur);
	cur = NULL;
}
1
2
3
4
5
6
7
8
9
10
11

7）判断链表是否为空

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

8）双向链表数据的个数

size_t ListNodeSize(ListNode* phead)
{
	size_t n = 0;
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		++n;
		cur = cur->next;
	}
	return n;
}
1
2
3
4
5
6
7
8
9
10
11

9）在双向链表查找数据

ListNode* ListNodeFInd(ListNode* phead, LTDataType x)
{
	ListNode* 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

10）在双向链表中插入一个数据

void ListNodeInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* prev = pos->prev;
	ListNode* newnode = BuyListNode(x);
	prev->next = newnode;
	newnode->prev = prev;
	newnode->next = pos;
	pos->prev = newnode;
}
1
2
3
4
5
6
7
8
9
10

11）在双向链表中删除一个数据

void ListNodeErase(ListNode* pos)
{
	assert(pos);

	ListNode* prev = pos->prev;
	ListNode* 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 ListNodeDestory(ListNode* phead)
{
	assert(phead);

	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* 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

5.顺序表与链表的区别