typora-root-url: ./

1. 单链表的基本概念

1.1 定义

单链表：结点只有一个指针域的链表，称为单链表或线性链表。

单链表是由表头唯一确定，因此单链表可以用头指针的名字来命名若头指针名是L，则把链表称为表L

单链表的存储结构如下：

image-20220831153232802

1.2 表示

typedef struct Lnode{ //声明结点的类型和指向结点的指针类型
    ElemType data;      //结点的数据域
    struct Lnode *next;    //结点的指针域
}Lnode,*LinkList;    //LinkList为指向结构体Lnode的指针类型

定义链表L：LinkList L;

定义结点指针 p：LNode *p; 等价于 LinkList p;

例如，存储学生学号、姓名、成绩的单链表结点类型定义如下：

typedef struct student{
    char num[8];    // 数据域
    char name[8];    // 数据域
    int score;        // 数据域
    struct student *next;    // 指针域
}Lnode,*LinkList;

定义链表L：LinkList L;

为了统一链表的操作，通常这样定义：

typedef struct{
    char num[8];    // 数据域
    char name[8];    // 数据域
    int score;        // 数据域
}ElemType;
typedef struct Lnode{
    ElemType data;    // 数据域
    struct Lnode *next;    // 指针域
}Lnode,*LinkList;

2. 单链表基本操作的实现

2.1 初始化链表

（带头结点的单链表）：即构造一个空表。

【算法步骤】

（1）生成新结点作头结点，用头指针L指向头结点。
（2）将头结点的指针域置空。

【算法描述】

typedef struct Lnode{ //声明结点的类型和指向结点的指针类型
    ElemType data;      //结点的数据域
    struct Lnode *next;    //结点的指针域
}Lnode,*LinkList;    //LinkList为指向结构体Lnode的指针类型

Status InitList_L(LinkList &L){
    L = new LNode;// 或： L= (LinkList)malloc(sizeof(LNode));
    L->next = NULL;
    return OK;
}

2.2 判断链表是否为空

空表：链表中无元素，称为空链表（头指针和头结点仍然在)

【算法思路】：判断头结点指针域是否为空

int ListEmpty(LinkList L){    // 若L为空表，则返回1，否则返回0
    if(L->next)
        return 0;
    else
        return 1;
}

2.3 销毁链表

【算法分析】：从头指针开始，依次释放所有结点

① 首先定义一个指针变量 p 用来存放结点的地址，由于 L 本身就是指向头指针的指针变量，因此可将其赋给 指针变量 p，这样两者都指向了头指针。

bbe431e91fb520f14993805cc211e73

② 将 L向后移，即让 L 来存储下一个结点的地址，即指向首元结点 $a_1$；而首元结点 $a_1$ 的地址存储在头结点中的指针域，即 L->next；

2e2240b322ee119691666429e6ffd0c

这样我们就可以删除指针 p 所指向的结点（头结点）了；

③ 同样地，重复①②的操作，令 p 指向首元结点 $a_1$，然后指针变量 $L$ 指向结点 $a_2$，即L=L->next，然后删除指针 p指向的结点......

image-20220831155703993

直至最后，L和p 同时指向最后一个结点 $a_n$，此时后面无结点，则 L->next = NULL ，至此循环终止，删除指针 p；

Status DestroyList_L(LinkList &L){    // 销毁单链表L
    Lnode *p;    //或 LinkList p;
    while(L){
        p = L;
        L = L->next;
        delete p;
    }
}

2.4 清空链表

链表仍存在，但链表中无元素，成为空链表（头指针和头结点仍然在）

【算法分析】依次释放所有结点，并将头结点指针域设置为空

① 首先定义一个指针变量 p 指向首元结点 $a_1$，即 p = L->next，因为指针变量 L 指向的头结点的指针域存储的地址就是首元结点的地址。

image-20220831161216067

② 然后定义指针变量 q，令q 指向下一结点 $a_2$，即 q = p->next，这样我们就可以放心的删除指针 p，而又不会丢失寻找下一结点的地址；

image-20220831161911010

