链表（C语言）

前言：前面几篇文章我们详细介绍了顺序表，以及基于顺序表来实现的通讯录。今天我们连介绍一下链表的下一个结构链表。那么链表和顺序表究竟有什么区别呢？他们两个的优缺点分别是什么。今天这篇文章就带大家了解一下链表。

一.链表的概念

二.链表的分类

三.链表的实现

1.尾插链表

2.尾删链表

3.头插链表

4.头删链表

5.查找节点

6.打印链表

7.指定位置后插入链表

8.删除指定位置链表

三.链表所有代码

四.结言

一.链表的概念

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

首先我们先构造一个链表的基本结构：

typedef int ListType;
typedef struct List
{
	ListType x;
	struct List* next;
}List;

这里我们x存放我们需要储存的数据，next指针指向下一个数据节点的地址。

大概就是这样一个形态。

相当于一个火车的模型一节连着一节，这样就不用担心找不到下一节车厢了。

注意：

1.链式结构在逻辑上来讲是连续的，但是在物理结构上不一定连续。

2.现时结构上的内存都是从堆上申请过来的。

3.从堆上申请的空间，是按照一定的策略分配的可能连续也可能不连续。

二.链表的分类

从结构上来讲链表分为：

1.单向或双向

2. 带头或不带头

3.循环或非循环

但是我们实际应用中最常用到的还是：

无头单向非循环链表

有头双向循环链表

1. 无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。

2. 带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都
是带头双向循环链表。

三.链表的实现

1.尾插链表

这里由于许多函数都要用到创建内容，所以我们把创建空间分装成一个函数以便后续的操作。

List* BuyMemory(List* ls, ListType x)
{
	List* tem = (List*)malloc(sizeof(List));
	if (tem == NULL)
	{
		perror(malloc);
		return;
	}
	tem->val = x;
	tem->next = NULL;
	return tem;
}

接下来是尾插的内容：

void ListBackPush(List** ls, ListType x)
{
	List*newnext=BuyMemory(*ls,x);
	if (*ls == NULL)
	{
		*ls = newnext;
		(*ls)->next = NULL;
	}
	else
	{
		List* pcur = *ls;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = newnext;
	}
}}

2.尾删链表

void ListBackPop(List** ls)
{
	assert(*ls);
	if ((*ls)->next == NULL)
	{
		*ls = NULL;
		return;
	}
	List* pcur = *ls;
	while (pcur->next->next)
	{
		pcur = pcur->next;
	}
	pcur->next = NULL;
	free(pcur->next);
	
}

尾删我们只需要找到下一个节点为空的节点然后将他free掉就可以实现我们的尾删操作。

3.头插链表

void ListFrontPush(List** ls, ListType x)
{
	List* newnext = BuyMemory(*ls, x);

		newnext->next = (*ls);
		(*ls) = newnext;
	
}

这里我们需要注意的是 newnext->next = (*ls) (*ls) = newnext这两句代码的位置不能改变否则就找不到（*ls）的下一个节点。

4.头删链表

void ListFrontPop(List** ls)
{
	assert(*ls);
	List* pcur = *ls;
	(*ls) = pcur->next;
	free(pcur);
	pcur = NULL;
}

与头插链表一样需要注意的是链表之间的前后关系，插入之前要弄清楚每个节点的后节点于前节点有什么改变即可。

5.查找节点

List* ListFind(List** ls, ListType x)
{
	assert(*ls);
	List* pcur = *ls;
	int count = 1;
	while (pcur->val != x)
	{
		pcur = pcur->next;
		count++;
	}
	if (pcur)
	{
		prinft("找到了\n");
		return pcur;
	}
	else
	{
		printf("找不到\n");
		return 0;
	}
}

遍历链表查找所寻找节点的val，找到后返回该节点的地址。如果找不到则返回0。

6.打印链表

void ListPrint(List** ls)
{
	assert(*ls);
	List* pcur = *ls;
	while (pcur)
	{
		printf("%d->", pcur->val);
		pcur = pcur->next;
	}
}

我们所需要做的就是遍历链表并打印。

7.指定位置后插入链表

void ListRandomPush(List** ls, ListType x, List* flag)
{
	assert(ls);
	assert(*ls);
	List* newnext = BuyMemory(*ls, x);
	List* pcur = *ls;
	while (pcur != flag)
	{
		pcur = pcur->next;
	}
	newnext->next = pcur->next;
	pcur->next = newnext;
}

