链表基础知识（一、单链表、头插、尾插、头删、尾删、查找、删除、插入）

3.1

一、链表表示和实现

顺序表的问题及思考
问题：
1. 中间/头部的插入删除，时间复杂度为O(N)
2. 增容需要申请新空间，拷贝数据，释放旧空间。会有不小的消耗。
3. 增容一般是呈2倍的增长，势必会有一定的空间浪费。例如当前容量为100，满了以后增容到
200，我们再继续插入了5个数据，后面没有数据插入了，那么就浪费了95个数据空间。
思考：
如何解决以上问题呢？下面给出了链表的结构来看看。

1.1 链表的概念及结构

概念：链表是一种物理存储结构上非连续、非顺序的存储结构，用于存储逻辑关系为 “一对一” 的数据。链表中每个数据的存储都由以下两部分组成：
1.数据元素本身，其所在的区域称为数据域。
2.指向直接后继元素的指针，所在的区域称为指针域。

（单链表的节点）

数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

1.2简易理解链表概念

链表的结构跟火车车厢相似，淡季时车次的车厢会相应减少，旺季时车次的车厢会额外增加几节。只需要将火车里的某节车厢去掉/加上，不会影响其他车厢，每节车厢都是独立存在的。

车厢是独立存在的，且每节车厢都有车门。想象一下这样的场景，假设每节车厢的车门都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带一把钥匙的情况下如何从车头走到车尾？
最简单的做法：每节车厢里都放一把下一节车厢的钥匙。

1.21问：在链表里，每节“车厢”是什么样的呢？

如图：

与顺序表不同的是，链表里的每节”车厢”都是独立申请下来的空间，我们称之为“结点/节点”
节点的组成主要有两个部分：当前节点要保存的数据和保存下一个节点的地址（指针变量）。
图中指针变量 plist保存的是第一个节点的地址，我们称plist此时“指向”第一个节点，如果我们希
望plist“指向”第二个节点时，只需要修改plist保存的内容为0x0012FFA0。

1.22问：那为什么还需要指针变量来保存下一个节点的位置？

答：链表中每个节点都是独立申请的（即需要插入数据时才去申请一块节点的空间），我们需要通过指针变量来保存下一个节点位置才能从当前节点找到下一个节点。

结合前面学到的结构体知识，我们可以给出每个节点对应的结构体代码：
假设当前保存的节点为整型：

struct SListNode
{
int data; //节点数据
struct SListNode* next; //指针变量用保存下一个节点的地址
};

当我们想要保存一个整型数据时，实际是向操作系统申请了一块内存，这个内存不仅要保存整型数
据，也需要保存下一个节点的地址（当下一个节点为空时保存的地址为空）。
当我们想要从第一个节点走到最后一个节点时，只需要在前一个节点拿上下一个节点的地址（下一个节点的钥匙）就可以了。

1.23给定的链表结构中，如何实现节点从头到尾的打印？

思考：当我们想保存的数据类型为字符型、浮点型或者其他自定义的类型时，该如何修改？
补充说明：
1、链式机构在逻辑上是连续的，在物理结构上不一定连续
2、节点一般是从堆上申请的
3、从堆上申请来的空间，是按照一定策略分配出来的，每次申请的空间可能连续，可能不连续。

二、链表的分类：

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

头节点：是一个节点，本质上是一个结构体变量，区分数据域和指针域，不存放任何数据，只存放指向链表中真正存放数据的第一个节点的地址，仅用于辅助管理整个链表的结构。
头指针：是一个指针，本质上是一个结构体类型的指针变量，不区分数据域和指针域，它仅存储链表中第一个节点的地址。
带头节点也就意味着不需要传二级指针了

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

2.2链表和顺序表的对比

三、单链表

3.1单链表的优劣：

1、查找速度慢

2、不能从后往前

3、找不到前驱

4、单向链表不能自我删除，需要靠辅助节点。

3.1无头+单向+非循环链表增删查改实现

