【数据结构】链表：插入、删除

我是通过b站的教程(如下图)学习的，这里记录下学习笔记。数据结构简单导言(为什么会出现数据结构？在日常生活中，为了组织不同类型的数据，我们需要不同类型的结构，帮助我们更高效更方便的找到想要的数据。

爱写文章的汉堡包

3468人浏览 · 2023-07-01 20:04:14

爱写文章的汉堡包 · 2023-07-01 20:04:14 发布

我是通过b站的教程(如下图)学习的，这里记录下学习笔记。

数据结构简单导言(为什么会出现数据结构？)。在日常生活中，为了组织不同类型的数据，我们需要不同类型的结构，帮助我们更高效更方便的找到想要的数据。

链表引言

当我们有一堆相同类型的数据时，我们会想到把他们归为一个列表，在代码实现上，你可能会想到数组，因为在我们已有知识基础上，数组就是用来存放相同类型数据的一种数据结构，能够帮助我们实现把这些数据归为一个列表的操作，通过数组，我们可以给数据赋值，可以修改，也可以实现读取数据打印出来。

但是当我们想要更多功能，我们想这个列表的空间是动态的(因为我们知道数组在定义时是要规定数组所存储元素的个数的)，想对列表中的数据进行插入，删除等操作时，倘若用数组实现，那将会非常麻烦。

使用数组实现动态列表的弊端

1.插入和删除元素的时间复杂度较高

数组是一种线性数据结构，它在内存中是连续存储的。这意味着当我们想要在数组中插入一个元素时，我们需要将插入位置后面的所有元素都向后移动一位，以腾出空间。这个过程的时间复杂度为O(n)，其中n为数组的长度。【关于插入数据的时间复杂度这里说的可能不清晰，在后面会详细解释】

2.需要预先分配内存空间导致扩容不方便

如果我们数据比较多还想要增大这个列表的容量，通过数组我们怎么处理呢？数组在创建时会预先分配存储空间，也就是我们要提前确定数组的元素个数，数组一创建大小就已经固定了，而且该数组内存空间周围的空间也可能已经被计算机分配给其他变量了，所以我们只能在创建一个比当前数组内存更大的数组，将原来的数据复制到新的更大的数组中，这又是多么麻烦

3.浪费内存

由于数组需要预先分配内存空间，因此当数组中的元素数量远小于数组的容量时，会造成内存浪费。

由于以上原因，我们便想存在一种动态列表这样的数据结构来提高效率和内存利用率。链表这种数据结构就出现了(´▽`ʃ♡ƪ)。

链表的思想

我们想要单独的定义每一个所需要的数据，来实现内存的充分利用，同时这些数据还必须是一个列表，如何实现呢？(下图每个小格子代表4bit一个整型数据)

如图，我们每个变量都单独申请空间，这样就不会出现内存浪费啦。但这样我们得到的是在内存条上随机的地址，如何把这些散乱的地址串联起来呢？

在数组中，数据连续存储，我们通过数组的首元素地址和数据在数组中的位置，可以得到所有元素的地址。但在这里，我们可以通过将该地址紧随其后的那个地址指向列表中下一个数据的地址来实现该操作。这里我们发现所存储的数据和下一个元素的地址应该当作一个整体，要实现这一目的，在c/c++中我们可以定义一个结构体变量：包含两个元素，一个元素用来存储数据，一个元素用来存储下一个数据的地址。

注意最后一个节点的地址部分是NULL或0(空指针)，不指向任何节点。也是作为链表结束的标志。

链表和数组

1.查找元素

在链表中，我们唯一知道的信息就是头节点的地址，通过它来索引到链表中的所有元素。这意味着我们如果想要找链表中的某个元素，必须从头节点往后查找，这样也就说明链表查找某个元素的时间是不同的，其时间复杂度应该是O(n)，

这里的计算是：好的情况是要查找的元素就在第一个节点，那么时间复杂度是O(1)，最坏的情况是O(n)，访问到最后一个元素。平均下来就是O(n+1/2)，由于常数对整体影响不大，所以整体时间复杂度是O(n)

这一点是有别于数组的，数组查找某个元素的地址时间是相同的，时间复杂度都是O(1)。

2.所占内存

数组可能会出现，元素个数小于开辟的数组元素个数，导致开辟的内存没有被使用而被浪费的情况，也有可能元素个数超过数组开辟的元素个数，导致只能通过重新开辟一份更大的空间来存放数组元素的情况，然鹅仍然可能出现内存没有完全利用的可能。

而链表中开辟的内存没有浪费，始终是需要了才开辟。虽然链表的形式需要给每个数据多开辟一个存放地址的变量内存，但在有很多数据的时候，链表还是有很多优势的。

3.插入删除列表元素的成本

插入元素分为：在头节点，中间节点，末尾节点插入对应着不同的时间复杂度。

如果是数组的话，分别对应O(n)：每一个元素都要挪动。 O(n)。 O(1)。

如果是链表，分别对应O(1)。 O(n)。 O(n)。

链表插入数据

在链表中我们只能通过头节点来对链表进行操作，所以需要定义一个指针变量来表示链表头节点，使我们能够标识该链表。

最初链表中没有数据，头节点为NULL。向链表中存储数据的时候，需要创建一个节点，由于我们每次插入数据的时候都不知道列表中会有多少数据需要存储，所以在C语言中需要使用malloc函数，来动态分配内存空间。

malloc函数返回值类型为void*，这意味着它返回一个通用指针，在使用时我们可以通过类型转换为我们所需要的类型。

 struct Node* temp=(struct Node*)malloc(sizeof(struct Node));

接下来就是实现插入数据的过程了。

其实从任意节点插入就已经包含了从头节点插入的情况，但是有时候我们仍然会提供一个单独的函数来从头部插入数据。

这是因为从头部插入数据比从任意位置插入数据更简单，不需要遍历链表来找到插入位置。更容易理解和实现。如果我们经常需要从头部插入数据，那么提供一个单独的函数来执行此操作可能会提高性能。(关于插入数据函数书写的思路在代码注释中有说明)

下面是C语言代码实现从链表头部插入数据

//从头部插入节点
#include<stdio.h>
#include<stdlib.h>
struct Node{
    int data;
    struct Node* next;
};
struct Node* head;//定义为全局变量 (或者定义为局部变量，在代码实现上会存在差异)
//插入函数
void Insert(int x)
{
    struct Node* temp=(struct Node*)malloc(sizeof(struct Node));
    //malloc 的返回值为 void*，接收时必须强制类型转换
    (*temp).data = x;
    temp->next=head;
    //当链表为空的时候head自然是NULL，该语句仍然成立，所以可以不分链表是否为空情况 写一个语句即可
    head = temp;
}
//打印链表
void Print()
{
    struct Node* temp = head;
    printf("link is: ");
    while(temp != NULL)//遍历链表
    {
        printf("%d ",temp->data);
        temp = temp->next;
    }
    printf("\n");
}
int main()
{
    head = NULL;//链表起始是空的
    printf("How many numbers?\n");
    int n,i,x;//n表示数据个数，用来作为循环结束的条件，x表示每次插入的数据
    scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        printf("Enter the numbers:\n");
        scanf("%d",&x);
        Insert(x);//从头结点处插入一个数
        Print();
    }
    return 0;
}

下面是用c++实现从链表中任意位置插入数据

// 在任意位置插入节点 区别于直接从头部插入数据的情况主要是需要寻找所需要的节点
#include <iostream>
using namespace std;
struct Node
{
    int data;
    Node *next;
};
struct Node *head;
void Insert(int data, int n) // 要在第n个节点处插入数据，那么要找到第n-1个节点
// 但是当链表为空的时候，意味着我们无法在链表中找到要插入位置的前一个节点。所以得到思路分两种情况
{
    Node *temp1 = new Node();
    temp1->data = data;
    temp1->next = NULL;
    if (n == 1)
    {
        temp1->next = head;
        head = temp1;
        return;
    }
    Node *temp2 = head;
    for (int i = 0; i < n - 2; i++) // 找到第n-1个节点
    {
        temp2 = temp2->next;
    }
    temp1->next = temp2->next;
    temp2->next = temp1;
}
void Print()
{
    Node *temp = head;
    while (temp != NULL)
    {
        printf("%d ", temp->data);
        temp = temp->next;
    }
}
int main()
{
    head = NULL; // 最初链表为空
    Insert(1, 1);
    Insert(2, 2);
    Insert(3, 1);
    Insert(4, 2);
    Print();
    return 0;
}

链表删除数据

想要删除数据，就是在前面插入完数据的基础上再写一个函数执行删除操作。

如何删除呢？首先思路还是要找到想删除的元素的前一个元素，因为前一个元素中还存着它的地址呢，我们要通过修改它所指向的地址来实现删除该元素。

由于当x=1时，表示的是删除第一个元素，此时就不需要找它的前一个元素，所以函数在实现时要想到分两种情况。

首先需要创建临时变量，让它指向头节点，这样我们不会丢失头节点的地址，当x=1时，直接修改临时变量头节点的地址指向，再释放该临时变量来实现删除。

当所要删除的元素不是头节点，此时我们就需要通过for循环来找到第x-1个节点，由于这时修改涉及到x-1,x,x+1这三个节点的变化，我们需要再创建一个临时变量，来实现地址指向的修改，达到删除元素的目的

下面是C语言代码实现删除节点

#include<stdio.h>
#include<stdlib.h>
struct Node{
    int data;
    struct Node* next;
};
struct Node* head;
void Insert(int x)
{
    struct Node* temp=(struct Node*)malloc(sizeof(struct Node));//创建节点
    (*temp).data=x;
    temp->next= head ;
    head = temp;
}
void Print()
{
    struct Node* temp=head;
    while(temp != NULL)
    {
        printf("%d ",temp->data);
        temp = temp->next;
    }
    printf("\n");
}
void Delete(int x)
{
    struct Node* temp1= head;
    if(x==1)
    {
        head = temp1->next;
        free(temp1);
        return;
    }
    int i;
    for(int i =0;i<x-2;i++)
    {
        temp1 = temp1->next;
    }//现在找到的是目标位置的前一个位置 即此时temp1表示的是要删除元素的前一个元素
    struct Node* temp2=temp1->next;//现在temp2表示的是要删除的这个元素
    temp1->next= temp2->next;//让n-1的地址指向n+1的位置
    free(temp2);
}
int main()
{
    head = NULL;
    //由于链表初始为空，也就是从头部插入数据
    Insert(2);
    Insert(3);
    Insert(8);
    Insert(6);
    Insert(4);
    Print();
    int n;//n表示想要删除的元素的位置
    scanf("%d",&n);
    Delete(n);
    Print();
    return 0;
}

好啦，这次先说到这里。

由于本人还是小白，仅靠网课资源学习记录笔记，如果有哪里出现错误的说法欢迎指出，非常感谢。

也欢迎交流建议奥。