[数据结构与算法]【数据结构】链表

1.链表的概念

链表是一种物理存储单元上非连续、非顺序的存储单元，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。 相比于线性表数据结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

2.链表的优缺点

使用链表结构可以克服数组链表需要预先知道数据大小的缺点，链表结构可以充分利用计算机内存空间，实现灵活的内存动态管理。但是链表失去了数组随机读取的优点，同时链表由于增加了结点的指针域，空间开销比较大。链表最明显的好处就是，常规数组排列关联项目的方式可能不同于这些数据项目在记忆体或磁盘上顺序，数据的存取往往要在不同的排列顺序中转换。链表允许插入和移除表上任意位置上的节点，但是不允许随机存取。

3.链表的分类

1. 单链表
2. 双向链表
3. 带头链表
4. 循环链表
5. 带头双向循环链表

4.实现链表

4.1 单链表

链表的一个节点由指针域和数据域构成。
链表的整体思想其实并不难懂，但一旦让他和指针结合在一起时，就容易让人摸不得头脑。
可以这样理解：在链表的创建中，添加一个指向下一个节点的指针，这个指针保存的是下一个节点的地址，我们说这个指针指向下一个节点。
那么指针的类型是什么呢？当然是Node了，因为指针不仅仅指向数据域，同时也指向指针域。

代码实现：

typedef struct SListNode
{
	int data;
	struct ListNode* next;
}SListNode;

4.1.1 单链表初始化

参数的传入：涉及改变链表的操作统统用指针传链表，不然函数调用完成之后，为传入的链表分配的的内存会自动释放，链表不会有任何改变。
创建头结点，为头结点分配内存。
令头节点的指针为空指针(指针不初始化容易出现很多问题)
PS：这里为什么要动态分配内存呢？
因为这就是数组和链表的区别呀：线性表的顺序存储结构用数组实现，而数组占用的是一整块内存，数组元素分布很集中，需要提前预定数组的长度。
而链表是一种动态结构，它所占用的大小和位置是不需要提前分配的，可以根据自身的需求即时生成。
代码实现：

SListNode* SListinit()
{
	SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));
	tmp->next = NULL;
	return tmp;
}

4.1.2 单链表动态申请节点

创建变量tmp动态开辟一块内存，如果tmp不为空，就赋值返回回去，如果为空就返回NULL，并提示信息。

SListNode* BuyNewNode(int data)
{
	SListNode* tmp = (SListNode*)malloc(sizeof(SListNode));
	tmp->data = data;
	tmp->next = NULL;
	if (tmp == NULL)
	{
		printf("开辟空间失败!");
		return NULL;
	}
	else
	{
		return tmp;
	}
}

4.1.3 单链表尾插

定义一个tail指针，要tail指针走到链表的最后一个节点，然后开辟一个新的结点，把最后一个节点的next赋值为心新的结点。

void SListPushBack(SListNode** List,int x)
{
	if (*List == NULL)
	{
		*List = SListinit();
		(*List)->data = x;
		return;
	}
	else
	{
		SListNode* tail = *List;
		SListNode* tmp = BuyNewNode(x);
		if (tmp == NULL)
		{
			printf("开辟空间失败!");
			return;
		}
		while (tail->next)
		{
			tail = tail->next;
		}
		tail->next = tmp;
	}
}

4.1.4 单链表头插

先保存第一个节点的next节点（就是第一个的下一个节点），然后开辟一个新的结点，然后将新的节点赋值为头，再将新节点的next赋值为之前的第一个节点

void SListPushFront(SListNode** List, int x)
{
	if (*List == NULL)
	{
		*List = SListinit();
		(*List)->data = x;
		return;
	}
	else
	{
		SListNode* tmp = BuyNewNode(x);
		if (tmp == NULL)
		{
			printf("开辟空间失败!");
			return;
		}
		tmp->next = *List;
		*List = tmp;
	}
}

4.1.5 单链表头删

先保存第一个节点的next节点（就是第一个的下一个节点），然后free(第一个节点)，再将头赋值为第一个节点的next节点。

void SListPopFront(SListNode** List)
{
	assert(*List);
	SListNode* tail = (*List)->next;
	free(*List);
	*List = tail;
}

4.1.6 单链表尾删

如果链表为空，不需要删除，如果不为空则，找到尾部结点的前一个结点，让前一个结点的next置为NULL就好了。

void SListPopBack(SListNode** List)
{
	assert(*List);
	SListNode* prev = *List;
	SListNode* tail = (*List)->next;
	if ((*List)->next == NULL)
	{
		free(*List);
		*List = NULL;
		return;
	}
	while (tail->next)
	{
		tail = tail->next;
		prev = prev->next;
	}
	free(tail);
	tail = NULL;
	prev->next = NULL;
}

4.1.7 单链表指定位置插入

如果链表没有结点，则新插入的就是第一个结点。如果不是，则找到x的前一个节点和后一个节点，要x的前一个节点的next指向x的后一个节点。

void SListRamPush(SListNode** List, int x, int place)
{
	if (*List == NULL)
	{
		*List = SListinit();
		(*List)->data = x;
		return;
	}
	if (place == 0)
	{
		SListPushFront(List, x);
		return;
	}
	else
	{
		SListNode* tail = (*List)->next;
		SListNode* prev = *List;
		SListNode* tmp = BuyNewNode(x);
		if (tmp == NULL)
		{
			printf("开辟空间失败!");
			return;
		}
		while (place--)
		{
			tail = tail->next;
			prev = prev->next;
		}
		tmp->next = tail;
		prev->next = tmp;
	}
}

4.1.8 单链表指定位置删除

如果链表为空，不需要删除 如果删除的是第一个结点，则需要将保存链表首地址的指针保存第一个结点的下一个结点的 地址 如果删除的是中间结点，则找到中间结点的前一个结点，让前一个结点的指针域保存这个结 点的后一个结点的地址即可

void SListRamPop(SListNode** List, int place)
{
	assert(*List);
	if (place == 0)
	{
		SListPopFront(List);
	}
	else
	{
		SListNode* prev = NULL;
		SListNode* next = *List;
		while (place--)
		{
			prev = next;
			next = next->next;
		}
		prev->next = next->next;
		free(next);
		next = NULL;
	}
}

4.1.9 单链表查找

先对比第一个结点的数据域是否是想要的数据，如果是就直接返回，如果不是则继续查找下 一个结点，如果到达最后一个结点的时候都没有匹配的数据，说明要查找数据不存在

SListNode* SListFind(SListNode* SList, int x)
{
	assert(SList);
	while(SList)
	{
		if (SList->data == x)
		{
			return SList;
		}
		else
		{
			SList = SList->next;
		}
	}
	return NULL;
}

4.1.10 单链表的销毁

void DestorySList(SListNode** List)
{
	assert(*List);
	SListNode* tail = (*List)->next;
	while(tail)
	{
		free(*List);
		*List = tail;
		tail = tail->next;
	}
	*List = NULL;
}

xdm有说的不对的地方，请多多指教。