数据结构从入门到精通——链表

链表

• 前言
• 一、链表
• • 1.1 链表的概念及结构
  • 1.2 链表的分类
  • 1.3 链表的实现
  • 1.4 链表面试题
  • 1.5 双向链表的实现
• 二、顺序表和链表的区别
• 三、单项链表实现具体代码
• • text.h
  • text.c
  • main.c
  • 单链表的打印
  • 空间的开辟
  • 链表的头插、尾插
  • 链表的头删、尾删
  • 链表中元素的查找
  • 链表在指定位置之前、之后插入数据
  • 删除链表中的结点
  • 销毁链表
• 四、双向循环链表代码的具体实现
• • text.h
  • text.c
  • main.c
  • 双向循环链表的创建
  • 双向循环链表的初始化
  • 双向循环链表的销毁
  • 双向循环链表的打印
  • 双向循环链表的头插和尾插
  • 双向循环链表的头删和尾删
  • 双向循环链表的元素查找
  • 双向循环链表的插入和删除

---

前言

链表是一种常见的数据结构，由一系列节点组成，每个节点包含数据和指向下一个节点的指针。链表的一个显著特点是，它不需要在内存中连续存储，因此可以高效地插入和删除节点。这种灵活性使得链表在许多应用中成为理想的选择，尤其是在需要动态调整数据结构大小的场景中。

在链表的实现中，通常会有头节点和尾节点之分。头节点是链表的第一个节点，而尾节点是链表的最后一个节点。通过遍历链表，我们可以访问链表中存储的所有数据。链表还支持在链表头部或尾部快速添加新节点，这些操作的时间复杂度通常为O(1)。

然而，链表也有一些缺点。比如，访问链表中的某个特定节点需要从头节点开始遍历，这导致访问链表中间节点的平均时间复杂度为O(n)。此外，链表需要额外的空间来存储指针，这增加了内存的使用。

链表有多种类型，如单向链表、双向链表和循环链表等。单向链表是最简单的链表类型，每个节点只有一个指向下一个节点的指针。双向链表则允许节点同时指向前一个和下一个节点，这使得双向链表在某些操作上比单向链表更高效。循环链表则是将尾节点的指针指向头节点，形成一个闭环。

在实际应用中，链表常用于实现栈、队列和哈希表等数据结构。例如，链表可以作为栈的底层数据结构，实现元素的先进后出。此外，链表还可以用于实现动态数组，支持元素的动态插入和删除。

总之，链表作为一种重要的数据结构，在编程和数据处理中发挥着重要作用。尽管链表在某些方面存在不足，但其灵活性和高效性使得它在许多场景中仍然是理想的选择。通过深入了解链表的特性和应用，我们可以更好地利用这种数据结构来解决实际问题。

---

一、链表

1.1 链表的概念及结构

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


现实中 数据结构中

1.2 链表的分类

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

1. 单向或者双向
   
2. 带头或者不带头
   
3. 循环或者非循环
   

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

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

1.3 链表的实现

// 1、无头+单向+非循环链表增删查改实现
typedef int SLTDateType;
typedef struct SListNode
{
 SLTDateType data;
 struct SListNode* next;
}SListNode;
// 动态申请一个结点
SListNode* BuySListNode(SLTDateType x);
// 单链表打印
void SListPrint(SListNode* plist);
// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x);
// 单链表的头插
void SListPushFront(SListNode** pplist, SLTDateType x);
// 单链表的尾删
void SListPopBack(SListNode** pplist);
// 单链表头删
void SListPopFront(SListNode** pplist);
// 单链表查找
SListNode* SListFind(SListNode* plist, SLTDateType x);
// 单链表在pos位置之后插入x
// 分析思考为什么不在pos位置之前插入？
void SListInsertAfter(SListNode* pos, SLTDateType x);
// 单链表删除pos位置之后的值
// 分析思考为什么不删除pos位置？
void SListEraseAfter(SListNode* pos);

1.4 链表面试题

