链表总结

原理

链表是一种物理存储结构上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。

由一系列节点（Node）通过指针连接而成，从一个头节点（Head）开始，头节点作为链表的入口点，它包含了对第一个节点的引用。头节点不存具体的内容，可以存储长度，使用头节点能够使得插入节点更加容易。最后一个节点的指针指向一个空值（NULL），表示链表的结束。

优点：链表的插入操作更快（头插），无需预先分配内存空间

缺点：失去了随机读取的优点（需要从头节点开始依次遍历，直到找到目标节点）。

创建

插入

主要有两种插入方式：

头插法

1. p指针指向头节点
2. temp的next指向p->next->next
3. p->next指向temp

尾插法

1. 通过循环的方式将p指向结尾的节点
2. temp的next置为nullptr
3. 结尾的节点的next指向temp

遍历

通过条件为节点不是nullptr循环得到每个节点的值（注意第一个头节点）

删除

1. p指针指向需要删除的节点的前一个节点
2. p->next置为p->next->next
3. 释放p->next的空间

代码实现

这是最原始的版本，还是存在许许多多的问题的，没有加入泛型，data的类型仅仅是int

struct Node{ //链表节点
    int data;
    Node* next;
};
class LinkedList{   //单向链表
private:
    Node* data;
public:
    LinkedList(){   //构造函数创建头节点
        this->data=new Node;
        this->data->data=0;
        this->data->next=nullptr;
    }
    void headInsert(int x){ //头插法创建节点并插入
        this->data->data++;
        Node* temp=new Node;
        temp->data=x;
        temp->next=this->data->next;
        this->data->next=temp;
    }
    void tailInsert(int x){ //尾插法创建节点并插入
        this->data->data++;
        Node* temp=new Node;
        temp->data=x;
        temp->next=nullptr;
        Node* p=this->data;
        while(p->next!=nullptr){
            p=p->next;
        }
        p->next=temp;
    }
    bool removeByIndex(int index){  //按照位置删除节点
        if (index >= this->length()) {
            return false;
        }
        this->data->data--;
        Node* p = this->data;
        for (int i = 0; i < index; i++) {
            p = p->next;
        }
        Node* temp = p->next;
        p->next = p->next->next;
        delete temp;
        return true;
    }
    int read(int index){    //读取某一个位置的节点的值
        Node* p=this->data;
        for(int i=0;i<=index;i++){
            p=p->next;
        }
        return p->data;
    }
    void write(int index,int x){    //修改某一个位置的节点的值
        Node* p=this->data;
        for(int i=0;i<=index;i++){
            p=p->next;
        }
        p->data=x;
    }
    int length(){   //获取长度
        return this->data->data;
    }
    bool isEmpty(){ //判断是否为空
        if(this->length()==0){
            return true;
        }
        return false;
    }
    void println(){ //打印链表
        Node* p=this->data->next;
        while(p!=nullptr){
            cout<<p->data<<"->";
            p=p->next;
        }
        cout<<"NULL"<<endl;
    }
};