C++ 链表

链表是以一个Node节点为单位，存储相关数据。

一、与数组对比区别：

数组
内存分配需要在一开始就确定
当插入与删除其中的数需要先将数字进行移动，再加入新的数字

链表
每个节点单独分配部分的内存
当进行修改时，修改对应节点的指针即可修改链表节点顺序
缺点是不支持直接读取，因此在单向链表的情况下越往后读取速度越慢

二、链表的使用

实例一：链表大致结构

class Node
{
Public:
    int Value; //存储的数据
    Node* Next; //指向下一节点的指针
public:
    Node(int value) //带参构造,初始化变量
    {
        Value = value; //初始化数据
        Next = nullptr; //初始化指向下一节点的指针
    }
};

实例二：双向链表
双向链表每个节点有两个指针，一个指向前一个节点，一个指向后一个节点
当单向对链表数据进行读取修改只能从开头顺序访问节点，效率低，因此可以加上从最后一位向前的反向节点，增加访问效率

class Node
{
Public:
    int Value; //存储的数据
    Node* Next; //从头开始的指向下一节点的指针
    Node* Pre; //从尾开始的指向上一节点的指针
public:
    Node(int value) //带参构造,初始化变量
    {
        Value = value; //初始化数据
        Next = nullptr; //初始化从头往后指针
        Pre = nullptr; //初始化从后往前指针
    }
}
class LinkList
{
Public:
    int Count; //存储的计数
    Node* Head; //指向第一个节点的指针
    Node* Last; //指向最后节点的指针

Public:
    void AddLast(int value) //设置链表结束位
    {
        //当链表未开始时分配最后一位节点
        if (Head == nullptr) //当Head为空时，说明链表没节点
        {
            Head = new Node(value); //分配Head的内存，将数据`value`给与第一位
            Last = Head; //将Last也指向Head,此时说明链表就一位
            return; //返回，修改完成
        }
        //当链表未开始时分配最后一位节点
        Node* node = Last;      //定义指针node，将其指向Last。（用于存储原本的Last地址）
                                //node -> {Vlaue = X,Next = nullptr,Pre = Y}
                                //Last -> {Vlaue = X,Next = nullptr,Pre = Y}
        Last = new Node(value); //分配Last位内存，将数据`value`给与最后一位
                                //node -> {Vlaue = X,Next = nullptr,Pre = Y}
                                //Last -> {Vlaue = value,Next = nullptr,Pre = nullptr}
        Last->Pre = node;       //将Last中的Pre指向node的位置
                                //node -> {Vlaue = X,Next = nullptr,Pre = Y}
                                //Last -> {Vlaue = value,Next = nullptr,Pre = node}
        node->Next = Last       //将原本Last位的上一位指针指向现在的末尾位
                                //node -> {Vlaue = X,Next = Last,Pre = Y}
                                //Last -> {Vlaue = value,Next = nullptr,Pre = node}
    }

    void AddFirst(int value) //设置链表第一位
    {
        //当链表未开始时分配最后一位节点
        if (Head == nullptr) //当Head为空时，说明链表没节点
        {
            Head = new Node(value); //分配Head的内存，将数据`value`给与第一位
            Last = Head; //将Last也指向Head,此时说明链表就一位
            return; //返回，修改完成
        }
        Node* node = Head;      //定义指针node，将其指向Head。（用于存储原本的Head地址）
                                //node -> {Vlaue = X,Next = Y,Pre = nullptr}
                                //Head -> {Vlaue = X,Next = Y,Pre = nullptr}
        Head = new Node(value); //分配Head位内存，将数据`value`给与第一位
                                //node -> {Vlaue = X,Next = Y,Pre = nullptr}
                                //Head -> {Vlaue = value,Next = nullptr,Pre = nullptr}
        Head->Next = node;      //将Head中的Next指向node的位置
                                //node -> {Vlaue = X,Next = Y,Pre = nullptr}
                                //Head -> {Vlaue = value,Next = node,Pre = nullptr}
        node->Pre = Head       //将原本Head位的下一位指针指向现在的第一位
                                //node -> {Vlaue = X,Next = Y,Pre = Head}
                                //Head -> {Vlaue = value,Next = node,Pre = nullptr}

    }

    int Get(int index) //获取第index位的数值
    {
        if (Head == nullptr) //当链表没有数值
        {
            return 0;       //返回无
        }
        Node* node = Head; //定义指针node，将其指向Head。（归零）
        for (int i = 0, i < index, i++) //i循环到index位
        {
            if (node == nullptr) //当node变空说明链表没有index位
            {
                return 0;       //返回无
            }
            node = node-> Next; //让链表前进1
        }
        return node->Value; //返回获得的值
    }

    void RemoveFirst() //掐头
    {
        if (Head == nullptr) //当链表没有数值
        {
            return 0;       //返回无
        }
        Node* next = Head->Next; //定义next保存Head下一位内容
        delete Head; //删除Head位
        Head = nullptr; //防泄露
        if (next != nullptr) //当下一位有数值
        {
            Head = next; //将第一位Head等于下一位
            next->Pre = nullptr; //将原本下一位的前一位改为空
        }
    }

    void InsertAt(int index, int value) //插值
    {
        if (index > 1 && index < count)
        {
            Node* node = Head; //定义指针node，将其指向Head。（归零）
            for (int i = 0; i < index; i++) //i循环到index位
            {
                if (node == nullptr) //当node变空说明链表没有index位
                {
                    return;       //返回无
                }
                node = node-> Next; //让链表前进1
            }
            Node* newnode = new Node(value); //新建index后一位
            *newnode = *node; //将index后一位还原为node
            node->Value = value; //将node数值改为value
            node->Next = newnode; //node的下一位改成newnode
            newnode->Pre = node; //将newnode的上一位改成node
            count++; //增加计数
        }
    }

    ~LinkList() //析构函数
    {
    Count = 0;
    delete[] Head;
    delete[] Last;
    Head = nullptr;
    Last = nullptr;
    }
};