链表

_shining · 2024-05-18 15:21:00 · 算法·理论

链表：

链表，是一种线性数据结构。它的优势我们可以通过与数组的对比来看一下。

• 数组，优势在于可以随机访问，调用非常方便。但是劣势也非常明显：①删除和插入的操作中会涉及到大量数据的移动。②定义的空间必须是连续的，这就导致当需要一个较大空间的数组时，系统将面临无法分配处如此之大的连续空间的问题。
• 链表，是一种物理上分散，但逻辑上连续的数据结构。它可以将各个数据存入到内存中任意的空余空 间，哪怕这些空间是分散的。但在空间与空间之间建立一条隧道，即通过指针将空间串联起来，使得我 们可以有序访问。在逻辑上，它便是连续的。当我们需要插入和修改时，只需更改其指针的值即可。

一、单链表

🚀️准备操作：

1.定义：

struct node{
    int data;//存储数据 
    node *next;//存下一个数据点的地址 
};

2.申请空间：

p = new node;

3.释放空间：

delete p;

4.节点赋值：

p -> data = x;

🚀️基本操作：

子操作一：构建单链表

inline void create_list()//构建单链表 
{
    int n, x;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> x;
        p = new node;//申请新的空间
        p -> data = x;//将 x 封装成 node 节点
        //反向插入写法，从头部插入
        p -> next = head;//next 指向此时 head 所指向的地址
        head = p;//将 head 指向自己
    }
}

子操作二：输出单链表

inline void print_list()
{
    p = head;
    while(p != NULL){
        cout << p -> data << " ";
        p = p -> next;//让 p 跳到下一个节点 
    }
    cout << "\n";
}

子操作三：插入

inline void insert_list(int k, int x)//在第 k 个节点插入 x
{
    p = new node;
    p -> data = x;
    if(k == 1){//头部插入
        p -> next = head;//next 指向此时 head 指向的节点，即目前第一个节点
        head = p;//head 指向自己，称谓新的首节点
    }
    else{//非头部插入
        int i = 1;
        node *q = head;
        while(i < k - 1){//找到第 k-1 个节点
            q = q -> next;
            i++;
        }
        p -> next = q -> next;
        //q 为第 k-1 个节点，它的 next 指向此时第 k 个节点，将此值赋予 p 的 next 后，p 将成为新的第 k 个节点 
        q -> next = p;//第 k-1 个节点的 next 指向 p，即指向了新的第 k 个节点
    }
}

子操作四：删除

inline void delete_list(int k)
{
    if(k == 1){//头部删除 
        p = head;
        head = p -> next;
        delete p;
    }
    else{
        int i = 1; 
        p = head;
        while(i < k - 1){//p 为第 k - 1 个节点 
            p = p -> next;
            i++;
        }
        node *q = p -> next;//q 为待删除的第 k 个节点 
        p -> next = q -> next;//p 指向第 k + 1 节点 
        delete q;
    }   
}

In a word

#include <bits/stdc++.h>
using namespace std;
struct node{
    int data;//存储数据 
    node *next;//存下一个数据点的地址 
};
node *p, *head = NULL;
inline void create_list()//构建单链表 
{
    int n, x;
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> x;
        p = new node;//申请新的空间
        p -> data = x;//将 x 封装成 node 节点
        //反向插入写法，从头部插入
        p -> next = head;//next 指向此时 head 所指向的地址
        head = p;//将 head 指向自己
    }
}
inline void print_list()
{
    p = head;
    while(p != NULL){
        cout << p -> data << " ";
        p = p -> next;//让 p 跳到下一个节点 
    }
    cout << "\n";
} 
inline void insert_list(int k, int x)//在第 k 个节点插入 x
{
    p = new node;
    p -> data = x;
    if(k == 1){//头部插入
        p -> next = head;//next 指向此时 head 指向的节点，即目前第一个节点
        head = p;//head 指向自己，称谓新的首节点
    }
    else{//非头部插入
        int i = 1;
        node *q = head;
        while(i < k - 1){//找到第 k-1 个节点
            q = q -> next;
            i++;
        }
        p -> next = q -> next;
        //q 为第 k-1 个节点，它的 next 指向此时第 k 个节点，将此值赋予 p 的 next 后，p 将成为新的第 k 个节点 
        q -> next = p;;//第 k-1 个节点的 next 指向 p，即指向了新的第 k 个节点
    }
} 
inline void delete_list(int k)
{
    if(k == 1){//头部删除 
        p = head;
        head = p -> next;
        delete p;
    }
    else{
        int i = 1; 
        p = head;
        while(i < k - 1){//p 为第 k - 1 个节点 
            p = p -> next;
            i++;
        }
        node *q = p -> next;//q 为待删除的第 k 个节点 
        p -> next = q -> next;//p 指向第 k + 1 节点 
        delete q;
    }   
}
int main()
{

    return 0;
}

二、forward_list标准库

STL中的List是一种单向链表，可高效进行插入和删除。 使用前必须调用forward_list头文件

准备操作：

• 头文件：

#include <forward_list>

• 定义：

forward_list<数据类型> lst;

• 函数：

具体操作与 list 一样，不多赘述，重点看 list

三、List标准库

STL中的List是一种双向链表，可高效进行插入和删除。 使用前必须调用list头文件

准备操作：

• 头文件：

#include <list>

• 定义：

list<数据类型> lst;

• 函数：

• 重点：

其中需要注意的是，虽然这部分函数的时间复杂度为 O(1)，但是插入和删除函数使用前需要先查找到待处理的位置 p，这个准备工作所需时间接近 O(n)。