③ 然后就是类似于销毁链表的部分，重新将 q 赋值给p，即 p = q，此时指针变量 p 和 q 都指向结点 $a_2$，其次再将 q 后移指向下一节点 $a_3$，即 q = q->next，最后放心删除指针 p。

image-20220831163023024

当删除到最后一个结点的时候，q 指向最后一个结点，赋值给 p ，则p == NULL 此时跳出循环，因此循环条件是 p != NULL；

④ 最后将头结点的指针域设置为空：L->next = NULL

【算法实现】

Status ClearList(LinkList &L){    // 将L重置为空表
    Lnode *p,*q;    // 或者 LinkList p,q;
    p = L->next;
    while(p){        // 没到表尾
        q = p->next;
        delete p;
        p = q;
    }
    L->next = NULL;    //头结点指针域设为空
    return OK;
}

2.5 求单链表的表长

【算法思路】从首元结点开始，依次计数所有结点

首先定义一个指针变量 p，让其指向头结点，即 p = L->next，此时令整型变量为 i=1，然后循环令 p = p->next指向下一结点，每移动依一次，计数加一；直至p = p->next = NULL，则停止计数；

image-20220831174943159

如果是空表，则p = L->next = NULL，此时i = 0;

【算法实现】

int ListLength_L(LinkList L){ // 返回L中元素的个数
    LinkList p;
    p = L->next;    //p指向第一个结点
    i = 0;
    while(p){        //遍历单链表，统计结点数
        i++;
        p = p->next;
    }
    return i;
}

2.6 取值

取单链表中第 i 个元素的内容

从链表的头指针出发，顺着链域 next 逐个结点往下搜索，直至搜索到第 i 个结点为止。因此，链表不是随机存取结构

【算法分析】

① 从第1个结点（L->next）顺链扫描，用指针 p 指向当前扫描到的结点，p 初值 p = L->next 。(查找 i=3 的值)

② j做计数器，累计当前扫描过的结点数，j 初值为1

image-20220901145511260

③ 当 p 指向扫描到的下一结点时，计数器 j 加1

image-20220901145532443

④ 当 j==i 时，p 所指的结点就是要找的第 i个结点。

image-20220901145609226

【算法实现】

// 获取线性表L中的某个数据元素的内容,通过变量e返回
Status GetElem_L(LinkList L,int i,ElemType &e){
    LinkList p; int j;
    p = L->next; j = 1;    // 初始化
    while(p && j < i){    // 向后扫描，直到p指向第i个元素或p为空
        p = p->next; ++j;
    }
    if(!p || j>i) return ERROR; // 第i个元素不存在
    e = p->data;    // 取出第i个元素
    return OK;
}

2.7 查找

【算法分析】

比如查找值为30的元素:

① 从第一个结点起，依次和 带查找的值e相比较。

image-20220901151318433

② 如果找到一个其值与e 相等的数据元素，则返回其在链表中的 “位置” 或地址；

image-20220901151354469

③ 如果查遍整个链表都没有找到其值和e相等的元素，则返回0或

【算法实现】 (返回e 的数据元素的地址)

Lnode *LocateElem_L(LinkList L, Elemtype e){
    // 在线性表L中查找值为e的数据元素
    // 找到，则返回L中值为e的数据元素的地址，查找失败返回NULL
    LinkList p;
    p = L->next;
    while(p && p->data != e){
        p = p->next;
    }
    return p;
}

【算法实现】 (返回e 的数据元素的位置序号)

// 在线性表L中查找值为e的数据元素的位置序号
int LocateElem_L(Linklist L,Elemtype e){
    LinkList p; int i;
    p = L->next; i = 1;
    // 返回L中值为e的数据元素的位置序号，查找失败返回0
    while(p && p->data != e){ 
        p = p->next; i++;
    }
    if(p) return i;
    else return 0;
}

单链表查找的算法复杂度：$O(n)$

因线性链表只能顺序存取，即在查找时要从头指针找起，查找的时间复杂度为$O(n)$。

2.8 插入

插入——在第 i 个结点前插入值为 e 的新结点

【算法分析】

如图所示，在第 i = 3 个结点前插入值为 e 的新结点

image-20220901153018874

