0.定义节点结构

template<typename T>
struct Node{
    Node* next;
    T data;
    Node(T data) : data(data),next(nullptr){
    }
};

一个指向下一个节点的指针next,一个存放数据的变量data,一个构造函数

1.定义链表类

template<typename T>
class LinkedList{
    private:
    int size;
    Node<T>* head;
    public:
    ~LinkedList();
    LinkedList() : head(NULL),size(0) {}
    void insert(int index,T value);
    void remove(int index);
    void printAllValue();
    void editValue(int index,T value);
    T getValue(int index);
    int findValue(T value);
};

2.链表类的析构函数

template<typename T>
LinkedList<T>::~LinkedList(){
    Node<T>* cur = head;
    while(cur != nullptr){
        Node<T>* temp = cur;
        cur = cur->next;
        delete temp;
    }
    size = 0;
}

定义一个新指针cur,将其初始化为头指针,接着用这个cur指针通过cur = cur->next遍历链表的每个节点,逐个delete掉就可以了;

3.链表的增删改查

template<typename T>
void LinkedList<T>::insert(int index,T value){
    if(index < 0 || index > size){
        throw out_of_range("Invalid Position");
    }
    if(index == 0){
        /*Node<T>* temp = head;
        head = new Node<T>(value);
        head->next  = temp;*/
        Node<T>* new_node = new Node(value);
        new_node->next = head;
        head = new_node;
        size+=1;
    }else{
        Node<T>* new_node = new Node(value);
        Node<T>* cur = head;
        for(int i=0;i <index-1; i++){
            cur = cur->next;
        }
        new_node->next = cur->next;
        cur->next = new_node;
        size+=1;
    }


}

//删
template<typename T>
void LinkedList<T>::remove(int index){
    if(index < 0 || index >= size){
        throw out_of_range("Invalid Position");
    }
    if(index == 0){
        Node<T>* temp = head;
        head = temp->next;
        delete temp;
    }
    else{
        Node<T>* cur=head;
        for(int i = 0;i < index-1;i++){
            cur = cur->next;
        }
        Node<T>* temp = cur->next;
        cur->next  = temp -> next;
        delete temp;
    }
    size-=1;
}

//改
template<typename T>
void LinkedList<T>::editValue(int index, T value){
    if(index<0 || index>=size){
        throw out_of_range("Invalid Position");
    }
    Node<T>* cur = head;
    for(int i =0;i<index;i++){
        cur = cur->next;
    }
    cur->data = value;
}

//查
template<typename T>
int LinkedList<T>::findValue(T value){
    Node<T>* cur = head;
    for(int i = 0;i < size;i++){
        if(cur->data == value){
            return i;
        }
        cur = cur->next;
    }
    return -1;
}

插入

删除

查找