无头单向非循环链表：结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结
构的子结构，如哈希桶、图的邻接表等等。另外这种结构在笔试面试中出现很多。

3.2DList.h

#pragma once //防止重复包含
#include<stdio.h>
#include<string.h>
#include<stdlib.h>
#include<assert.h>

typedef int SLTDataType;//方便改变数据类型
struct SListNode
{
	SLTDataType data;
	struct SListNode* next;//下一个地址
	//结构体中嵌套指针,但不能嵌套自己,会死循环
}SLTNode;
typedef struct SListNode STLNode;


// 不会改变链表的头指针，传一级指针
void SListPrint(STLNode* phead);

// 可能会改变链表的头指针，传二级指针
void SListPushBack(STLNode** pphead, SLTDataType x);
void SListPushFront(STLNode** pphead, SLTDataType x);//分有节点头插和无节点头插,尾插得分开处理
void SListPopFront(STLNode** pphead);
void SListPopBack(STLNode** pphead);

// 不会改变链表的头指针，传一级指针
STLNode* SListFind(STLNode* pphead, SLTDataType x);
// 在pos的前面插入x
void SListInsert(STLNode** pphead, STLNode* pos, SLTDataType x);
// 删除pos位置的值
void SListErase(STLNode** pphead, STLNode* pos);


有些地方也有这样定义
 在pos的前面插入x
//void SListInsert(STLNode** phead, int i, SLTDataType x);
 删除pos位置的值
//void SListErase(STLNode** phead, int i);

3.3打印链表

第一步：输出第一个节点的数据域，输出完毕后，让指针保存后一个节点的地址

第二步：输出移动地址对应的节点的数据域，输出完毕后，指针继续后移

第三步：以此类推，直到节点的指针域为NULL

void SListPrint(STLNode* phead)
{
	STLNode* cur = phead;
	while (cur != NULL)//第一个地址不为空
	{
		printf("%d->", cur->data);
		cur = cur->next;//令cur下一个地址
	}
	printf("NULL\n");

}

3.4新建一个节点

函数中的 malloc 用于在堆上分配内存。它返回一个指向新分配内存的指针，该指针被转换为 stlNode* 类型并存储在 newnode 变量中。这个新节点被初始化为包含一个 data 字段和一个 next 字段，其中 data 字段被设置为参数 x 的值，而 next 字段被初始化为 NULL。

STLNode* BuySListNode(SLTDataType x)
{
	STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
	newnode->data = x;
	newnode->next = NULL;
}

3.5尾插

void SListPushBack(STLNode** pphead, SLTDataType x)
//void SListPushBack(STLNode*& pphead, SLTDataType x)
//在					C++语法中可以加&,引用,别名
{
	STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
	newnode->data = x;
	newnode->next = NULL;
	
	// 找尾节点的指针
	if (*pphead == NULL)//pphead是plist的地址
	{
		*pphead = newnode;//在尾部创建新节点
	}
	else {
		STLNode* tail = *pphead;//phead在开始时为空
		while (tail->next != NULL)//判断下一个指针是否为空
		{
			tail = tail->next;//指向下一个节点
		}

		// 尾节点，链接新节点
		tail->next = newnode;
	}
}

3.6头插

void SListPushFront(STLNode** pphead, SLTDataType x)
{
	STLNode* newnode = BuySListNode(x);//新建一个节点
	newnode->next = *pphead;//在第一个地址前建立一个新节点
	*pphead = newnode;//使新节点变为第一个地址
}

3.7头删

void SListPopFront(STLNode** pphead)
{
	STLNode* next = (*pphead)->next;//保存下一个地址
	free(*pphead);//释放空间
	*pphead = next;//令其指针指向下一个地址
}

3.8尾删

尾删的目的是从给定的单链表中删除最后一个节点，所以分三种情况：

1、链表为空

2、链表只有一个节点

3、链表有多个节点

链表为空：