1. 删除链表中等于给定值 val 的所有结点
2. 反转一个单链表
3. 给定一个带有头结点 head 的非空单链表，返回链表的中间结点。如果有两个中间结点，则 返回第二个中间结点
4. 输入一个链表，输出该链表中倒数第k个结点
5. 将两个有序链表合并为一个新的有序链表并返回。新链表是通过拼接给定的两个链表的所有 结点组成的
6. 编写代码，以给定值x为基准将链表分割成两部分，所有小于x的结点排在大于或等于x的结 点之前
7. 链表的回文结构
8. 输入两个链表，找出它们的第一个公共结点
   
9. 给定一个链表，判断链表中是否有环
   【思路】
   快慢指针，即慢指针一次走一步，快指针一次走两步，两个指针从链表其实位置开始运行，如果链表带环则一定会在环中相遇，否则快指针率先走到链表的末尾。比如：陪女朋友到操作跑步减肥。

【扩展问题】

• 为什么快指针每次走两步，慢指针走一步可以？
  假设链表带环，两个指针最后都会进入环，快指针先进环，慢指针后进环。当慢指针刚进环时，可能就和快指针相遇了，最差情况下两个指针之间的距离刚好就是环的长度。
  此时，两个指针每移动一次，之间的距离就缩小一步，不会出现每次刚好是套圈的情况，因此：在满指针走到一圈之前，快指针肯定是可以追上慢指针的，即相遇。

• 快指针一次走3步，走4步，…n步行吗？
  

10. 给定一个链表，返回链表开始入环的第一个结点。 如果链表无环，则返回 NULL

• 结论
  让一个指针从链表起始位置开始遍历链表，同时让一个指针从判环时相遇点的位置开始绕环
  运行，两个指针都是每次均走一步，最终肯定会在入口点的位置相遇。
• 证明
  

11. 给定一个链表，每个结点包含一个额外增加的随机指针，该指针可以指向链表中的任何结点 或空结点。
    要求返回这个链表的深度拷贝
12. 其他 。ps：链表的题当前因为难度及知识面等等原因还不适合我们当前学习，大家可以先把c++学一下，在逐步开始刷题 Leetcode + 牛客

1.5 双向链表的实现

// 2、带头+双向+循环链表增删查改实现
typedef int LTDataType;
typedef struct ListNode
{
 LTDataType _data;
 struct ListNode* next;
 struct ListNode* prev;
}ListNode;
// 创建返回链表的头结点.
ListNode* ListCreate();
// 双向链表销毁
void ListDestory(ListNode* plist);
// 双向链表打印
void ListPrint(ListNode* plist);
// 双向链表尾插
void ListPushBack(ListNode* plist, LTDataType x);
// 双向链表尾删
void ListPopBack(ListNode* plist);
// 双向链表头插
void ListPushFront(ListNode* plist, LTDataType x);
// 双向链表头删
void ListPopFront(ListNode* plist);
// 双向链表查找
ListNode* ListFind(ListNode* plist, LTDataType x);
// 双向链表在pos的前面进行插入
void ListInsert(ListNode* pos, LTDataType x);
// 双向链表删除pos位置的结点
void ListErase(ListNode* pos);

二、顺序表和链表的区别

不同点	顺序表	链表
存储空间上	物理上一定连续	逻辑上连续，但物理上不一定连续
随机访问	支持O(1)	不支持：O(N)
任意位置插入或者删除元素	可能需要搬移元素，效率低O(N)	只需修改指针指向
插入	动态顺序表，空间不够时需要扩容	没有容量的概念
应用场景	元素高效存储+频繁访问	任意位置插入和删除频繁
缓存利用率	高	低

备注：缓存利用率参考存储体系结构 以及 局部原理性。

与程序员相关的CPU缓存知识

三、单项链表实现具体代码

text.h

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

typedef int SLTDataType;

typedef struct SListNode
{
	SLTDataType data;
	struct SListNode* next;
}SLTNode,*Node;

