1.单链表

1.数据结构简介

程序=数据结构+算法

数据

数据（data）是客观事物的一个符号表示

数据元素（data element）是数据的基本单位，一个数据元素可以由若干个数据项（data item）组成。数据项是数据不可分割的最小单位。

数据结构

是数据元素之间相互关系的集合

逻辑结构 逻辑层面：同窗

数据元素之间存在的逻辑关系

集合：

数据结构中的元素之间除了“同属一个集合”的相互关系外，别无其他关系

**线性结构： **排队：一列

数据结构中的元素存在一对一的相互关系，如数组（索引）、链表（指针）、栈和队列（操作顺序）等。

**树形结构： **排队：方队

数据结构中的元素存在一对多的相互关系，如树和二叉树（一个父节点对应多个子节点）等

图形结构：

数据结构中的元素存在多对多的相互关系，如图（每个节点都可以与多个节点相连，同时它也可以被多个节点所连接。）等

物理结构(存储结构)

数据的物理结构或存储结构是数据在计算机中的存储表示或实现

顺序结构：

数据元素在物理位置上相邻，通过元素的存储地址来表示数据元素之间的逻辑关系，比如数组

链表结构：

对逻辑上相邻的元素不要求其物理位置相邻，元素间的逻辑关系通过附设的指针域来表示

索引结构：

为每个数据结构建立索引表，每个数据元素占用表中的一项，每个表项通常包含关键字和地址指针 map

散列结构（哈希结构）：

根据数据元素的关键字通过哈希函数计算出一个数值用作数据元素的存储地址，以实现快速查找和插入

2.线性表（逻辑上）

它表示元素之间具有一对一的相邻关系的数据集合。

线性表的数据元素可以是各种各样、但是同一个线性表中的元素必须是相同类型。

特性：

存在唯一的一个被称为："第一个"的数据元素

存在唯一的一个被称为：“最后一个”的数据元素

除了第一个元素之外，集合中的每一个数据元素前均只有一个节点

除了最后一个元素之外，集合中的每一个数据元素后均只有一个节点

线性表可以是顺序结构也可以是链表结构.。顺序存储的线性表通常通过数组（Array）实现，而链式存储的线性表则通过链表（Linked List）实现

2.1顺序存储的线性表（数组）

在C++中，数组是最简单的顺序存储的线性表实现。数组中的元素在内存中连续存放，每个元素可以通过索引（或下标）快速访问。

例子：

#include <iostream>  
using namespace std;  
int main() 
{  
int arr[5] = {1, 2, 3, 4, 5}; // 定义一个整型数组，大小为5  
for(int i = 0; i < 5; i++) 
{  
cout << arr[i] << " "; // 访问并打印数组中的每个元素  
}

上述结构存在一些问题问题：我们在定义数组的时候，需要规定数组的长度，定义好了就不能修改了。

int a[10]; // 定义了一个元素为int类型的数组，数组大小为10个int类型
// 修改数组的大小
a = malloc(sizeof(int) * 100); // 不行的，因为a是常量指针，不能改变a指向。

*2.1链式存储的线性表（链表）**

链表的定义：链表就是由一个或者是多个包含指针成员变量的结构体.

struct 类型名
{
类型1 变量1; // 数据1...
类型n 变量n; // 数据nstruct 类型名 *指针变量; // 存储数据元素的地址。在单链表结构里面，存储下一个数据元素的内
存地址
}

通过其指针变量来指向其他同类型结构体内存地址来形成一种逻辑上的链式的数据结构。我们把每一个结构体实例（变量/空间）称为该链表的：节点（node)

链表中的每个元素都是一个节点（Node），节点之间通过指针连接。链表分为单向链表、双向链表和循环链表等多种类型。

***问题1：***为什么是 struct （结构体）？

因为包含指针成员，，记录下一个元素的地址。而其他数据类型可能与指针类型不同，因此需要能够存放 不同数据类型的结构，因此是结构体。

问题2：：为什么指针成员是 struct 类型名 *（当前结构体指针类型）？

