1. 链表的概念及结构

相信大家都坐过过火车吧，没做过至少也看过吧，火车都是一节一节的，车厢之间用车钩连接在一起，我们今天学习的链表和火车就有相似的地方，让我们来了解一下链表

1.1链表的概念

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的 。
链表由一系列节点（链表中每一个元素称为节点，每个节点又是一个结构体）组成，节点在运行时动态开辟（malloc），每个节点包括两个部分：

 1.一个是存储数据元素的数据域
 2.另一个是指针域（存储下一个节点地址(单链表),或者上一个节点和下一个节点地址的(双向链表)）

以下是一个简单的单链表的定义

struct ListNode {
	int val;//数据域
	struct ListNode *next;//指针域
};

1.2链表的结构

链表的结构是通过节点（Node）之间的指针连接，形成一种动态、灵活的存储方式。听起来可能有点蒙所以用图来介绍。

根据这个图我们可以看到以下特点：
1.每个节点中都存放了**下一个节点的地址**，这样我们可以通过指针访问到下一个节点。
2.每个节点的地址是一定不连续的（正好印证了物理存储结构上非连续非顺序的存储结构）。
3.既然不是连续的那么每一个节点都需要去动态开辟（malloc）。

2.链表的分类

链表的分类是按照三个大方向来区分的
1.单向/双向

2.循环/不循环

3.带头节点/不带头节点（有的地方也叫哨兵位，只是一个头不存数据）

根据这三种大的方向的排列组合我们就可以得到不同的链表了。
以下我们采用无头单向非循环链表和带头双向循环链表，作为例子介绍后面的内容。因为：
1.无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。
2.带头双向循环链表：结构最复杂，一般用在单独存储数据。实际中使用的链表数据结构，都是带头双向循环链表。另外这个结构虽然结构复杂，但是使用代码实现以后会发现结构会带来很多优势，实现反而简单了，后面我们代码实现了就知道了。

3. 链表的实现

这里我们先以无头单向非循环链表为例为大家介绍链表的实现

3.1 链表的声明

typedef int SListDataType;
//节点
typedef struct SListNode
{
	SListDataType data;
	struct SListNode* next;
}SListNode;

1.typedef int SListDataType; 的意义是如果后面我们想改节点中存放的数据类型的话在这里改会方便很多。
2.struct SListNode* next ：next指向的数据类型是SListNode类型的也就是指向的是一个节点。

3.2 动态申请一个结点 (BuySListNode）

因为我们后面要实现各种头插，尾插，中间节点插入都需要开辟新的节点所以，为了复用就写一个申请节点的接口。

SListNode* BuySListNode(SListDataType x)
{
	SListNode* newNode = (SListNode*)malloc(sizeof(SListNode));
	if (newNode == NULL)
	{
		printf("申请失败\n");
		exit(-1);//这样
	}
	newNode->data = x;
	newNode->next = NULL;
	return newNode;
}

1.一般来说我们在开辟一个新节点时都需要初始化（不初始化里面存的是随机值，可能会有影响）

3.3尾插 （SListPushBack）

void SListPushBack(SListNode** pphead, SListDataType x)
{
	SListNode* newNode = BuySListNode(x);
	if (*pphead == NULL)
	{

		*pphead = newNode;//
	}
	else
	{
	SListNode* tail = *pphead;
	while (tail->next != NULL)
	{
		tail = tail->next;
	}
		tail->next = newNode;
	}
}

为什么这里要用二级指针？

1.当链表为空时（*pphead == NULL），需要将新节点 newNode 赋值给头指针 *pphead。
2.如果函数参数是 SListNode* phead（一级指针），函数内部对 phead 的修改（如 phead = newNode）
不会影响调用者的头指针，因为是值传递。
3.通过传递头指针的地址（SListNode** pphead），函数可以直接修改调用者的头指针（*pphead = newNode）。
4.此时 phead 是局部变量，修改它不会影响外部的头指针。
5.统一处理非空链表无论链表是否为空，函数都需要通过 pphead 访问头指针：空链表时：修改 *pphead。
非空链表时：通过 *pphead 找到链表起点，遍历到尾部并插入新节点。

3.4 尾删(SListPopBack)

void SListPopBack(SListNode** pphead)
{
	
	if (*(pphead) == NULL)
	{
		return;
	}
	
	else if ((*pphead)->next==NULL)
	{
		free((*pphead));
		*pphead = NULL;
	}
	else
	{
		SListNode* cur = *pphead;
		SListNode* end = NULL;
		while (cur->next!=NULL)
		{
			
			end = cur;
			cur = cur->next;
		}
		
		free(cur);
		end->next = NULL;
	}
}

注意这里要分不同的情况，

1.链表为空
2.链表只有一个节点
3.链表有一个以上节点

3.5头插 SListPushFront

void SListPushFront(SListNode** pphead, SListDataType x)
{
	SListNode* newNode = BuySListNode(x);
	newNode->next = *pphead;
	*pphead = newNode;
}

记得把头插的节点定义为链表的头

3.6头删 SListPopFront

void SListPopFront(SListNode** pphead)
{
	if (*pphead == NULL)
	{
		return;
	}
	SListNode* cur = *pphead;
	*pphead = (*pphead)->next;
	free(cur);

}

3.7 查询 SListFind

SListNode* SListFind(SListNode* phead, SListDataType x)
{
	SListNode* cur = phead;
	while (cur)
	{
		if (cur->data == x)
		{
			return cur;
		}
		cur=cur->next;
	}
	return NULL;
}

这里写的查询非常简单且功能非常单一

1.只能按顺序查询，只能返回第一个节点内，数为x的节点
2.当我们找到某个节点后就可以对这个节点经行其他操作了，例如：改，删......

3.8单链表在pos位置之后插入x （SListInsertAfter）

void SListInsertAfter(SListNode* pos, SListDataType x)
{
	SListNode* newNode = BuySListNode(x);
	newNode->next = pos->next;
	pos->next = newNode;
}

这里千万要注意！！！
一定是先让newnode的next指向pos位置后一个节点，再让pos的next指向newnode
反了就会导致找不到后面一个节点了

3.9 单链表删除pos位置之后的值 （SListEraseAfter）

void SListEraseAfter(SListNode* pos)
{
	if (pos->next)
	{
		SListNode* next = pos->next;
		SListNode* nextnext = next->next;
		pos->next = nextnext;
		free(next);
	}
}

到这里我们就实现了单链表的定义及一些常用的接口代码
这里可以想想，我们实现了在任意位置之后插入删除，是不是可以复用一下实现头尾的插入和删除

4.链表面试题目及思路分享

相信你要已经对链表有了一定的了解，想必你现在也想知道自己对链表到底掌握了多少

多说不易，直接先上两道题试试

链表面试题目

1.删除链表中等于给定值 val 的所有结点。OJ链接
2.反转一个单链表。OJ链接
3.给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则返回第二个中间结点。OJ链接
4.输入一个链表，输出该链表中倒数第k个结点。 OJ链接

想必聪明的你，对这几道简单题目可以说不在话下，可以说手拿把掐

那么你就可以去试试下面几道题了，如果都能做出来那么你就神功大成了。

5.将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有
结点组成的OJ链接

6.编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结
点之前OJ链接
7.链表的回文结构。OJ链接
8. 输入两个链表，找出它们的第一个公共结点。OJ链接
9.给定一个链表，判断链表中是否有环。OJ链接
10. 给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULLOJ链接
11. 给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点
或空结点。OJ链接
12.给定单个链表的头 head ，使用 插入排序 对链表进行排序，并返回 排序后链表的头 。OJ链接

思路分享

如果你对这几道题做不出来也不用担心，以下就给你说说每道题目的思路和代码

我把思路和代码都放到了我的gitee里面了gitee连接有需要自取

在我们了解单向链表之后，我们可以来看看双向链表的实现了

5.双向链表

5.1双向链表的定义和初始化

typedef struct ListNode
{
	struct ListNode* next;
	struct ListNode* prev;
	LTDataType val;
}ListNode;
//初始化
ListNode* ListInit()
{
	ListNode* phead = BuyListNode(0);
	phead->next = phead;
	phead->prev = phead;

	return phead;
}

这里要特别注意，所以初始化时头和尾都指向自己。

带头双向循环链表的实现比我们之前学的单链表要简单。

5.2 尾插

void ListPushBack(ListNode*	phead, LTDataType x)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* newnode = BuyListNode(x);

	tail->next = newnode;
	newnode->prev = tail;

	newnode->next = phead;
	phead->prev = newnode;
}