如果链表为空（*pphead == NULL），那么就没有什么可以删除的内容，所以函数直接返回。

只有一个节点时：

有多个节点时：

如果链表有多个节点，我们需要找到链表的最后一个节点，并删除它。为了找到最后一个节点，我们设置两个指针 prev 和 tail，开始时都指向链表头。然后我们遍历链表，直到找到最后一个节点。找到后，我们释放最后一个节点的内存，然后把倒数第二个节点的 next 设置为 NULL，表示链表最后一个节点已经被删除。

void SListPopBack(STLNode** pphead)
{
	//1.空
	//2.一个节点
	//3.一个以上节点
	if (*pphead == NULL)//1.空
    //如果为空，说明链表已经为NULL，没有可以删除的内容了
	{
		return;
	}
	else if ((*pphead)->next == NULL)//2.一个节点
	{
		free(*pphead);//1.先释放
		*pphead = NULL;//2.把plist置成空
	}
	else {
        //3.一个以上节点
		STLNode* prev = NULL;
		STLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	
	}
}

3.9查找

其实就是遍历一遍链表，但是只能返回第一次出现的地址。我们查找到节点的地址后就可以通过地址去修改数据域中存储的数据。

TLNode* SListFind(STLNode* phead, SLTDataType x)
{
	STLNode* cur = phead;
	while (cur != NULL)
	//while (cur)
	{
		if (cur->data = x)
		{
			return cur;//找到了
		}
		cur = cur->next;
	}
	return NULL;
}

3.10在pos的前面插入

//创建新节点 stlNode* newnode = BuySListNode(x);
// 初始时，prev 指向链表的头节点 pphead。 stlNode* prev = *pphead;
while (cur != pos) // 这个 while 循环用于找到 pos 节点。
prev = prev->next; cur = cur->next; //如果 cur 不等于 pos，那么移动 prev 和 cur。prev 移动到 cur 的下一个节点。cur 移动到下一个节点。
prev->next = newnode;//现在，prev 指向 pos 的前一个节点，cur 指向 pos 节点本身。我们将新节点插入到 prev 和 cur 之间。
prev->next = newnode; // 然后，我们将新节点的 next 指向 pos，这样新节点就位于 pos 之前了。

void SListInsert(STLNode** pphead, STLNode* pos, SLTDataType x)
{
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else {
		STLNode* newnode = BuySListNode(x);
		STLNode* prev = *pphead;
		/*while (prev->next != pos)*/
		STLNode* cur = *pphead;
		while (cur != pos)
		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	
	}
}

3.11删除pos位置的值

void SListErase(STLNode** pphead, STLNode* pos)
{
	if (pos == *pphead)//如果要删除的是头节点
	{
		SListPopFront(pphead);//头删
	}
	else {
		STLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;//删除指定位置的节点
		free(pos);//释放要删除节点的内存
	}
}

四、DList.c

#include"SeqList.h"

void SListPrint(STLNode* phead)
{
	STLNode* cur = phead;
	while (cur != NULL)//第一个地址不为空
	{
		printf("%d->", cur->data);
		cur = cur->next;//令cur下一个地址
	}
	printf("NULL\n");

}

STLNode* BuySListNode(SLTDataType x)
{
	STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
	newnode->data = x;
	newnode->next = NULL;
}

//尾插
void SListPushBack(STLNode** pphead, SLTDataType x)
//void SListPushBack(STLNode*& pphead, SLTDataType x)
//在					C++语法中可以加&,引用,别名
{
	STLNode* newnode = (STLNode*)malloc(sizeof(STLNode));
	newnode->data = x;
	newnode->next = NULL;
	
	// 找尾节点的指针
	if (*pphead == NULL)//pphead是plist的地址
	{
		*pphead = newnode;
	}
	else {
		STLNode* tail = *pphead;//phead在开始时为空
		while (tail->next != NULL)//判断下一个指针是否为空
		{
			tail = tail->next;
		}

		// 尾节点，链接新节点
		tail->next = newnode;
	}
}


