链表

前言

在实际运用中，我们常常会对数据进行插入或删除操作而很少的对数据进行查询。如果我们使用数组来储存数据，插入或删除一个元素的时间复杂度为$O(n)$，显然不能满足我们高频查询的时间需求。为了更好的解决问题，我们引入一种新的数据结构——链表

基本概念和常用操作的时间复杂度

链表是一种物理存储结构上非连续、非顺序的链式储存结构，元素与元素之间使用指针进行连接，从而实现逻辑顺序。

插入	查找	删除
$O(1)$	$O(n)$	$O(1)$

单链表

graph LR
    节点1---后置指针1--> 节点2
    节点1---数据1
    节点2---后置指针2--> 节点3
    节点2---数据2
    节点3---后置指针3--> 节点4
    节点3---数据3
    节点4---后置指针4--> 空
    节点4---数据4

单链表的构造

链表由节点连接而成的，而每个节点有两个（或多个）子成员，如数据和后置指针（等）。

想要构造一个链表，我们就得先设计出我们的节点。如

struct 节点 {
    数据的具体类型 数据;
    struct 节点 *后置指针;
};

这个节点类型包含了一个数据和一个节点类型的后置指针，随后我们将使用其来构造一个链表。

一般来说，单链表是可变长度的，为了在实现长度可变的同时提高空间的利用率，我们需要动态的给链表分配内存，这也是为什么这里的后置指针采用指针类型的原因。

在C语言中，我们可以使用以下语句来分配一个内存空间

节点 *链表节点 = (节点*)malloc(sizeof(节点));    //需要#include<stdlib.h>

而在C++中，我们可以使用new关键字来申请内存

节点 *链表节点 = new 节点;

注意！！！分配完的空间在使用结束后一定要记得释放，不然会造成内存泄漏

释放申请的内存空间的方法

//C语言 需要#include<stdlib.h>
free(链表节点);
//C++ delete关键字
delete 链表节点;

• 使用C++的同学还能使用memory库中的智能指针来简化内存释放操作

插入数据

如在节点1后插入节点N，则流程如下：先让节点N的后置指针指向节点2，随后让节点1的后置指针指向节点N

graph LR
    节点1---后置指针1--> 节点2
    节点1---数据1
    节点N---后置指针N
    节点N---数据N
    节点2---后置指针2--> 节点3
    节点2---数据2
    节点3---后置指针3--> 节点4
    节点3---数据3
    节点4---后置指针4--> 空
    节点4---数据4

graph LR
    节点1---后置指针1--> 节点2
    节点1---数据1
    节点N---后置指针N-->节点2
    节点N---数据N
    节点2---后置指针2--> 节点3
    节点2---数据2
    节点3---后置指针3--> 节点4
    节点3---数据3
    节点4---后置指针4--> 空
    节点4---数据4

graph LR
    节点1---后置指针1--> 节点N
    节点1---数据1
    节点N---后置指针N-->节点2
    节点N---数据N
    节点2---后置指针2--> 节点3
    节点2---数据2
    节点3---后置指针3--> 节点4
    节点3---数据3
    节点4---后置指针4--> 空
    节点4---数据4

具体实现如下

//用于插入节点（向后插入）
void insertNode(struct node* pos) {
    //新建一个节点
    node *tmp = (node *)malloc(sizeof(node));
    scanf("%d", &tmp->data);
    //新节点的后置指针指向pos的后一个节点
    tmp->next = pos->next;
    //pos的后置指针指向新节点
    pos->next = tmp;
}

查找数据

如查找数据3，则流程如下：从链表头开始，以此比较节点中的数据和要查找的数据，若找到数据，返回其位置

注：图中使用圆框表示正在访问的节点

graph LR
    A((节点1))---后置指针1--> 节点2
    A((节点1))---数据1
    节点2---后置指针2--> 节点3
    节点2---数据2
    节点3---后置指针3--> 节点4
    节点3---数据3
    节点4---后置指针4--> 空
    节点4---数据4

graph LR
    节点1---后置指针1--> A((节点2))
    节点1---数据1
    A((节点2))---后置指针2--> 节点3
    A((节点2))---数据2
    节点3---后置指针3--> 节点4
    节点3---数据3
    节点4---后置指针4--> 空
    节点4---数据4

