引言：链表作为数据结构的一部分是在发现顺序表的不足上作了改进，在增与删中做了优化，本来要进行数据的移动最多O（n）的时间复杂度变成了O（1），接下来带大家来手撕链表。

链表的概念：https://v1meipiuniw.feishu.cn/docx/JqD6dw24VomqKDxoKCVcCuicnQd#share-AfuUd78Nto5JHOx2RVUcJ6ulnUh

一，前置操作：

1，头文件与定义数据类型：

#include<iostream>
#include<stdexcept>//抛出异常语句的头文件
using namespace std;
#define eletType int//定义通用的数据类型

2,创建一个链表结点结构体：

struct ListNode//链表节点结构体
{
    eletType data;//链表数据域
    ListNode* next;//链表指针域，next结点用next表示 为什么next 类型是ListNode？因为List指向同类型节点的指针。链表是一个链着一个的都是同类型的，不然数据的地址对不上会导致程序崩溃。

可以将链表想象成一列火车：

• ​ListNode* next​：就像每节车厢标准化的连接钩，专门用于连接另一节车厢。所有车厢类型相同，连接钩规格一致，火车可以安全连贯地运行。
• ​其他类型的 next​：就像车厢的连接钩被强行换成了一种无法匹配其他车厢的挂钩​（比如只能挂接卡车、集装箱或其他不相关的东西）。结果就是列车无法组装和运行，整个系统崩溃。

    ListNode(eletType x) :data(x), next(NULL) {};//构造结点函数并赋值，传入数据并把指针指向空
};如图所示：

3，创建一个实现单向链表的类：

class LinkedList//实现单向链表的类
{
private:
    ListNode* head;//储存头节点 返回结点的结构体这个类
    int size;//链表元素
public://先声明函数接口，然后在类外实现。声明的函数可以在类外直接
    LinkedList():head(NULL),size(0){}//初始化链表的构造函数并且把头结点指向空参考上图，程序运行时会自动调用
    ~LinkedList();//链表的析构函数，释放内存。程序结束运行时会自动调用
    void insert(int i, eletType value);//函数的声明
    void remove(int i);//移除元素 
    ListNode* find(eletType value);//返回找到listnode结点本身
    ListNode* get(int i);//返回索引的对应的listnode结点
    void update(int i, eletType value);//更新
    void print();//打印链表。
};

实现类内的函数：

1.0：链表析构函数：LinkedList::~LinkedList()

LinkedList::~LinkedList()
{
    ListNode* curr = head;//建立一个游标结点从head开始遍历。
    while (curr)
    {
        ListNode* tmp = curr;//LinkNode* tmp = curr; 这一步是必不可少的。它确保了：
        //​内存的正确释放​：能够准确无误地释放每一个节点。
            //​程序的稳定性​：避免了访问已释放内存而导致的程序崩溃
        curr = curr->next;//遍历的基础语法
        delete tmp;//此时tmp是游离的所以要删除节省空间
    }
}

2.0：链表插入函数：void LinkedList::insert(int i,  eletType value)

void LinkedList::insert(int i,  eletType value)//直接对链表进行操作，不需要返回值

    if (i<0 || i>size)
    {
        throw std::out_of_range("Invalid position");//抛出异常语句
    }

2.1创建新的结点：
  

 ListNode* newNode = new ListNode(value);//申请一个新的结点并把输入函数的值赋值给结点，

2.2分类插入

if (i == 0)//分类插入头结点的情况，因为头结点本指向空，现在要插入一个有数值的结点。
    {
        newNode->next = head;//先指向头结点
        head = newNode;//再把值赋值给头节点;
    }
    else{
        ListNode* curr = head;//建立游标结点,从head开始遍历
        for (int j = 0; j < i - 1; j++)
        {
            curr = curr->next;//插入位置的前一个位置 插入结点的前一个结点

        }
        ;//让新结点指向插入位置另外一个结点
        newNode->next=curr->next;
        curr->next = newNode;
        //再把新结点指向i   
        //画图解决

根据图来理解

    }
    ++size;//链表长度加一
}

3.0链表删除函数实现：void LinkedList::remove(int i)

图解：

先进行插入位置是否合法判断：

if (i<0 || i>=size)
{
    throw std::out_of_range("Invalid position");
}

3.1分类删除的情况：

if (i == 0)
{
    ListNode* temp = head;//把头结点储存在temp中
    head = head->next;//把头结点更新成头结点后一位
    delete temp;//删除初始的头结点
}

    else {
        ListNode* curr = head;//游标结点用于遍历
        for (int j = 0; j < i - 1; j++)
        {
            curr = curr->next;//找到第i-1个结点
        }
        ListNode* temp = curr->next;//指向第i个结点。
        curr->next = temp->next;指向i+1个结点
        delete temp;删除第i个结点
    }
    --size;//链表长度
}

4.0：链表查找函数：ListNode* LinkedList::find(eletType value)//返回值是结点

{
    ListNode* curr = head;//创建游标结点用来遍历链表
    while (curr && curr->data != value)//为空和找不到元素退出循环。
    {
        curr = curr->next;
    }
    return curr;//返回结点
}

5.0：链表结点值获取函数：ListNode* LinkedList::get(int i)

{
    if (i < 0 || i >= size)
    {
        throw std::out_of_range("Invalid position");//异常抛出
    }
    ListNode* curr = head;//游标结点
    for (int j = 0; j < i; ++j)
    {
        curr = curr->next;
    }
    return curr;//返回结点的值
}

