一、引言
1.1 知识框架
1.2 有了数组为什么还要链表？
在前面我们介绍过数组，数组中元素是存储在连续的内存位置在声明数组时，我们可以指定数组的大小，但这将限制数组可以存储的元素数量 例如我们声明的是 int arr[10]，那么arr数组最多可以存储10个数据元素 但是我们事先不知道元素的大小呢？ 我们该如何去做？
当然首先想到的是申请一个足够大的数组，但是内存中可能会没有足够大的连续内存空间
那么我们能不能设计一种数据结构，合理的利用内存的中的非连续空间呢？
链表是一种非常灵活的动态数据结构，也是一种线性表。但是并不会按线性的顺序存储数据，而是在每一个节点里存入到下一个节点的指针。链表是由数据域和指针域两部分组成的，它的组成结构如下：
链表不会将其元素存储在连续的内存位置中，所以我们可以任意添加链表元素的数量。
1.3 顺序表和链表的区别
顺序表的存储位置可以用一个简单直观的公式表示，它可以随机存取表中任一元素，但插入和删除操作需要移动大量元素。
链式存储线性表时，不需要使用地址连续的存储单元，即不要求逻辑上相邻的元素在物理位置上也相邻，它通过“链”建立元素之间的逻辑关系，因此插入和删除操作不需要移动元素，而只需修改指针，但也会失去顺序表可随机存取的优点。
二、单链表知识点
2.1 单链表的概念
考点：单链表的应用(2009、2012、2013、2015、2016、2019)
线性表的链式存储也称单链表，它是指通过一组任意的存储单元来存储线性表中的数据元素。为了建立数据元素之间的线性关系，对每个链表结点，除存放元素自身的信息外，还需要存放一个指向其后继的指针。
单链表结点结构如图 2.3 所示，其中 data 为数据域，存放数据元素；next 为指针域，存放其后继结点的地址。
2.2 链表结构
#include <stdio.h>
#include <stdlib.h>
#define ElemType int
typedef struct LNode {
int data; // 数据域
struct LNode * next; // 指针域
} LNode, *LinkList;
- data：数据域，也是节点的值
- next：指针域，指向下一个结点的指针
图解：
💡之所以称为单链表，并不是指它是只有一个链表结点组成，是为了明确它是“单向的”，即每个节点只包含一个指向下一个结点的指针。 这与后面要讲的双向链表不同，所以也可以把单链表称为单向链表。
2.3 单链表的优缺点
单链表和数组都是常见的数据结构，各有优缺点。
单链表的节点在需要时动态分配内存，这意味着不需要像数组那样在创建时预先分配一大片连续内存。因此，单链表在内存使用上更加灵活，可以有效应对内存碎片和动态增长的问题。
由于链表节点是在需要时分配的，可以避免数组因初始化大小不确定而造成的内存浪费。例如，如果数组大小初始化过大，未使用的部分将浪费内存；若初始化过小，则可能需要频繁重新分配和复制。
每个节点需要一个指针域来存储对下一个节点的引用，这意味着相比于数组，单链表在每个节点上都会有额外的内存开销。对于存储小数据的场景，这个开销相对较大，可能导致内存利用率下降。
单链表的特点
- 非随机存取的存储结构，也称顺序存储结构 – 不能直接找到表中某个特定的结点，查找特定结点的时候，需要从表头开始遍历，依次查找
- 因为附加指针域，存在浪费存储空间的
2.4 头结点
在单链表的开始结点之前设立一个节点称之为头结点(也称为哨兵节点或哑节点)，头结点的数据域可以不存储任何信息，也可以存储链表的长度等附加信息，头结点的指针域存储指向第一个结点(首元结点)的指针。
带头结点和不带头结点的区别
在带头结点的链表中，链表的第一个节点是一个特殊的节点，称为头节点，它不存储数据(或存储链表长度)，仅用于简化链表的操作。
引入头结点后的优点
- 插入操作：在插入新节点时，无论插入位置是链表头部、中间还是尾部，处理逻辑一致，无需特别处理第一个节点。
- 删除操作：在删除节点时，无论删除的是第一个节点还是其他节点，处理逻辑一致，无需特别处理第一个节点。
- 判空操作： 空链表和非空链表的处理逻辑一致，因为头节点始终存在。
带头和不带头结点的链表在遍历方面处理逻辑无大差别。
带头和不带头结点区别
根据上图显示：头结点处存储的链表长度3，也可以不存储任何信息
2.5 头指针
头指针是指链表中，指向第一个结点的指针。
头指针具有标识作用，所以常常会用头指针冠以链表的名字。所以你定义一个链表，那么链表的名字一般就是这个链表的头指针。
ListNode L = new ListNode(0); 左边的是指针和结点
无论链表是否为空，头指针均不为空，头指针是链表的必要元素。
2.6 首元结点
链表中第一个元素所在的结点，它是头结点后边的第一个结点。如果是带头结点的链表，则头结点后面的为首元结点。
元素是指链表中实际存储数据的结点，像头结点就不属于元素，因为它存储的不是数据，而是一些链表的属性信息(链表长度)或者为空。
2.7 总结以上概念
整理成一句话就是
- 头指针：指向第一个结点
- 头结点：在首元结点前面设立一个结点
- 首元结点：链表中第一个元素所在的结点
- 元素结点：存储链表实际信息的结点
2.8 本节注意事项
结构体定义：
typedef struct LNode {
Elemtype data;
struct LNode* next;
}LNode,*LinkList;
struct LNode是结构体标签，用于标识这个结构体类型Elemtype是数据域的类型，实际使用时需要替换为具体类型（如int、char等）next是指向下一个struct LNode节点的指针，通过它可以将多个节点连接成链表
类型别名定义
typedef struct LNode { ... } LNode, *LinkList;
LNode等价于struct LNode，可以直接使用LNode声明变量LinkList等价于struct LNode*，即指向链表节点的指针，通常用来表示整个链表
这种设计允许使用统一的类型系统操作链表：
LinkList强调链表整体，通常用于表示链表头指针LNode*强调节点操作，例如遍历链表时的当前节点指针
本网站原创文章版权归何大锤的狂飙日记所有。发布者：何大锤，转转请注明出处：何大锤的博客
