数据结构之单链表

大家好，我们今天来简单的认识下单链表。

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

单链表就像图中的火车一样，是由一节一节车厢链接起来的，每个车厢都有下一节车厢的节点，也就是我们所说的地址，所以我们的单链表在逻辑上是连续的，但在物理上不一定连续。

链表的实现

构建我们的链表：

typedef struct SListNode
{
	SLNDataType val;
	struct SListNode* next;
}SLNode;

1
2
3
4
5
6
7

接口的实现：

//打印链表
void SLTPrint(SLNode* phead);

void SLTPushBack(SLNode** pphead,SLNDataType x);

void SLTPushFront(SLNode** pphend, SLNDataType x);

void SLTPopBack(SLNode** pphead);
void SLTPopFront(SLNode** pphead);

SLNode* SLTFind(SLNode* phead, SLNDataType x);

// 在pos的前面插入
void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x);

// 删除pos位置
void SLTErase(SLNode** pphead, SLNode* pos);

// 后面插入 后面删除
void SLTInsertAfter(SLNode* pos, SLNDataType x);
void SLTEraseAfter(SLNode* pos);


void SLTDestroy(SLNode** pphead);
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

打印链表：

void SLTPrint(SLNode* phead)
{
	assert(phead);
	SLNode* cur = phead;
	while (cur)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}
1
2
3
4
5
6
7
8
9
10
11

创建一个新节点：

SLNode* CreateNode(SLNDataType x)
{
	SLNode* newnode = (SLNode*)malloc(sizeof(SLNode));
	if (newnode == NULL)
	{
		perror("malloc fail");
		exit(-1);
	}

	newnode->val = x;
	newnode->next = NULL;
	return newnode;
}
1
2
3
4
5
6
7
8
9
10
11
12
13

对节点进行头插：

void SLTPushFront(SLNode** pphead, SLNDataType x)
{
	assert(pphead);
	assert(*pphead);
	SLNode* newnode = CreateNode(x);
	newnode->next = *pphead;
	*pphead = newnode;

}
1
2
3
4
5
6
7
8
9

对节点进行头插，我们要保证我们的链表不为空我们就进行头插，我们头插的节点的下一个节点就指向我们链表的头结点，而我们的头结点就变成我们的新节点。

尾插：

void SLTPushBack(SLNode** pphead, SLNDataType x)
{
	assert(pphead);
	SLNode* newnode = CreateNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		// 找尾
		SLNode* 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

尾插的话我们得先考虑链表为空的情况，如果链表为空的话，我们的头结点就直接为我们要尾插的节点，如果不为空的话我们就要找到尾节点，我们的遍历条件为tail->next！=NULL,而不是tail!=NULL，前者可以找到尾，而后者我们会使得tail为空，从而出现内存泄漏的情况。

头删：

void SLTPopFront(SLNode** pphead)
{
	assert(*pphead);
	SLNode* tmp = *pphead;
	*pphead = (*pphead)->next;
	free(tmp);
}
1
2
3
4
5
6
7

头删比较简单，首先保证它不为空，但是我们直接给它释放的话，我们就找不到下一个节点了，所以我们用一个指针来保存它的节点，在使得它指向它的下一个节点，在给它释放就可以了。

尾删：

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

如果头结点的下一个为空的话，我们就直接给它释放掉就OK了，但是如果不是头结点的话，我们就找到尾节点，在给它释放掉就可以了。

查找链表：

SLNode* SLTFind(SLNode* phead, SLNDataType x)
{
	SLNode* cur = phead;
	while (cur)
	{
		if (cur->val == x)
		{
			return cur;
		}
		else
		{
			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 SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	if (*pphead = pos)
	{
		// 头插
		SLTPushFront(pphead, x);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		SLNode* newnode = CreateNode(x);
		prev->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
22

在pos前面插入就很简单了，如果我们要插入的位置为头结点的话，我们直接进行头插就可以了，而我们的pos不为头节点我们就进行遍历，找到pos的前一个位置，我们让插入的节点的前一个节点指向我们要插入的节点，而我们要插入的结点的下一个节点指向pos节点。

删除pos位置：

void SLTErase(SLNode** pphead, SLNode* pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);

	if (*pphead == pos)
	{
		// 头删
		SLTPopFront(pphead);
	}
	else
	{
		SLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		prev->next = pos->next;
		free(pos);
		pos = 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

这里也一样，如果pos为头结点就进行尾删，如果不为空我们就让pos的前一个节点指向pos的下一个节点就可以了。

pos后面插入：

void SLTInsertAfter(SLNode* pos, SLNDataType x)
{
	assert(pos);
	SLNode* newnode = CreateNode(x);

	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6
7
8

后面插入的情况就比较简单了，我们只要让新节点的下一个指向pos的下一个节点，pos节点的下一个指向新节点就可以了。

pos后面删除：

void SLTEraseAfter(SLNode* pos)
{
	assert(pos);
	assert(pos->next);

	SLNode* tmp = pos->next;
	pos->next = pos->next->next;

	free(tmp);
	tmp = NULL;
}
1
2
3
4
5
6
7
8
9
10
11

我们要保存下一个节点防止它找不到下下个节点，我们让下一个节点指向下下个节点，再free掉下一个节点。

销毁链表：

void SLTDestroy(SLNode** pphead)
{
	assert(pphead);

	SLNode* cur = *pphead;
	while (cur)
	{
		SLNode* next = cur->next;
		free(cur);
		cur = next;
	}

	*pphead = NULL;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14

我们同样的要用一个节点来保存下一个节点，我们通过遍历链表来一个一个释放空间，释放后头结点指向下一个节点。

如果对大家有帮助的话，就拜托大家发财的小手点个赞吧，感谢大家的支持。