数据结构与算法——线性表（链表篇）

🚀前言

上一文数据结构与算法——线性表（顺序表篇）中详细介绍了线性表的顺序存储结构的特点是逻辑关系上相邻的两个元素在物理位置上也相邻，因此可以随机存取表中的任一元素，它的存储位置可用一个简单直观的公式来表示。

但是，从另外一方面来看，线性表顺序存储的特点也构成了这种存储结构的特点：在做插入和删除操作时，需要移动大量元素。

本篇文章，我将详细介绍线性表的另外一种表示方式——链式存储结构。由于链式存储结构不要求逻辑上相邻的元素在物理位置上也相邻，因此它没有顺序存储结构所具有的弱点，但同时也失去了顺序表可随机存取的优势

---

🚀线性链表（单链表）

🚢概念

线性表的链式存储结构的特点是用一组任意的存储单元存储线性表的数据元素（这组存储单元可以是连续的，也可以是不连续的），因此，为了表示某个数据元素$ai$与它的直接后继元素$ai+1$之间的逻辑关系，对数据元素$ai$来说，除存储其本身的信息之外，还需要存储一个指示它直接后继的信息（即直接后继的存储位置），这两部分信息组成数据元素$ai$的存储映像，称为结点（node）。

它包括两个域：其中存储数据元素信息的域称为数据域，存储直接后继存储位置的域称为指针域，指针域中存储的信息称为指针或链，$n$个结点（$ai$(1<=i<=n)的存储映像）链结成一个链表，即为线性表的链式存储结构

由于链表的每个结点中只包含一个指针域，所以又称这种链表为线性链表或单链表，整个链表的存取必须从头指针开始进行，头指针指示链表中的第一个结点（即第一个数据元素的存储映像）的存储位置，同时，由于最后一个数据元素没有直接后继，则线性链表中最后一个结点的指针为空（NULL）

单链表的定义：

//方式一
typedef struct LNode{           //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素    
    struct LNode *next;         //指针指向下一个节点    
}LNode, *LinkList  


//方式二
struct LNode{                   //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素    
    struct LNode *next;         //指针指向下一个节点  
};
typedef struct LNode LNode;
typedef struct LNode *LinkList;
1
2
3
4
5
6
7
8
9
10
11
12
13
14

用线性链表表示线性表时，数据元素之间的逻辑关系是由结点中的指针指示的，换句话说，指针为数据元素之间的逻辑关系的映像，则逻辑上相邻的两个数据元素其存储的物理位置不要求紧邻，由此可得出，这种存储结构为非顺序映像或链式映像。

通常我们把链表画成用箭头相连接的结点的序列，结点之间的箭头表示链域中的指针，它所表是的线性表中数据元素之间的逻辑顺序，而不是每个数据元素在存储器中的实际位置

一般在一个单链表中，L表示为单链表的头指针，它指向表中的第一个结点，若L为‘空’（L=NULL），则所表示的线性表为‘空表’，其长度n为‘零’。

带头结点的单链表初始化：

typedef struct LNode{           //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素    
    struct LNode *next;         //指针指向下一个节点    
}LNode, *LinkList               

//初始化一个单链表(带头结点)
bool InitList(LinkList &L){
    L = (LNode *)malloc(sizeof(LNode));     //分配一个头结点
    if(L == NULL){          //内存不足，分配失败
        return false;
    }
    L->next = NULL;         //头结点之后暂时还没有结点
    return true;
}

