【数据结构】手撕单链表

前言

1 链表

1.1 链表的概念及结构

1.2 链表的分类

1.2.1 单向或者双向

1.2.2 带头或者不带头

1.2.3 循环或者非循环

1.2.4 无头单向非循环链表

1.2.5 带头双向循环链表

2 链表的实现

2.1 结构

2.2 结点的创建

2.3 尾插

2.4 头插

2.5 尾删

2.6 头删

2.7 查找

2.8 在pos位置之前插入数据

2.9 删除pos位置

2.10 在pos位置之后插入数据

2.11 删除pos位置之后的数据

2.12 打印数据

2.13 销毁数据

🎈个人主页：库库的里昂
🎐C/C++领域新星创作者
🎉欢迎 👍点赞✍评论⭐收藏
✨收录专栏：数据结构与算法
🤝希望作者的文章能对你有所帮助，有不足的地方请在评论区留言指正，大家一起学习交流！🤗

前言

上一次我们分享了线性表中的一种结构顺序表，它存在着一些其缺点，比如：在中间位置或者头部进行元素插入或者删除的时候时间复杂度是O(N)效率比较低，并且顺序表在扩容的时候也存在时间和空间上的消耗，由于我们每次都是按照二倍来扩的，那就很有可能会出现扩大了用不完导致空间浪费的现象。这些问题该如何解决呢？那就需要用到今天分享给大家的另一种线性结构链表。

1 链表

1.1 链表的概念及结构

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

注意：

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

假设在32位系统上，结点中值域为int类型，则一个节点的大小为8个字节，则也可能有下述链表：

1.2 链表的分类

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

1.2.1 单向或者双向

1.2.2 带头或者不带头

1.2.3 循环或者非循环

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

1.2.4 无头单向非循环链表

1.2.5 带头双向循环链表

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

2 链表的实现

2.1 结构

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;//数据域
	struct SListNode* next;//指针域
}SLTNode;

2.2 结点的创建

我们想使用链表来实现各种功能得先有链表，所以首先使用malloc创建节点。

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;
}

2.3 尾插

我们在尾插时，会有两种情况，链表为空的插入和有其他节点的尾插。第一种情况会出现一些理解性的错误，接下来就让我们学习学习这两种尾插的情况。

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;
	}	
}

2.4 头插

要想让链表连起来，就要让newnode->next存放下一个节点的地址，也就是旧链表phead的值，然后将newnode的地址存放在phead中，形成新的链表。无论一开始有没有节点，头插都是相同的。

void SLTPushFront(SLNode** pphead, SLNDataType x)
{
	assert(pphead);

	SLNode* newnode = CreateNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

2.5 尾删

在尾删时也有两种情况，一种是有很多节点，另一种是只剩一个节点，当删最后一个节点时，要改变plist的值，所以我们要传递plist的指针。我们要使用两个指针，当后面的指针释放后，可以利用前面的指针将最后一个节点的next置为空。

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;
	}
}

2.6 头删

头删时如果先释放空间，就会找不到下一个节点的地址；如果先把下一个节点的地址赋给*pphead就会导致无法释放空间，所以我们要创建一个临时变量来存放下一个节点的地址。

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

	SLNode* tmp = *pphead;
	*pphead = (*pphead)->next;
	free(tmp);
}

2.7 查找

循环判断时不要使用cur->next，这样写最后一个数据要单独处理不方便，找到时就返回此时的地址。

SLNode* SLTFind(SLNode* phead, SLNDataType x)
{
	SLNode* cur = phead;
	while (cur)
	{
		if (cur->val == x)
		{
			return cur;
		}
		else
		{
			cur = cur->next;
		}
	}
	return NULL;
}

2.8 在pos位置之前插入数据

在pos位置之前插入有一种特殊的情况就是头插，要改变plist的值，我们要传二级指针进去。同时我们要创建一个指针变量，找到pos之前的位置，才能使链表连接起来。

void SLTInsert(SLNode** pphead, SLNode* pos, SLNDataType x)
{
	assert(pphead);
	assert(pos);
	assert(*pphead);

	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;
	}
}

2.9 删除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;
	}
}

2.10 在pos位置之后插入数据

这里我们要注意地址赋值的顺序，顺序不对会造成内存泄漏。如果先把newnode的地址赋给pos的指针域，就会丢失下一个节点的地址。

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

	newnode->next = pos->next;
	pos->next = newnode;
}

2.11 删除pos位置之后的数据

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

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

	free(tmp);
	tmp = NULL;
}

2.12 打印数据

void SLTPrint(SLNode* phead)
{
	SLNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->val);
		cur = cur->next;
	}
	printf("NULL\n");
}

2.13 销毁数据

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

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

	*pphead = NULL;
}