链表基础知识（一、单链表）

一、链表表示和实现

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

1.1 链表的概念及结构?

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

? ?（单链表的节点）

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

?

??

二、链表的分类：

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

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

• 头节点：是一个节点，本质上是一个结构体变量，区分数据域和指针域，不存放任何数据，只存放指向链表中真正存放数据的第一个节点的地址，仅用于辅助管理整个链表的结构。

• 头指针：是一个指针，本质上是一个结构体类型的指针变量，不区分数据域和指针域，它仅存储链表中第一个节点的地址。

• 带头节点也就意味着不需要传二级指针了

?

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

2.2链表和顺序表的对比

三、单链表

3.1单链表的优劣：

1、查找速度慢

2、 不能从后往前

3、找不到前驱

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

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

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

3.2SList.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);//释放要删除节点的内存
	}
}

四、SList.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;
}

今天就先到这了！！！

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

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

关注必回！！！