graph LR
    节点1---后置指针1--> 节点2
    节点1---数据1
    节点2---后置指针2--> A((节点3))
    节点2---数据2
    A((节点3))---后置指针3--> 节点4
    A((节点3))---数据3
    节点4---后置指针4--> 空
    节点4---数据4

具体实现如下

//在链表中查找数据为data的元素的节点，返回指向该节点的指针
struct node* findNode(struct node* head, int data) {
    struct node* tmp = head;
    //循环遍历链表
    while(tmp != NULL) {
        //找到数据，退出循环
        if(tmp->data == data)
            break;
        tmp = tmp->next;
    }
    //返回指向该节点的指针
    return tmp;
}

删除数据

如删除节点2，则流程如下：先让临时指针指向节点3，随后清除节点2，最后让节点1的后置指针指向临时指针所指向的节点。

graph LR
    节点1---后置指针1--> 节点2
    节点1---数据1
    临时指针-->节点3
    节点2---后置指针2--> 节点3
    节点2---数据2
    节点3---后置指针3--> 节点4
    节点3---数据3
    节点4---后置指针4--> 空
    节点4---数据4

graph LR
    节点1---后置指针1
    节点1---数据1
    临时指针-->节点3
    节点2---后置指针2
    节点2---数据2
    节点3---后置指针3--> 节点4
    节点3---数据3
    节点4---后置指针4--> 空
    节点4---数据4

graph LR
    节点1---后置指针1 -->节点3
    节点1---数据1
    临时指针-->节点3
    节点3---后置指针3--> 节点4
    节点3---数据3
    节点4---后置指针4--> 空
    节点4---数据4

graph LR
    节点1---后置指针1 -->节点3
    节点1---数据1
    节点3---后置指针3--> 节点4
    节点3---数据3
    节点4---后置指针4--> 空
    节点4---数据4

具体实现如下（由于集成了查找元素位置，所以这个实现的时间复杂度应该是$O(n)$）

//用于删除节点
void removeNode(struct node* head, int data) {
    struct node* tmp = head;
    if(tmp == NULL) return;
    //循环遍历链表，找到待删除节点的前置节点
    while(tmp->next != NULL) {
        //找到数据，退出循环
        if(tmp->next->data == data)
            break;
        tmp = tmp->next;
    }
    //临时指针指向待删除节点的后置节点
    struct node* p = tmp->next->next;
    //清除待删除节点
    free(tmp->next);
    //将 已删除节点的前置节点的后置指针 指向 已删除节点的后置节点
    tmp->next = p;
}

完整代码

//C语言实现
#include <stdlib.h>
#include <stdio.h>
//节点类型
struct node {
    struct node *next;
    int data;
};
//构建长度为len的链表
struct node* buildList(int len) {
    //若长度为0，返回空
    if(len == 0) return NULL;
    //动态分配空间给头节点
    node *head = (node *)malloc(sizeof(node));
    //临时指针，用于实时变化链表尾节点位置
    node *tmp = head;
    //循环len-1次，避免多申请一次空间
    while (--len) {
        //用户输入数据
        scanf("%d", &tmp->data);
        //动态分配空间给下一个节点
        tmp->next = (node *)malloc(sizeof(node));
        //临时指针更新为尾节点
        tmp = tmp->next;
    }
    //处理尾节点的输入
    scanf("%d", &tmp->data);
    //设置链表尾节点的下一个节点为空
    tmp->next = NULL;
    //返回表头
    return head;
}
//用于插入节点（向后插入）
void insertNode(struct node* pos) {
    //新建一个节点
    node *tmp = (node *)malloc(sizeof(node));
    scanf("%d", &tmp->data);
    //新节点的后置指针指向pos的后一个节点
    tmp->next = pos->next;
    //pos的后置指针指向新节点
    pos->next = tmp;
}
//在链表中查找数据为data的元素的节点，返回指向该节点的指针
struct node* findNode(struct node* head, int data) {
    struct node* tmp = head;
    //循环遍历链表
    while(tmp != NULL) {
        //找到数据，退出循环
        if(tmp->data == data)
            break;
        tmp = tmp->next;
    }
    //返回指向该节点的指针
    return tmp;
}
//用于删除节点
void removeNode(struct node* head, int data) {
    struct node* tmp = head;
    if(tmp == NULL) return;
    //循环遍历链表，找到待删除节点的前置节点
    while(tmp->next != NULL) {
        //找到数据，退出循环
        if(tmp->next->data == data)
            break;
        tmp = tmp->next;
    }
    //临时指针指向待删除节点的后置节点
    struct node* p = tmp->next->next;
    //清除待删除节点
    free(tmp->next);
    //将 已删除节点的前置节点的后置指针 指向 已删除节点的后置节点
    tmp->next = p;
}
//用于打印链表
void print(struct node* head) {
    struct node* tmp = head;
    while(tmp != NULL) {
        printf("%d ", tmp->data);
        tmp = tmp->next;
    }
    putchar('\n');
}
//链表的内存释放
void freeList(struct node* head) {
    struct node* tmp = head;
    while(tmp != NULL) {
        struct node* p = tmp;
        tmp = tmp->next;
        free(p);
    }
}
int main() {
    int len;
    scanf("%d", &len);
    //构建链表
    struct node* list = buildList(len);
    //打印链表
    print(list);
    //查找元素
    struct node* pos = findNode(list, 5);
    //若能找到元素，则插入到元素后面，找不到则不修改
    if(pos != NULL) 
        insertNode(pos);
    //打印链表
    print(list);
    removeNode(list, 10);
    //打印链表
    print(list);
    //清除内存
    freeList(list);
    return 0;
}

