当前位置：首页 > article >正文

单链表：数据结构的灵动之链

article 2025/3/29 18:32:20

本文主要讲解链表的概念和结构以及实现单链表

一、链表的概念及结构

二、单链表的实现

1.1链表的实现：

1.2单链表的实现：

单链表尾插：

单链表的头插：

单链表的尾删：

单链表头删：

单链表查找：

单链表在pos位置之后插入x：

单链表删除pos位置之后的值：

在pos的前面插入：

删除pos位置：

销毁：

整体实现：

一、链表的概念及结构

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

链表的结构跟⽕⻋⻋厢相似，淡季时⻋次的⻋厢会相应减少，旺季时⻋次的⻋厢会额外增加⼏节。只需要将⽕⻋⾥的某节⻋厢去掉/加上，不会影响其他⻋厢，每节⻋厢都是独⽴存在的。概念：链表是⼀种物理存储结构上⾮连续、⾮顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。
⻋厢是独⽴存在的，且每节⻋厢都有⻋⻔。想象⼀下这样的场景，假设每节⻋厢的⻋⻔都是锁上的状态，需要不同的钥匙才能解锁，每次只能携带⼀把钥匙的情况下如何从⻋头⾛到⻋尾？
最简单的做法：每节⻋厢⾥都放⼀把下⼀节⻋厢的钥匙。

其中，下一节车厢的钥匙就是，下一个节点的地址，也就是下一个节点的指针

typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

next指针就相当于是下一节车厢的钥匙

链表中每一节车厢都是malloc独立申请下来的空间，我们称之为节点，节点主要由数据以及下一个节点的地址组成，所以我们要用结构体来封装

当然，如果我们想要保存的数据是字符型或者是浮点型，只需要写一个，这个随时可以替换

typedef int SLTDateType;

链式结构在逻辑上是连续的，在物理结构上不⼀定连续
节点⼀般是从堆上申请的
从堆上申请来的空间，是按照⼀定策略分配出来的，每次申请的空间可能连续，可能不连续

二、单链表的实现

1.1链表的实现：

首先，创建链表，把链表连接起来

#pragma once
#include <stdio.h>
#include <stdlib.h>
#include <assert.h>
typedef int SLTDateType;
typedef struct SListNode
{
	SLTDateType data;
	struct SListNode* next;
}SListNode;

#include "slist.h"
void SListNodeTest()
{
	SListNode* node1 = (SListNode*)malloc(sizeof(SListNode));
	node1->data = 1;
	SListNode* node2 = (SListNode*)malloc(sizeof(SListNode));
	node2->data = 2;
	SListNode* node3 = (SListNode*)malloc(sizeof(SListNode));
	node3->data = 3;
	SListNode* node4 = (SListNode*)malloc(sizeof(SListNode));
	node4->data = 4;
	node1->next = node2;
	node2->next = node3;
	node3->next = node4;
	node4->next = NULL;
	SListPrint(node1);
}
int main()
{
	SListNodeTest();
	return 0;
}

打印的函数：

void SListPrint(SListNode* plist)
{
	assert(plist);
	SListNode* pcur = plist;
	while (pcur)
	{
		printf("%d->", pcur->data);
		pcur = pcur->next;
	}
	printf("\n");
}

把连接起来的结果打印一下

1.2单链表的实现：

需要记住的两点:

但凡添了新数据第一步都是要申请新的空间的
插入节点，记住一定要从后往前改变

单列表相比于顺序表是没有初始化的，他一开始就是创建一个结构体指针

void SListNodeTest1()
{
	SListNode* plist = NULL;
}

单链表尾插：

尾插首先需要找尾，但如果整个列表是空的的话，那就直接把newNode给*pphead,如果不是空的，就要找尾,定义一个ptail,不要动头节点*pphead,那ptail去尾插

// 单链表尾插
void SListPushBack(SListNode** pplist, SLTDateType x)
{
	SListNode* ptail = *pplist;
	SListNode* newNode=BuySListNode(x);
	if (ptail == NULL)
	*pplist = newNode;
	else
	{
		while (ptail->next)
		{
			ptail = ptail->next;
		}
		ptail->next=newNode;
	}
}

运行结果：

这里传的是二级指针，为什么要传二级指针呢？

一开始定义了一个结构体的指针置为NULL，这个指针是plist等于NULL，我给这个结构体指针给他newNode空间和nest指针以及date数据,让 phlist==newNode，相当于定义了一个数组arr ,让int *tmp去开辟malloc空间，成功了就让arr==tmp，为了真正的改变这个SlistNode *phlist我要知道它地址，相当于说我要给它赋值，由于函数结束，你的形参是不能影响实参的，所以说我要传它的地址，他是一级指针，所以我要传二级指针，为了真正能赋值，让phlist接收好这个节点的空间, 这是给一级指针赋值，想要真正改变一级指针，，你就要传他的地址，就要用二级指针接收

这是一个难点，头插也是一样