同样需要注意的是每个节点之间的关系，要注意 newnext->next = pcur->next; pcur->next = newnext位置不可以改变否则会找不到pcur的next。

8.删除指定位置链表

void ListRandomPop(List** ls, List* flag)
{
	assert(ls);
	assert(*ls);
	List* pcur = *ls;

	while (pcur->next != flag)
	{
		pcur = pcur->next;
	}
	List* prev = pcur->next;
	pcur->next = pcur->next->next;
	free(prev);
	prev = NULL;
}

我们需要注意各个节点之间的关系，处理好他们的链接关系就可以了。

还有许多可以实现的操作但实现方法大都大同小异，以上的代码就可以解决大部分的实际问题，大家感兴趣的可以自己去写一下其他的操作。

三.链表所有代码

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

typedef int ListType;
typedef struct List
{
	ListType val;
	struct List* next;
}List;

void ListBackPush(List** ls,ListType x);
void ListBackPop(List** ls);
void ListFrontPush(List** ls, ListType x);
void ListFrontPop(List** ls);
List* ListFind(List** ls, ListType x);
void ListRandomPush(List** ls, ListType x,List*flag);
void ListRandomPop(List** ls, List* flag);
void ListPrint(List** ls);

List.c
nclude"List.h"


List* BuyMemory(List* ls, ListType x)
{
	List* tem = (List*)malloc(sizeof(List));
	if (tem == NULL)
	{
		perror(malloc);
		return;
	}
	tem->val = x;
	tem->next = NULL;
	return tem;
}
void ListBackPush(List** ls, ListType x)
{
	List*newnext=BuyMemory(*ls,x);
	if (*ls == NULL)
	{
		*ls = newnext;
		(*ls)->next = NULL;
	}
	else
	{
		List* pcur = *ls;
		while (pcur->next)
		{
			pcur = pcur->next;
		}
		pcur->next = newnext;
	}
}
void ListBackPop(List** ls)
{
	assert(*ls);
	if ((*ls)->next == NULL)
	{
		*ls = NULL;
		return;
	}
	List* pcur = *ls;
	while (pcur->next->next)
	{
		pcur = pcur->next;
	}
	pcur->next = NULL;
	free(pcur->next);
	
}
void ListFrontPush(List** ls, ListType x)
{
	List* newnext = BuyMemory(*ls, x);

		newnext->next = (*ls);
		(*ls) = newnext;
	
}
void ListFrontPop(List** ls)
{
	assert(*ls);
	List* pcur = *ls;
	(*ls) = pcur->next;
	free(pcur);
	pcur = NULL;
}
List* ListFind(List** ls, ListType x)
{
	assert(*ls);
	List* pcur = *ls;
	int count = 1;
	while (pcur->val != x)
	{
		pcur = pcur->next;
		count++;
	}
	if (pcur)
	{
		printf("找到了\n");
		return pcur;
	}
	else
	{
		printf("找不到\n");
		return 0;
	}
}
void ListPrint(List** ls)
{
	assert(*ls);
	List* pcur = *ls;
	while (pcur)
	{
		printf("%d->", pcur->val);
		pcur = pcur->next;
	}
}
void ListRandomPush(List** ls, ListType x, List* flag)
{
	assert(ls);
	assert(*ls);
	List* newnext = BuyMemory(*ls, x);
	List* pcur = *ls;
	while (pcur != flag)
	{
		pcur = pcur->next;
	}
	newnext->next = pcur->next;
	pcur->next = newnext;
}
void ListRandomPop(List** ls, List* flag)
{
	assert(ls);
	assert(*ls);
	List* pcur = *ls;

	while (pcur->next != flag)
	{
		pcur = pcur->next;
	}
	List* prev = pcur->next;
	pcur->next = pcur->next->next;
	free(prev);
	prev = NULL;
}

text.c 

#include"List.h"
void test01()
{
	List* ls = NULL;

	ListBackPush(&ls, 1);
	ListBackPop(&ls);
	ListFrontPush(&ls, 1);
	ListBackPush(&ls, 2);
	ListBackPush(&ls, 3);
	ListBackPush(&ls, 4);
	List* ret = ListFind(&ls, 2);
	ListRandomPush(&ls, 100, ret);
	List* ret1 = ListFind(&ls, 100);
	ListRandomPop(&ls, ret1);
	ListPrint(&ls);
	//ListFrontPop(&ls);

}
int main()
{
	test01();
	return 0;
}