6.0：链表对应下标区值函数：ListNode* LinkedList::get(int i)

{
    if (i < 0 || i >= size)
    {
        throw std::out_of_range("Invalid position");//异常抛出
    }
    ListNode* curr = head;//同上
    for (int j = 0; j < i; ++j)
    {
        curr = curr->next;
    }
    return curr;
}

7.0：链表更新函数：LinkedList::update(int i,eletType value)

{
    get(i)->data = value;//修改算法

}

8.0：链表打印函数：void LinkedList::print()

{
    ListNode* curr = head;
    while (curr)
    {
        cout << curr->data << " ";
        curr = curr->next;
     }
    cout << endl;

}

三：主函数调用部分：

现在函数部分已经实现，接下来就是在主函数中调用这些函数啦

int main()
{
    LinkedList list;//实例化链表构造函数
    for (int i = 0; i < 5; i++)
    {
        list.insert(i, i * 5);//插入5个元素
    }
    list.print();//打印元素
    list.remove(3);//移除第三个元素
    ListNode* temp = list.find(10);//创建临时结点接受元素
    cout<<temp->data<<endl;//打印找的的元素
    cout << list.find(20)->data << endl;
    list.print();//打印移除后剩下的元素
    cout << list.get(1)->data << endl;//打印取到位置的元素
    list.update(1, 9);//将第一个位置更新成九
    list.print();//打印操作过后的链表
    return 0;
}
运行效果图：

源码实例：

#include<iostream>
#include<stdexcept>
using namespace std;
#define eletType int
struct ListNode//链表节点结构体
{
    eletType data;//链表数据域
    ListNode* next;//链表指针域，next结点用next表示

    ListNode(eletType x) :data(x), next(NULL) {};//构造结点函数并赋值
};
class LinkedList//实现单向链表的类
{
private:
    ListNode* head;//储存头节点
    int size;//链表元素
public:
    LinkedList():head(NULL),size(0){}//链表的构造函数
    ~LinkedList();//链表的析构函数
    void insert(int i, eletType value);//函数的声明
    void remove(int i);//移除元素 
    ListNode* find(eletType value);//返回接结点本身
    ListNode* get(int i);//返回索引
    void update(int i, eletType value);//更新
    void print();
};
 

LinkedList::~LinkedList()
{
    ListNode* curr = head;
    while (curr)
    {
        ListNode* tmp = curr;//LinkNode* tmp = curr; 这一步是必不可少的。它确保了：
        //​内存的正确释放​：能够准确无误地释放每一个节点。
            //​程序的稳定性​：避免了访问已释放内存而导致的程序崩溃
        curr = curr->next;
        delete tmp;
    }
}
void LinkedList::insert(int i,  eletType value)//直接对链表进行操作，不需要返回值
{
    if (i<0 || i>size)
    {
        throw std::out_of_range("Invalid position");
    }
    ListNode* newNode = new ListNode(value);
    if (i == 0)
    {
        newNode->next = head;//先指向头结点
        head = newNode;//再把值赋值给头节点;
    }
    else{
        ListNode* curr = head;//建立游标结点,从head开始遍历
        for (int j = 0; j < i - 1; j++)
        {
            curr = curr->next;//插入位置的前一个位置 插入结点的前一个结点

        }
        ;//让新结点指向插入位置另外一个结点
         
        newNode->next=curr->next;
        curr->next = newNode;
        //再把新结点指向i
        //画图解决
    }
    ++size;
}
void LinkedList::remove(int i)
{
    if (i<0 || i>=size)
    {
        throw std::out_of_range("Invalid position");
    }
    if (i == 0)
    {
        ListNode* temp = head;
        head = head->next;
        delete temp;
    }
    else {
        ListNode* curr = head;
        for (int j = 0; j < i - 1; j++)
        {
            curr = curr->next;
        }
        ListNode* temp = curr->next;
        curr->next = temp->next;
        delete temp;
    }
    --size;
}
ListNode* LinkedList::find(eletType value)//返回值是结点
{
    ListNode* curr = head;
    while (curr && curr->data != value)
    {
        curr = curr->next;
    }
    return curr;
}
ListNode* LinkedList::get(int i)
{
    if (i < 0 || i >= size)
    {
        throw std::out_of_range("Invalid position");
    }
    ListNode* curr = head;
    for (int j = 0; j < i; ++j)
    {
        curr = curr->next;
    }
    return curr;
}
void LinkedList::update(int i,eletType value)
{
    get(i)->data = value;

}
void LinkedList::print()
{
    ListNode* curr = head;
    while (curr)
    {
        cout << curr->data << " ";
        curr = curr->next;
     }
    cout << endl;
}
int main()
{
    LinkedList list;//实例化链表构造函数
    for (int i = 0; i < 5; i++)
    {
        list.insert(i, i * 5);//插入5个元素
    }
    list.print();//打印元素
    list.remove(3);//移除第三个元素
    ListNode* temp = list.find(10);//创建临时结点接受元素
    cout<<temp->data<<endl;//打印找的的元素
    cout << list.find(20)->data << endl;
    list.print();//打印移除后剩下的元素
    cout << list.get(1)->data << endl;//打印取到位置的元素
    list.update(1, 9);//将第一个位置更新成九
    list.print();//打印操作过后的链表
    return 0;
}
 

结语：至此链表已经的增删改查已经手撕完毕了，以后还会慢慢更新其他数据结构，尽情期待。

有用的话点点收藏点点赞，谢谢大家！！！