【数据结构】链表简介及单链表的实现

简单不先于复杂，而是在复杂之后。

1. 链表

1.1 链表的概念及结构

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

现实中 数据结构中

1.2 链表的分类

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

1. 单向或双向：

2. 带头或不带头：

3. 循环或非循环：

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

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

1.3 无头单向非循环链表的实现

Slist.h

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

typedef int SLTDataType;
typedef struct SlistNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode,*PSLTNode;

//以下三种形式等价
//SLTNode*
//PSLTNode
//struct SlistNode

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

//打印链表
void SListPrint(SLTNode* phead);
//void SListPrint(PSLTNode phead);

//销毁链表
//不及时销毁链表是一种内存泄露
void SListDestory(SLTNode** pphead);

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

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

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

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

//查找
//可以充当修改
SLTNode* SlistFind(SLTNode* phead, SLTDataType x);

//在pos之前插入
void SlistInsert(SLTNode** pphead, SLTNode* pos, SLTDataType x);

//在pos之后插入
void SlistInsertAfter(SLTNode* pos, SLTDataType x);


//删除pos位置
void SlistErase(SLTNode** pphead, SLTNode* pos);

//删除pos后面位置
void SlistEraseAfter(SLTNode* pos, SLTDataType x);

Slist.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"

void SListPrint(SLTNode* phead)
{
	//不能断言，因为phead为空是正常情况，表示空链表
	SLTNode* cur = phead;
	while (cur != NULL)
	{
		printf("%d->", cur->data);
		cur = cur->next;
	}
	printf("NULL\n");
}

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

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

	SLTNode* newnode = BuySLTNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}

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

	SLTNode* newnode = BuySLTNode(x);

	//1. 链表为空
	//2. 链表非空

	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		//找尾
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			tail = tail->next;
		}
		tail->next = newnode;
		//尾插改变的是结构体成员，所以不用二级指针（结构体指针的指针），用结构体指针
	}
}


void SListPopBack(SLTNode** pphead)
{
	assert(pphead);
	//1.多个节点
	//2.一个节点
	if (*pphead == NULL)
	{
		return;
	}

	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	else
	{
		SLTNode* prev = NULL;
		SLTNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}

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

	}

}



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

	//温柔的检查
	if (*pphead == NULL)
	{
		return;
	}

	暴力检查
	//assert(*pphead != NULL);

	SLTNode* del = *pphead;
	*pphead = (*pphead)->next;

	free(del);
	del = NULL;
}

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

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


SLTNode* SlistFind(SLTNode* phead, SLTDataType x)
{
	SLTNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur = cur->next;
	}
	return NULL;
}

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

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

			//暴力检查，pos不在链表中,prev为空还没有找到pos说明pos传错了
			assert(prev);
		}
		SLTNode* newnode = BuySLTNode(x);
		prev->next = newnode;
		newnode->next = pos;

	}

}

void SlistInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	SLTNode* newnode = BuySLTNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}

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

	if (*pphead == pos)
	{
		SListPopFront(pphead);
	}
	else
	{
		SLTNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
			//检查pos不是链表中节点，参数传错了
			assert(prev);
		}
		prev->next = pos->next;
		free(pos);
		
	}
}


void SlistInsertAfter(SLTNode* pos, SLTDataType x)
{
	assert(pos);

	if (pos->next == NULL)
	{
		return;
	}
	else
	{
		SLTNode* next = pos->next;
		pos->next = next->next;
		free(next);
	}
}

test.c

#define _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"

void TestSlist1()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPrint(plist);
}

void TestSlist2()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

	//SListPopBack(&plist);
	//SListPopBack(&plist);
	//SListPopBack(&plist);
	//SListPopBack(&plist);
	//SListPopBack(&plist);
	//SListDestory(&plist);

	SLTNode* pos = SlistFind(plist, 3);
	if (pos)
	{	
		//修改
		//SlistInsert(&plist, pos, 20);
		SlistErase(&plist, pos);
		printf("找到了\n");
	}
	else
	{
		printf("没找到\n");
	}


	SListPrint(plist);
}


int main()
{
	//TestSlist1();
	TestSlist2();

	return 0;
}

单链表只适合头插头删，时间复杂度 O(1)

(next);
}
}

`test.c`

```c
#define _CRT_SECURE_NO_WARNINGS 1
#include"Slist.h"

void TestSlist1()
{
	SLTNode* plist = NULL;
	SListPushFront(&plist, 1);
	SListPushFront(&plist, 2);
	SListPushFront(&plist, 3);
	SListPushFront(&plist, 4);
	SListPrint(plist);
}

void TestSlist2()
{
	SLTNode* plist = NULL;
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

	//SListPopBack(&plist);
	//SListPopBack(&plist);
	//SListPopBack(&plist);
	//SListPopBack(&plist);
	//SListPopBack(&plist);
	//SListDestory(&plist);

	SLTNode* pos = SlistFind(plist, 3);
	if (pos)
	{	
		//修改
		//SlistInsert(&plist, pos, 20);
		SlistErase(&plist, pos);
		printf("找到了\n");
	}
	else
	{
		printf("没找到\n");
	}


	SListPrint(plist);
}


int main()
{
	//TestSlist1();
	TestSlist2();

	return 0;
}

单链表只适合头插头删，时间复杂度 O(1)

任意位置高效插入删除要交给之后文章讲解的双向链表。