模拟STL顺序容器list

title: 模拟STL顺序容器list

相对于vector的连续线性空间,list每次插入或删除一个元素就会分配或者释放一块空间.因此,list对空间的运用十分精准.

重点说一下list的插入和移除操作:

插入一个节点作为尾节点,思路是申请一块内存,将原list节点最后一个节点的 next 指向这个内存,并将该节点的next 设置为NULL.

当需要在中间插入一个节点时,先遍历找到需要插入节点的前一个节点node1,然后将node1的next指向该节点 并将该节点的next指向node1原来的下一个节点node2.

移除操作当需要移除一个尾节点node1时,将前一个节点的next指向NULL,然后删除该节点的内存.

当node1不是尾节点时,将node1前一个节点node0的next指向*(node1.next).next 然后删除该节点所占的内存.

#ifndef MY_LINKLIST_H
#define MY_LINKLIST_H
#include<vector>
#include<iostream>
using namespace std;
template <typename T> 
class LinkList {
    template<typename T> struct ListNode {
        T val;
        ListNode<T> *next;
        ListNode<T>(int x): val(x){}
    };
private:
    ListNode<T>* head; 
public:
    LinkList<T>() {      //creat a null list
        head = new ListNode<T>(0); head->next = nullptr;
    }   
    //~LinkList<T>();
    //creat list by a array
    void creatList(vector<T>& arr);  
    //insert x at position i;
    void insElem(int i, T x); 
    //get list length
    int getLen();    
    //delete a  node at pisition i
    T delElem(int i);
    //check empty
    bool empty() { return !head->next; }
    void printList() {
        ListNode<T>* tmp = head->next;
        while (tmp) {
            cout << tmp->val<<" ";
            tmp = tmp->next;
        }
        cout << endl;
        delete tmp;
    }
};
template<typename T>                   
void LinkList<T>::creatList(vector<T>& arr) {
    ListNode<T>* s;
    head = new ListNode<T>(0);
    head->next = nullptr;
    for (int i = arr.size()-1; i>=0; i--) {
        s = new ListNode<T>(arr[i]);
        s->next = head->next;
        head->next = s;
    }
}
template<typename T>
int LinkList<T>::getLen() {
    int len = 0;
    ListNode<T>* p; p = head->next;
    while (p) {
        len++;
        p = p->next;
    }
    return len;
}
template<typename T>
void LinkList<T>::insElem(int i, T x) {    
    if (i <0 || i > getLen())  
            throw "wrong positon";
    ListNode<T>* p = head;
    for (int j = 0; j < i; j++) {
        p = p->next;
    }
    ListNode<T>* tmp = new ListNode<T>(x);
    tmp->next=p->next;
    p->next = tmp;
}
template<typename T>
T LinkList<T>::delElem(int i) {
    if (i < 0 || i >= getLen())
        throw "wrong position";
    ListNode<T>* p = head;
    for (int j = 0; j < i; j++) {
        p = p->next;
    }
    ListNode<T>* q =p->next;
    p->next = q->next;
    delete q;
}
#endif