双向链表

偷个懒，这个就不细说了

双向链表和单链表的区别只有一个。在单链表中，我们只有一个后置指针指向后置节点，而没有指针指向前置节点。也就是说，单链表只能沿着一个方向访问节点，是一个“单行道”。而双向链表多出了一个前置指针，让我们可以访问前置节点，这样就可以双向访问链表了

关于节点的设计和单向链表也类似，但多出了前置节点

struct 节点 {
    数据的具体类型 数据;
    struct 节点 *前置指针, *后置指针;
};

在插入和查找，删除中操作和单链表基本一致，不过需要同时修改前置指针的指向。如插入

//用于插入节点（向后插入）
void insertNode(struct node* pos) {
    //新建一个节点
    node *tmp = (node *)malloc(sizeof(node));
    scanf("%d", &tmp->data);
    //新节点的后置指针指向pos的后一个节点
    tmp->next = pos->next;
    //新增下行\/新节点的前置指针指向pos指针指向的节点
    tmp->prev = pos;
    //新增下行\/pos的后置节点的前置指针指向新节点
    pos->next->prev = tmp;
    //pos的后置指针指向新节点
    pos->next = tmp;
}

C++ STL list双向链表

在C++中有一种STL容器——std::list<T>

注意，在使用STL list的时候需要#include <list>

这是C++ STL官方实现的双向链表，那个T填入的是我们作为数据的数据类型

如std::list<int> myList

他不仅实现了上文提及的关于链表的功能，还内置了很多方法(函数)

方法名	功能
push_back(elem)	在链表尾部插入一个元素
push_front(elem)	在链表头部插入一个元素
pop_back()	在链表尾部删除一个元素
pop_front()	在链表头部删除一个元素
insert(pos,elem)	在pos位置插元素并返回新元素的位置
insert(pos,n,elem)	在pos位置插入n个elem元素
insert(pos,begin,end)	在pos位置插入$[begin,end)$区间的元素
erase(pos)	删除在pos位置的元素并返回下一个元素的位置
clear()	清空链表力的所有元素
remove(elem);	删除链表中和elem值相等的元素
size()	返回链表的长度
empty()	判断链表是否为空
resize(n)	修改链表的长度，若变长则用默认值填充多出元素，反之删除
resize(n, elem)	修改链表的长度，若变长则用elem填充多出元素，反之删除
assign(*beg, *end)	将$[begin,end)$区间中的数据赋值给本身（用迭代器）
assign(n, elem)	将n个elem元素赋值给本身
swap(otherList)	和另一个链表进行交换
front()	返回链表头的元素
back()	返回链表尾的元素
reverse()	倒转整个链表
sort()	对链表中的元素进行排序

#include<iostream>
#include<list>
using namespace std;
int main() {
    list<int> mylst;
    //[1,11)，也就是[1,10]
    for(int i = 1; i < 11; i++) {
        mylst.push_back(i);
    }
    mylst.reverse();
    //遍历循环，每次循环从容器中取出来一个数，并赋给i
    for(int i : mylst) {
        cout << i << ' ';
    }
    return 0;
}