void SLTPrint(Node phead);
Node SLTBuyNode(SLTDataType x);//开辟空间
//链表的头插、尾插
void SLTPushBack(Node* pphead, SLTDataType x);
void SLTPushFront(Node* pphead, SLTDataType x);

//链表的头删、尾删
void SLTPopBack(Node* pphead);//尾删
void SLTPopFront(Node* pphead);//头删

//查找
Node SLTFind(Node* pphead, SLTDataType x);

//在指定位置之前插入数据
void SLTInsert(Node*  pphead, Node pos, SLTDataType x);
//在指定位置之后插入数据
void SLTInsertAfter(Node pos, SLTDataType x);

//删除pos节点
void SLTErase(Node* pphead, Node pos);
//删除pos之后的节点
void SLTEraseAfter(Node pos);

//销毁链表
void SListDesTroy(Node* pphead);

text.c

#include "text.h"
void SLTPrint(Node phead)
{
	assert(phead);
	Node purt = phead;
	while (purt)
	{
		printf("%d->", purt->data);
		purt = purt->next;
	}
	printf("NULL\n");
}
Node SLTBuyNode(SLTDataType x)
{
	Node str = (Node)malloc(sizeof(SLTNode));
	assert(str);
	str->data = x;
	str->next = NULL;
	return str;
}
void SLTPushBack(Node* pphead, SLTDataType x)
{
	assert(pphead);
	Node newnode = SLTBuyNode(x);
	if (*pphead == NULL)
	{
		*pphead = newnode;
	}
	else
	{
		Node ptail = *pphead;
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next = newnode;
	}
}
void SLTPushFront(Node* pphead, SLTDataType x)
{
	assert(pphead);
	Node newnode = SLTBuyNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}
void SLTPopBack(Node* pphead)
{
	assert(pphead);
	assert(*pphead);
	if ((*pphead)->next == NULL)
	{
		free(*pphead);
		*pphead = NULL;
	}
	Node ptail = *pphead;
	while (ptail->next->next)
	{
		ptail = ptail->next;
	}
	free(ptail->next);
	ptail->next= NULL;
}
void SLTPopFront(Node* pphead)
{
	assert(pphead);
	assert(*pphead);
	Node next = (*pphead)->next;
	free(*pphead);
	(*pphead) = next;
}
Node SLTFind(Node* pphead, SLTDataType x)
{
	assert(pphead);
	assert(*pphead);
	Node next = *pphead;
	while (next)
	{
		if (next->data == x)
		{
			printf("找到了\n");
			return next;
		}
		next = next->next;
	}
	return NULL;
}
void SLTInsert(Node* pphead, Node pos, SLTDataType x) {
	assert(pphead);
	assert(pos);
	//要加上链表不能为空
	assert(*pphead);

	Node newnode = SLTBuyNode(x);
	//pos刚好是头结点
	if (pos == *pphead) {
		//头插
		SLTPushFront(pphead, x);
		return;
	}

	//pos不是头结点的情况
	Node prev = *pphead;
	while (prev->next != pos)
	{
		prev = prev->next;
	}
	//prev -> newnode -> pos
	prev->next = newnode;
	newnode->next = pos;
}
void SLTInsertAfter(Node pos, SLTDataType x)
{
	assert(pos);
	Node newnode = SLTBuyNode(x);
	newnode->next = pos->next;
	pos->next = newnode;
}
void SLTErase(Node* pphead, Node pos)
{
	assert(pphead);
	assert(*pphead);
	assert(pos);
	Node node = *pphead;
	if (pos == *pphead)
	{
		SLTPopFront(&pos);
	}
	while (node->next != pos)
	{
		node = node->next;
	}
	node->next = pos->next;
	free(pos);
	pos = NULL;
}
void SLTEraseAfter(Node pos)
{
	assert(pos);
	assert(pos->next);
	Node next = pos->next,pre;
	while (next)
	{
		pre = next->next;
		free(next);
		next = pre;
	}
	pos->next = NULL;
}
void SListDesTroy(Node* pphead) {
	assert(pphead);
	assert(*pphead);
	Node pcur = *pphead;
	while (pcur)
	{
		Node next = pcur->next;
		free(pcur);
		pcur = next;
	}
	*pphead = NULL;
}