void test(){
    LinkList L;     //声明一个指向单链表的指针
    //初始化一个空表
    InitList(L);
    .....
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

在单链表的第一个结点之前附设一个结点，称之为头结点。头结点的数据域可以不存储任何信息，也可以存储如线性表的长度等类的附加信息，头结点的指针域存储指向第一个结点的指针（即第一个元素结点的存储位置），单链表的头指针指向头结点。若线性表为空表，则头结点的指针域为‘空’。头结点的作用在于便于边缘化处理（好写程序），头结点也可以不写。

不带头结点的单链表初始化：

typedef struct LNode{           //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素    
    struct LNode *next;         //指针指向下一个节点    
}LNode, *LinkList               

//初始化一个空的单链表
bool InitList(LinkList &L){
    L = NULL;       //空表，暂时没有任何结点（防止脏数据）
    return true;
}

void test(){
    LinkList L;     //声明一个指向单链表的指针
    // 初始化空表
    InitList(L);
    ...
}

//判断单链表是否为空
bool Empty(LinkList L){
    if(L == NULL){
        return true;
    }else{
        return false;
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

在线性表的顺序存储结构中，由于逻辑上相邻的两个元素在物理位置上也相邻，则每个元素的存储位置都可以从线性表的起始位置计算得到，而在单链表中，任何两个元素的存储位置之间没有固定的联系，要想取得第$i$个数据元素必须从头指针出发寻找，因此，单链表是非随机存储结构。

单链表的局限性：无法逆向检索，有时候不方便

🚢基本操作

👻插入操作

⛅按位序插入

插入操作，在表L中的第$i$个位置上插入指定元素

想要在第i个位置上插入元素，那么就要找到第$i-1$个结点，然后将新结点插入其后面

带头结点情况：

typedef struct LNode{           //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素    
    struct LNode *next;         //指针指向下一个节点    
}LNode, *LinkList               

//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1){
        return false;
    }
    LNode *p;       //指针p指向当前扫描的结点
    int j=0;        //当前p指针的是第几个结点
    while (p != NULL && j<i-1){     //循环找到第i-1个结点
        p = p->next;
        j++;
    }
    if(p == NULL){  //i值不合法
        return false;
    }
    LNode *t = (LNode *)malloc(sizeof(LNode));
    t->data = e;
    t->next = p->next;
    p->next = t;        //将结点t连接到p之后
    return true;        //插入成功
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

不带头结点情况：

typedef struct LNode{           //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素    
    struct LNode *next;         //指针指向下一个节点    
}LNode, *LinkList               

//在第i个位置插入元素e(带头结点)
bool ListInsert(LinkList &L, int i, ElemType e){
    if(i<1){
        return false;
    }
    if(i==1){
        LNode *t = (LNode *)malloc(sizeof(LNode));
        t->data = e;
        t->next = L;
        L = t:      //头指针指向新结点
        return true;
    }
    LNode *p;       //指针p指向当前扫描的结点
    int j = 1;      //当前p指向的是第几个结点
    p = L;          //p指向第一个结点(注意：不是头结点)
    while(p != NULL && j<i-1){      //循环找到第i-1个结点
        p = p->next;
        j++;
    }
    if(p == NULL){      //i值不合法
        return false;
    }
    LNode *t = (LNode *)malloc(sizeof(LNode));
    t->data = e;
    t->next = p->next;
    p->next = t;
    return true;        //插入成功
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33

当i=1时，执行插入操作所需要的时间复杂度为$T(n)=O(1)$
当i>1 && i<=n时，时间复杂度为$T(n)=O(n)$

但是，值得注意的是，实际上插入这个操作真正时间复杂度为$T(n)=O(1)$，而程序运行所耗费的时间都在找到要插入的元素位置的前一个位置，所以综合考究:

📌平均时间复杂为$T(n)=O(n)$

⛅指定结点的后插操作

typedef struct LNode{           //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素    
    struct LNode *next;         //指针指向下一个节点    
}LNode, *LinkList               

//后插操作：在p结点之后插入元素e
bool InsertNextNode(LNode *p, ElemType e){
    if(p == NULL){
        return false;
    }
    LNode *t = (LNode *)malloc(sizeof(LNode));
    if(s==NULL){        //内存分配失败
        return false;
    }
    t->data = e;        //用结点t保存数据元素e
    t->next = p->next;
    p->next = t         //将结点t连接到p之后
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

📌平均时间复杂度为$T(o)=N(1)$

⛅指定节点的前插操作

typedef struct LNode{           //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素    
    struct LNode *next;         //指针指向下一个节点    
}LNode, *LinkList               

//后插操作：在p结点之前插入元素e
bool InsertNextNode(LNode *p, ElemType e){
    if(p == NULL){
        return false;
    }
    LNode *t = (LNode *)malloc(sizeof(LNode));
    if(s==NULL){        //内存分配失败
        return false;
    }
    t->next = p->next;
    p->next = t;            //新结点t连接到p之后
    t->data = p->data;      //将p中元素复制到t中
    p->data = e;            //p中元素覆盖为e
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

📌平均时间复杂度为$T(o)=n(1)$

👻删除操作

删除操作。删除表L中第$i$个位置的元素，并用$e$返回删除元素的值

⛅按位序删除

带头结点情况：

typedef struct LNode{           //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素    
    struct LNode *next;         //指针指向下一个节点    
}LNode, *LinkList               

//带头结点的删除操作
bool ListDelete(LinkList &L, int i, ElemType &e){
    if(i<1){
        return false;
    }
    LNode *p;       //指针p指向当前扫描到的结点
    int j=0;        //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点(不存数据)
    while(p != NULL && j<i-1){      //循环找到第i-1个结点
        p = P->next;
        j++;
    }
    if(p == NULL){      //i值不合法
        return false;
    }
    if(p->next == NULL){        //第i-1个结点之后已无其他结点
        return false;
    }
    LNode *q = P->next;         //令q指向被删除结点
    e = q->data;                //用e返回元素的值
    p->next = q->next;          //将*q结点从链中断开
    free(q);                    //释放结点的存储空间
    return true;                //删除成功
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29

📌在删除操作中，最坏和平均时间复杂度为$T(o)=o(n)$

最好时间复杂度:$T(n)=O(1)$

⛅指定节点的删除

typedef struct LNode{           //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素    
    struct LNode *next;         //指针指向下一个节点    
}LNode, *LinkList               

//删除指定结点p
bool DeleteNode(LNode *p){
    if(p == NULL){
        return false;
    }
    LNode *q = p->next;     //令q指向*p的后继结点
    p->data = p->next->data //和后继结点交换数据域
    p->next = q->next;      //将*q结点从链中断开
    free(q);                //释放后继结点的存储空间
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

但是，使用这个算法有个问题，如果p是最后一个结点，那么当程序执行到p->data = p->next->data这一句时，会出现空指针的错误，所以只能从表头开始依次寻找p的前驱

📌时间复杂度为$T(n)=O(n)$

👻查找操作（带头结点）

⛅按位查找操作

按位查找操作。获取表L中第i个位置的元素的值

typedef struct LNode{           //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素    
    struct LNode *next;         //指针指向下一个节点    
}LNode, *LinkList               

//按位查找，返回第i个元素(带头结点)
LNode * GetElem(LinkList L, int i){
    if(i<0){
        return NULL;
    }
    LNode *p;       //指针p指向当前扫描的结点
    int j = 0;      //当前p指向的是第几个结点
    p = L;          //L指向头结点，头结点是第0个结点(不存数据)
    while(p != NULL && j<i){        //循环找到第i个结点
        p = p->next;
        j++;
    }
    return p;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

📌平均时间复杂度为$T(n)=O(n)$

⛅按值查找操作

按值查找操作。根据给定的值在表L中查找与之相同的指定元素

typedef struct LNode{           //定义单链表节点类型
    ElemType data;              //每个节点存放一个数据元素    
    struct LNode *next;         //指针指向下一个节点    
}LNode, *LinkList               

//按值查找操作(带头结点)
LNode * LocateElem(LinkList L, ElemType e){
    LNode *p = L->next;
    // 从第1个结点开始查找数据域为e的结点
    while(p != NULL && p->data != e){
        p = p->next;
    }
    return p;       //找到后返回该结点指针，否则返回NULL
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

📌平均时间复杂度为$T(n)=O(n)$

👻单链表的创建

⛅尾插法

每次都在最后一个元素之后插入新的元素

LinkList List_Taillnsert(LinkList &L){      //正向建立单链表
    int x;      //设ElemType为整型
    L = (LinkList)malloc(sizeof(LNode));        //建立头结点，初始化空表
    LNode *s, *r = L;       //r为表尾指针
    scanf("%d", &x);        //输入结点的值
    while(x != 9999){       //输入9999表示结束
        s = (LNode *)malloc(sizeof(LNode));
        s->data = x;
        r->next = s;        //在r结点之后插入元素x
        r = s;              //r指向新的表尾结点,永远保持r指向最后一个结点
        scanf("%d", &x);
    }
    r->next = NULL;         //尾结点指针置空
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

📌平均时间复杂度为：$T(n)=O(n)$

⛅头插法

每次都在头结点之后插入新元素，头插法较为重要，当遇到链表的逆置操作时，可以使用头插法实现

LinkList List_Taillnsert(LinkList &L){      //逆向建立单链表
    LNode *s;
    int x;
    L = (LinkList)malloc(sizeof(LNode));        //创建头结点
    L->next = NULL;                             //初始为空链表
    scanf("%d", &x);                            //输入结点的值
    while(x != 9999){                           //输入9999标志结束
        s = (LNode*)malloc(sizeof(LNode));      //创建新结点
        s->data = x;
        s->next = L->next; 
        L->next = s;                    //将性结点插入表中，L为头指针
        scanf("%d", &x);
    }
    return L;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

📌平均时间复杂度为：$T(n)=O(n)$

🚢静态链表

这种存储结构需要预先分配一个比较大的空间，但在做线性表的插入和删除时不需要移动元素，仅需要修改指针，所以仍然具有链式存储结构的主要优点，为了和指针型描述的线性链表相区别，所以称这种用数组描述的链表为静态链表

静态链表的优点和缺点

• 📌优点：增、删操作不需要移动大量的数据
• 📌缺点：不能随机存取，只能从头结点开始依次往后查找，容量固定不可变，静态分配

🚢循环链表

循环链表（circular linked list）是另外一种形式的链式存储结构，它的特点是从表中最后一个结点的指针域指向头结点，整个链表形成一个环，由此，从表中任一结点触发均可找到表中的其他结点

循环链表的操作和线性表基本一致，差别仅在于算法中的循环条件不是P—>next是否为空，而是是否等于头指针

📌在循环单链表中，从头部找到尾部元素，时间复杂度为$T(n)=O(n)$

📌从尾部找到头部元素，时间复杂度为$T(n)=O(1)$

🚢双向链表

上述的链式存储结构的结点中只有一个指示直接后继的指针域，由此，从某结点出发只能顺指针往后查询其他结点，若要寻查结点的直接前驱，则需要从头指针出发。换句话说，在单链表中，NextElem的执行时间为$O(1)$，而PriorElem的执行时间为$O(n)$，为克服单链表这种单向性的缺点，可利用双向链表。

顾名思义，在双向链表的结点中有两个指针域，其一指向直接后继，其二指向直接前驱。和单链表的循环链表类似，双向链表也有循环链表。

双向链表不可随机存取，按位查找、按值查找操作只能用遍历的方式实现

📌时间复杂度为：$T(n)=O(n)$

👻双向链表的初始化（带头结点）

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *DLinklist;

bool InitDLinkList(DLinklist &L){
    L = (DNode *)malloc(sizeof(DNode));     //分配一个头结点
    if(L == NULL){                  //内存不足，分配失败
        return false;           
    }
    L->prior = NULL;        //头结点的prior永远指向NULL
    L->next = NULL;         //头结点之后暂时还没有结点
    return true;
}

void testDLinkList(){
    //初始化双链表
    InitDLinkList(L);
    ......
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

👻双向链表的插入操作

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *DLinklist;

// 在p结点之后插入s结点
bool InsertNextDNode(DNode *p, DNode *s){
    if(p == NULL || s == NULL){         //非法参数
        return false;
    }
    s->next = p->next;
    if(p->next != NULL){        //如果p结点有后继结点
        p->next->prior = s;
    }
    s->prior = p;
    p->next = s;
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

👻双向链表的删除操作

typedef struct DNode{
    ElemType data;
    struct DNode *prior, *next;
}DNode, *DLinklist;

// 删除p结点的后继结点
bool DeletenextDNode(DNode *p){
    if(p == NULL || s == NULL){         //非法参数
        return false;
    }
    DNode *p = p->next;     //找到p的后继结点q
    if(q == NULL){
        return false;       //p没有后继
    }
    if(q->next != NULL){    //q结点不是最后一个结点
        q->next->prior = p;
    }
    free(q);                //释放结点空间
    return true;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20

---

💻总结

以上就是线性表中链表的相关知识整理，配合代码是实例讲解链表的基本操作，相对于顺序表来说，链表的分类较为多一些，且操作也较为复杂一些，但只要认真看完本篇文章，你会对链表有更为详细的认知和理解，文章内容很多，知识点也很全面，一如既往希望我的文章能给各位小伙伴们带来帮助，数据结构与算法专栏也在持续更细中！！！

🎨觉得不错的话记得点赞收藏呀！！🎨

😀别忘了给我关注~~😀