【数据结构初阶】手撕单链表_c++手撕链表

一.链表概念和结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
正像概念所说的，链表并不像顺序表那样在物理存储结构式是连续、顺序的。而是在逻辑上是连续的。

结构如下图所示:

创建一个结构体，存放一个数据元素和一个指向下一个结构体的指针，最后一个指针为NULL，这就构成了单链表；

typedef int SLDataType;

typedef struct SListNode
{
	SLDataType data;//存放数据元素
	struct SListNode* next;//指向下一个结构体的指针
}SLTNode;

SLTNode* P=NULL;//初始化单链表
1
2
3
4
5
6
7
8
9

二.单链表功能的实现

1.打印单链表内容

我们使用单链表存储数据后，为了方便我们检查数据是否正常存储，应该设计函数来打印当前单链表的内容。并且函数接受的结构体指针不需要断言检查，因为就算单链表为空也应当像顺序表那样打印出来。

void SLTPintf(SLTNode* 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

2.申请单链表节点

再后来我们要对链表进行插入时，就必须要再申请新的链表节点进行插入，所以我们可以分装申请节点的函数，在插入操作前调用此函数即可。

SLTNode* AppSLTnext(SLDataType x)
{
	SLTNode* nextnode = (SLTNode*)malloc(sizeof(SLTNode));
	if (nextnode == NULL)
	{
		perror("malloc fail");
		return NULL;
	}

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

3.头插和尾插

像插入和删除的操作都是会对链表进行修改的所以函数参数需要使用二级指针来接受。
头插比较简单，如下操作即可:

void SLTPushFront(SLTNode** pphead, SLDataType x)
{
	SLTNode* nextnode = AppSLTnext(x);
	nextnode->next = *pphead;
	*pphead = nextnode;
}
1
2
3
4
5
6

尾插则要区分链表是否为空，以及要进行找尾的重要操作。

void SLTPushBack(SLTNode** pphead, SLDataType x)
{
	SLTNode* nextnode = AppSLTnext(x);

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

4.头删和尾删

删除操作则需要对指针的内容进行检查，因为如果链表为空则不能够进行删除的操作。
头删操作如下:

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

	SLTNode* first = *pphead;

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

尾删的找尾与尾插的找尾则稍有不同:

void SLTPopBack(SLTNode** pphead)
{
	assert(*pphead);

	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* 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

5.单链表查找

SLTNode* SLTFind(SLTNode* phead, SLDataType x)
{
	//不直接使用传过来的指针，优雅永不过时
	SLTNode* cur = phead;
	//第一种
	while (cur->data != x)
	{
		cur = cur->next;
	}

	return cur;
	//第二种

	/*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
15
16
17
18
19
20
21
22

6.pos位置前后插入

前插需要考虑指针是否为空的情况，还有如果pos就在第一位，则等同于头插操作。

void SLTInsert(SLTNode** pphead, SLTNode* pos, SLDataType x)
{
	assert(pphead);
	assert(pos);

	if (pos = *pphead)
		SLTPushFront(pphead, x);
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}

		SLTNode* newnode = AppSLTnext(x);
		newnode->next = prev->next;
		prev->next = newnode;

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

尾插相较简单些:

void SLTInsertAfter(SLTNode* pos, SLDataType x)
{
	SLTNode* newnode = AppSLTnext(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
1
2
3
4
5
6

7.pos位置删除

pos位置删除:

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

	if (pos = *pphead)
		SLTPopFront(pphead);
	else
	{
		SLTNode* 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

删除pos后位置:

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

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

单链表的功能实现到此为止，感谢你们的阅读！

三.链表面试题剖析

欲知后事如何，且听下回分解。我将在下一篇博客详解多道面试题。