void SListPushFront(STLNode** pphead, SLTDataType x)
{
	STLNode* newnode = BuySListNode(x);
	newnode->next = *pphead;
	*pphead = newnode;
}


void SListPopFront(STLNode** pphead)
{
	STLNode* next = (*pphead)->next;//保存下一个地址
	free(*pphead);//释放空间
	*pphead = next;//令其指针指向下一个地址
}

void SListPopBack(STLNode** pphead)
{
	//1.空
	//2.一个节点
	//3.一个以上节点
	if (*pphead == NULL)
	{
		return;
	}
	else if ((*pphead)->next == NULL)
	{
		free(*pphead);//1.先释放
		*pphead = NULL;//2.把plist置成空
	}
	else {
		STLNode* prev = NULL;
		STLNode* tail = *pphead;
		while (tail->next != NULL)
		{
			prev = tail;
			tail = tail->next;
		}
		free(tail);
		prev->next = NULL;
	
	}
}


STLNode* SListFind(STLNode* phead, SLTDataType x)
{
	STLNode* cur = phead;
	while (cur != NULL)
	//while (cur)
	{
		if (cur->data = x)
		{
			return cur;//找到了
		}
		cur = cur->next;
	}
	return NULL;
}

// 在pos的前面插入x
void SListInsert(STLNode** pphead, STLNode* pos, SLTDataType x)
{
	if (pos == *pphead)
	{
		SListPushFront(pphead, x);
	}
	else {
		STLNode* newnode = BuySListNode(x);
		STLNode* prev = *pphead;
		/*while (prev->next != pos)*/
		STLNode* cur = *pphead;
		while (cur != pos)

		{
			prev = prev->next;
		}
		prev->next = newnode;
		newnode->next = pos;
	
	}
}
// 删除pos位置的值
void SListErase(STLNode** pphead, STLNode* pos)
{
	if (pos == *pphead)
	{
		SListPopFront(pphead);
	}
	else {
		STLNode* prev = *pphead;
		while (prev->next != pos)
		{
			prev = prev->next;
		}
		prev->next = pos->next;
		free(pos);
	}
}

五、Test.c

#include"SeqList.h"

void TestSList1()
{
	STLNode* plist = NULL;//先让plist指向空
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	//插入几个值,用节点存起来
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPushFront(&plist, 0);
	SListPrint(plist);
	
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPrint(plist);
	
	SListPopFront(&plist);
	SListPopFront(&plist);
	SListPrint(plist);
}
void TestSList3()
{
	STLNode* plist = NULL;//先让plist指向空
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	//插入几个值,用节点存起来
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

	/*SListPopBack(&plist);
	SListPopBack(&plist);
	SListPrint(plist);*/
	//想在3的前面插入一个数字
	STLNode* pos = SListFind(plist, 1);
	if (pos)
	{
		SListInsert(&plist, pos, 10);
	}
	SListPrint(plist);

	pos = SListFind(plist, 3);
	if (pos)
	{
		SListInsert(&plist, pos, 30);
	}
	SListPrint(plist);
}

void TestSList4()
{
	STLNode* plist = NULL;//先让plist指向空
	SListPushBack(&plist, 1);
	SListPushBack(&plist, 2);
	SListPushBack(&plist, 3);
	SListPushBack(&plist, 4);
	SListPrint(plist);

	STLNode* pos = SListFind(plist, 3);
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);

	pos = SListFind(plist, 4);
	if (pos)
	{
		SListErase(&plist, pos);
	}
	SListPrint(plist);
}

int main()
{
	TestSList4();

	return 0;
}

今天就先到这了！！！

看到这里了还不给博主扣个：
⛳️ 点赞☀️收藏 ⭐️ 关注！

你们的点赞就是博主更新最大的动力！
有问题可以评论或者私信！！!

关注必回！！！

文章出处登录后可见！

已经登录？立即刷新