main.c

#include"text.h"

void SlistTest01() {
	//一般不会这样去创建链表，这里只是为了给大家展示链表的打印
	SLTNode* node1 = (SLTNode*)malloc(sizeof(SLTNode));
	node1->data = 1;
	SLTNode* node2 = (SLTNode*)malloc(sizeof(SLTNode));
	node2->data = 2;
	SLTNode* node3 = (SLTNode*)malloc(sizeof(SLTNode));
	node3->data = 3;
	SLTNode* node4 = (SLTNode*)malloc(sizeof(SLTNode));
	node4->data = 4;

	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;

	SLTNode* plist = node1;
	SLTPrint(plist);
}
void SlistTest02() {
	Node plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist); //1->2->3->4->NULL

	SLTPushFront(&plist, 5);
	SLTPrint(plist);          //5->1->2->3->4->NULL
	SLTPushFront(&plist, 6);
	SLTPrint(plist);         //6->5->1->2->3->4->NULL
	SLTPushFront(&plist, 7);
	SLTPrint(plist);         //7-6->5->1->2->3->4->NULL

	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
	SLTPopBack(&plist);
	SLTPrint(plist);//1->2->3->NULL
}

void SlistTest03() {
	Node plist = NULL;
	SLTPushBack(&plist, 1);
	SLTPushBack(&plist, 2);
	SLTPushBack(&plist, 3);
	SLTPushBack(&plist, 4);
	SLTPrint(plist); //1->2->3->4->NULL

	/*SListDesTroy(&plist);*/
	//头删
	SLTPopFront(&plist);
	SLTPrint(plist);    //2->3->4->NULL
	SLTPopFront(&plist);
	SLTPrint(plist);    //3->4->NULL
	SLTPopFront(&plist);
	SLTPrint(plist);    //4->NULL
	//SLTPopFront(&plist);
	//SLTPrint(plist);    //NULL
	SLTPopFront(&plist);
	SLTPrint(plist);    //assert
	
	SLTNode* FindRet = SLTFind(&plist, 3);
	if (FindRet) {
		printf("找到了！\n");
	}
	else {
		printf("未找到！\n");
	}
	//SLTInsert(&plist, FindRet, 100);
	//SLTInsertAfter(FindRet, 100);
	//
	删除指定位置的节点
	//SLTErase(&plist, FindRet);
	//SLTPrint(plist); //1->2->3->NULL
}
int main() {
	//SlistTest01();
	/*SlistTest02();*/
	SlistTest03();
	return 0;
}

单链表的打印

void SLTPrint(Node phead)

void SLTPrint(Node phead)
{
	assert(phead);
	Node purt = phead;
	while (purt)
	{
		printf("%d->", purt->data);
		purt = purt->next;
	}
	printf("NULL\n");
}

单链表的打印是链表操作中的一个基础且重要的环节。链表是一种常见的数据结构，它由一系列节点组成，每个节点包含数据部分和指向下一个节点的指针。而单链表则是链表的一种，它的特点是每个节点只包含一个指向下一个节点的指针。

在打印单链表时，我们通常需要遍历整个链表，依次访问每个节点，并输出节点的数据部分。这个过程可以通过设置一个指针，初始时指向链表的头节点，然后不断将指针移动到下一个节点，直到指针为空，即遍历完整个链表。

为了实现单链表的打印，我们可以定义一个函数，该函数接受链表的头节点作为参数。在函数内部，我们使用一个循环来遍历链表。在每次循环中，我们输出当前节点的数据部分，并将指针移动到下一个节点。当指针为空时，循环结束，打印操作完成。

空间的开辟

Node SLTBuyNode(SLTDataType x);//开辟空间

Node SLTBuyNode(SLTData