这里我们可以注意到我们没有使用二级指针了
2. 为什么不需要二级指针？

在无头节点的链表中，头指针可能为 NULL（空链表时），因此需要通过二级指针修改头指针。
在带头节点的链表中，头节点始终存在（phead 永远不会为 NULL），因此：无需处理“空链表”的特殊情况。
无需通过二级指针修改头指针（因为头节点本身不会被修改或重新赋值）。

5.3尾删

void ListPopBack(ListNode*	phead)
{
	assert(phead);
	ListNode* tail = phead->prev;
	ListNode* prev = tail->prev;
	prev->next = phead;
	phead->prev = prev;
	free(tail);
}

5.4 头插

void ListPushFront(ListNode* phead, LTDataType x)
{
	ListNode* newnode = BuyListNode(x);
	ListNode* first = phead->next;

	newnode->prev = phead;
	phead->next = newnode;

	newnode->next = first;
	first->prev = newnode;
}

5.5头删

void ListPopFront(ListNode* phead)
{
	assert(phead);
	ListNode* first = phead->next;
	ListNode* next = first->next;
	phead->next = next;
	next->prev = phead;
	free(first);
}

5.6 查询

ListNode* ListFind(ListNode* phead, LTDataType x)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		if (cur->val == x)
			return cur;
		cur = cur->next;
	}
	return NULL;
}

5.7 pos位置之前插入

void ListInsert(ListNode* pos, LTDataType x)
{
	assert(pos);
	ListNode* posPrev = pos->prev;
	ListNode* newnode = BuyListNode(x);

	pos->prev = newnode;
	newnode->next = pos;

	posPrev->next = newnode;
	newnode->prev = posPrev;
}

5.8 pos位置之前删除

void ListErase(ListNode* pos)
{
	assert(pos); 
	ListNode* posPrev = pos->prev;
	ListNode* posNext = pos->next;

	posPrev->next = posNext;
	posNext->prev = posPrev;
	free(pos);
}

最后因为多了头节点我们需要删除链表（需要二级指针），和清理头节点之后的链表

void ListClear(ListNode* phead)
{
	assert(phead);
	ListNode* cur = phead->next;
	while (cur != phead)
	{
		ListNode* next = cur->next;
		free(cur);
		cur = next;
	}
	phead->next = phead;
	phead->prev = phead;
}

void ListDestory(ListNode** pphead)
{
	ListClear(*pphead);
	free(*pphead);
	*pphead = NULL;
}

以上就是我们对双向链表的代码实现和接口实现了

6.链表和顺序表的区别

区别大致有六种区别：

归根结底链表和顺序表之间是互补的，双方的不足之处都是另一个的长处。