① 首先找到 $a_{i-1}$ 的存储位置 p。

image-20220901155702939

② 生成一个数据域为 e 的新结点 s。

③ 插入新结点：新结点的指针域指向结点 $a_i$；结点 $a_{i-1}$ 的指针域指向新结点

image-20220901155636022

【算法实现】

// 在L中第i个元素之前插入数据元素e
Status ListInsert_L(LinkList &L,Elemtype e,int i){
    LinkList p; p = L->next; int j = 1;
    while(p && j < i-1){ //寻找第i-1个结点，p指向i-1结点
        p = p->next; ++j;}
    // i大于表长+1或者小于1，插入位置非法
    if(!p || j > i-1) return ERROR;
    s = new LNode; s->data = e; // 生成新结点s，将结点s的数据域置为e
    s->next    = p->next;    // 将结点s插入
    p->next = s;   
    return OK;
}

2.9 删除

【算法分析】

如图所示，删除 第i = 3 个结点：

image-20220901161526530

① 首先找到 $a_{i-1}$ 的存储位置 p，保存要删除的 $a_i$ 的值

image-20220901163110900

② 令 p-> next 指向 $a_{i+1}$

image-20220901164402616

【算法实现】

//将线性表L中第i个数据元素删除
Status ListDelete_L(Linklist &L,int i,Elemtype &e){
    Linklist p,q; p = L->next; int j = 1;
    while(p && j < i-1){ //寻找第i-1个结点，p指向i-1结点
        p = p->next;  ++j;}
    if(!p || j > i-1) return ERROR;// 删除位置非法
    q = p->next;  // 临时保存被删结点的地址以备释放
    p->next = q->next; // 改变删除结点前驱结点的指针域
    e = q->data;    // 保存删除结点的数据域
    delete q;        // 释放删除结点的空间
    return OK;
}

单链表插入和删除的算法复杂度：$O(1)$

因线性链表不需要移动元素，只要修改指针，一般情况下时间复杂度为$O(1)$。但是，如果要在单链表中进行前插或删除操作，由于要从头查找前驱结点，所耗时间复杂度为$O(1)$。

3. 单链表的建立

3.1 头插法

头插法：元素插入在链表头部，也叫前插法。

① 从一个空表开始，重复读入数据；

image-20220901172918421

② 生成新结点，将读入数据存放到新结点的数据域中

③ 从最后一个结点开始，依次将各结点插入到链表的前端

image-20220901173500721

image-20220901174647836

依次循环即可......

例如：建立链表 L（a,b,c,d,e）image-20220901171137194

【算法实现】

void CreateList_H(Linklist &L,int n){
    // 先建立一个带头结点的单链表
    L = new LNode;
    L->next = NULL;
    for(i=n; i>0; --i){
        p = new Lnode; // 生成新节点
        cin >> p->data;    // 输入元素值
        p->next = L->next;    //插入到表头
        L->next = p;
    }
}
头插法算法的时间复杂度为 $O(n)$

3.2 尾插法

尾插法：元素插入在链表尾部，也叫后插法

① 从一个空表 L 开始，初始时，r 同L 均指向头结点。

image-20220902092101786

② 将新结点赋值后，逐个插入到链表的尾部

image-20220902092431951

③ 尾指针 r 指向链表的尾结点。

image-20220902092446723

④ 每读入一个数据元素则申请一个新结点，将新结点插入到尾结点后，r 指向新结点。

image-20220902092543411

【算法实现】

// 正位序输入n个元素的值，建立带表头结点的单链表
void CreatList_R(Linklist &L, int n){
    L = new LNode; L->next = NULL;
    r = L;
    for(int i = 0,i < n;++i){
        p = new LNode; cin >> p->data;
        p->next = NULL;
        r->next = p;
        r = p;  
    }
}
尾插法算法的时间复杂度为 $O(n)$
🧐 本文作者：
 😉 本文链接：https://lukeyalvin.site/archives/89.html
 😊 版权说明：本博客所有文章除特别声明外，均默认采用 CC BY-NC-SA 4.0 许可协议。
最后修改：2022 年 09 月 24 日
© 允许规范转载
赏杯咖啡