因为需要存放下一个元素的地址，而下一个元素是 struct 类型名类型的。如果是 struct 类型名，要为当前类型分配空间，因为结构题没有定义完全**，没有办法分配内存**。

struct 类型名 *的话是指针，无论什么类型指针都是分配八个字节。

特殊的节点：

***头节点：***是链表中唯一一个没有前节点、只有后节点的节点，是整个链表的第一个节点（开端）。

***尾节点：***是链表中唯一一个没有后节点，只有前节点的节点，是整个链表的最后一个节点（结尾）。因此尾节点的指针指向空( NULL )，以保证尾节点的指针成员不会成为野指针。可以通过判断指针是否指向空来判断是不是查询到了最后一个元素。

画个图
在这里插入图片描述

2.3链表的创建过程

(单链表 Singly Linked List)

2.3.1 定义链表节点结构

首先，需要定义一个链表节点的结构体，该结构体至少包含两个成员：存储数据的部分（数据域）和指向下一个节点的指针（指针域）。

//定义链表节点结构
typedef struct listNode{int val; // 整型数据  
struct li

2.3.2 初始化链表头指针

在创建链表之前，需要初始化链表的头指针。头指针是一个指向链表第一个节点的指针。如果链表为空，则头指针通常设置为 NULL 。

//初始化链表头指针
ListNode* head = NULL; // 初始化链表为空链表

在这里插入图片描述

创建并添加节点到链表

接下来，可以通过创建新的节点并将其插入到链表中来构建链表。插入操作可以根据需要在链表的不同位置进行（如头部、尾部或特定位置）。

2.3.3 创建节点

//创建节点 value新节点存储的数据
//可以是普通结构体变量，但是之后用到的要&listNode *createNode(int value)
{listNode *newNode=new listNode{ value};//动态分配内存，设置新节点的值if(newNode!=NULL){newNode->next=NULL;//新节点的next指针初始化为NULL，没有后面的元素}return newNode;//此处可以返回局部变量的地址是因为newNode在堆区，生命周期在delete后才结
束}

推荐创建节点时用 new/malloc 在堆区申请节点，而不是栈区。

因为堆区空间由程序员维护，可以控制其声明周期，

而栈区内存空间由编译器维护，无法控制生命周期，有可能内存空间被意外收回。

2.3.4 插入节点

如果头节点为空，新创建的节点即为头节点

在这里插入图片描述

头插直接让新节点指向头节点，那么新节点就变成了新的头节点

//头插 2-3   ->   1-2-3直接让新节点指向头节点，新节点变成新的头节点
//头部添加节点//希望形参影响实参
listNode *insertNodeAtHead(listNode*head/*头节点的地址*/,int value/*数据*/)//head是一级指针要有返回值，
// 因为是值传递，用返回值更新head指向 二级指针不需要 地址传递
{if(head==NULL){//链表是空，新节点就是头节点head=createNode(value);return head;}![屏幕截图 2025-03-31 065839](D:\笔记\4-2 数据结构 （复习笔记）\屏幕截图 2025-03-31 065839.png)//创建新节点listNode *newHead=createNode(value);//让新节点指向头节点newHead->next=head;//返回新的头节点return newHead;}

添加头节点如果为空直接创建，新节点就是头节点，如果不为空直接让新节点指向头节点，新节点变成新的头节
在这里插入图片描述

尾部插入：如果要在链表尾部添加节点，需要遍历链表直到最后一个节点，然后将最后一个节点的next指针指向新节点

//尾部添加节点
listNode *insertNodeAtTail(listNode*head,int value)
{if(head==NULL){//链表是空，新节点就是头节点head=createNode(value);}else{  //定义中间变量，找到尾节点listNode *current=head;while( current->next==NULL){//向后遍历current==current->next;}//current指向尾节点 ，尾节点next指向新节点current->next=createNode(value);}//返回头节点 在调用该函数时要用head接受该返回值来更新头节点return head;}

在这里插入图片描述

中间插入：：按照一定规则在某个位置插入元素

//中间插入（从小到大）
//head:链表的头节点 newNode：插入节点
listNode *insertNodeAtMiddle(listNode*head,int value)
{if(head==NULL){//链表是空，新节点就是头节点head=createNode(value);}else{//比头节点小， 例如：2-3 头插if(value<head->val);{// 头插head=insertNodeAtHead(head,value);//结束return head;}//前面的节点listNode*first=head;//下一个的节点listNode*second=first->next;/*在两者之间插入 只需要在first和second之间插入 链表只有一个元素 first：1 second null 直接掺入first后只要second为空 直接尾插*///first不是尾节点while(second){//判断相邻两个节点的大小关系if(value>first->val&&value<second->val){listNode *newNode =createNode(value);//创建节点//一定是先连接后面节点，在连接前面节点，因为节点只记录了下一个节点的地址信// 息，如果先连接前面，则后面的地址信息就丢失了//先连接后面的节点，即先连接2-3newNode->next=second;//然后让前面的节点指向新节点，即1-2first->next=newNode;return head;}//向后遍历first=second;second=second->next;}//1-2-3   4  尾插head=insertNodeAtTail(head,value);}}

在这里插入图片描述

附加：

值传递和地址传递区别-------形参修改会不会影响实参

实参 int 形参 int 值传递 形参不会影响实参

实参 int 形参 int* 地址传递 形参会影响实参

实参 int* 形参 int* 值传递* 形参不会影响实参

2.3.5 删除链表中的节点

将链表中某个节点删除，删除时要注意，创建节点时申请了内存，删除时要释放内存以防止内存泄露，同时将指针置为空

//删除节点listNode  *deteleNode(listNode*head,int value)
{if (head==NULL){//如果链表是空，结束return 0;}else if(value==head->val){//纪律新的头节点listNode*newHead=head->next;//删除头节点。防止内存泄漏delete head;//更新头节点head=newHead;}//非头节点else{listNode*current=head;//遍历链表while(current->next){//只使用一个指针 删除当前节点的下一个节点if(current->next->val==value){// 当前节点的下一个节点 1-2-3 delete 2 变成1-3listNode* needDeleNode =current->next;//中间节点if(current->next->next ){//更新节点指向current->next= current->next->next;}//尾节点1-2 删除2 变1else{![屏幕截图 2025-03-31 070326](D:\笔记\4-2 数据结构 （复习笔记）\屏幕截图 2025-03-31 070326.png)current->next=NULL;}//删除下一个节点delete needDeleNode;needDeleNode=NULL;//提前结束return head;}current=current->next;//向后遍历}}//没有找到删除节点信息 return head;}

在这里插入图片描述

链表使用完毕记得要删除所有节点，防止内存泄露

void deinitNode(listNode*&head)
{//判断链表是不是空链表if(head==NULL){std::cout<<"链表为空"<<std::endl;return ;}listNode *current=head;while(current){//要删除的节点listNode *needDelNode=current;//遍历current=current->next;//删除节点delete  needDelNode;needDelNode=NULL;}}

2. 4 完整代码

#include <iostream>using namespace std;
//定义链表节点结构
typedef struct listNode
{int val;//整形数据struct listNode *next;//指向下一个节点的指针//listNode *next;不行，因为listNode没有定义出来
}listNode;//创建节点 value新节点存储的数据
//可以是普通结构体变量，但是之后用到的要&
listNode *createNode(int value)
{listNode *newNode=new listNode{value};//动态分配内存，设置新节点的值if(newNode!=NULL){newNode->next=NULL;//新节点的next指针初始化为NULL，没有后面的元素}return newNode;}//头插 2-3   ->   1-2-3直接让新节点指向头节点，新节点变成新的头节点
//头部添加节点
//希望形参影响实参
listNode *insertNodeAtHead(listNode*head,int value)//head是一级指针要有返回值，// 因为是值传递，用返回值更新head指向 二级指针不需要 地址传递
{if(head==NULL){//链表是空，新节点就是头节点head=createNode(value);return head;}//创建新节点listNode *newHead=createNode(value);//让新节点指向头节点newHead->next=head;//返回新的头节点return newHead;}
//尾部添加节点
listNode *insertNodeAtTail(listNode*head,int value)
{if(head==NULL){//链表是空，新节点就是头节点head=createNode(value);}else{  //定义中间变量，找到尾节点listNode *current=head;while( current->next){//向后遍历current=current->next;}//current指向尾节点 ，尾节点next指向新节点current->next=createNode(value);}//返回头节点 在调用该函数时要用head接受该返回值来更新头节点return head;}//中间插入（从小到大）
//head:链表的头节点 newNode：插入节点
listNode *insertNodeAtMiddle(listNode*head,int value)
{if(head==NULL){//链表是空，新节点就是头节点head=createNode(value);}else{//比头节点小， 例如：2-3 头插if(value<head->val){// 头插head=insertNodeAtHead(head,value);//结束return head;}//前面的节点listNode*first=head;//下一个的节点listNode*second=first->next;/*在两者之间插入 只需要在first和second之间插入 链表只有一个元素 first：1 second null 直接掺入first后只要second为空 直接尾插*///first不是尾节点while(second){//判断相邻两个节点的大小关系if(value>first->val&&value<second->val){listNode *newNode =createNode(value);//创建节点//一定是先连接后面节点，在连接前面节点，因为节点只记录了下一个节点的地址信// 息，如果先连接前面，则后面的地址信息就丢失了//先连接后面的节点，即先连接2-3newNode->next=second;//然后让前面的节点指向新节点，即1-2first->next=newNode;return head;}//向后遍历first=second;second=second->next;}// listNode*current=head;// while(value)//1-2-3   4  尾插head=insertNodeAtTail(head,value);}return head;
}
//删除节点listNode  *deteleNode(listNode*head,int value)
{if (head==NULL){//如果链表是空，结束return 0;}else if(value==head->val){//纪律新的头节点listNode*newHead=head->next;//删除头节点。防止内存泄漏delete head;//更新头节点head=newHead;}//非头节点else{listNode*current=head;//遍历链表while(current->next){//只使用一个指针 删除当前节点的下一个节点if(current->next->val==value){// 当前节点的下一个节点 1-2-3 delete 2 变成1-3listNode* needDeleNode =current->next;//中间节点if(current->next->next ){//更新节点指向current->next= current->next->next;}//尾节点1-2 删除2 变1else{delete current->next;current->next=NULL;}//删除下一个节点delete needDeleNode;needDeleNode=NULL;//提前结束return head;}current=current->next;//向后遍历}}//没有找到删除节点信息 return head;}//打印链表
void printtNode(listNode*head)
{//判断链表是不是空链表if(head==NULL){std::cout<<"链表为空"<<std::endl;return ;}listNode *current=head;//遍历while (current){std::cout<<current->val<<" ";   //输出内容current=current->next;}std::cout<<std::endl;
}//清空链表
void deinitNode(listNode*&head)
{//判断链表是不是空链表if(head==NULL){std::cout<<"链表为空"<<std::endl;return ;}listNode *current=head;while(current){//要删除的节点listNode *needDelNode=current;//遍历current=current->next;//删除节点delete  needDelNode;needDelNode=NULL;}}int main()
{// 初始化链表头指针listNode *head=NULL;//初始化链表为空链表//head=insertNodeAtHead的返回值//插入head=insertNodeAtMiddle(head,1);//头head=insertNodeAtMiddle(head,5);//尾head=insertNodeAtMiddle(head,3);//中间head=insertNodeAtMiddle(head,4);//中间head=insertNodeAtMiddle(head,2);//中间//打印printtNode(head);//删除head= deteleNode(head,1);//头head= deteleNode(head,5);//尾head= deteleNode(head,3);//中间printtNode(head);    //打印//清理链表deinitNode(head);//写完一个验证一个return 0;}