链表

链表和数组区别

• 两者的区别：
  • 数组静态分配内存，链表动态分配内存。
  • 数组在内存中是连续的，链表是不连续的。
  • 数组利用下标定位，查找的时间复杂度是O(1)，链表通过遍历定位元素，查找的时间复杂度是O(N)。
  • 数组插入和删除需要移动其他元素，时间复杂度是O(N)，链表的插入或删除不需要移动其他元素，时间复杂度是O(1)。
• 数组的优点：
  • 随机访问性比较强，可以通过下标进行快速定位。
  • 查找速度快
• 数组缺点：
  • 插入和删除的效率低，需要移动其他元素。
  • 会造成内存的浪费，因为内存是连续的，所以在申请数组的时候就必须规定七内存的大小，如果不合适，就会造成内存的浪费。
  • 内存空间要求高，创建一个数组，必须要有足够的连续内存空间。
  • 数组的大小是固定的，在创建数组的时候就已经规定好，不能动态拓展。
• 链表优点
  • 插入和删除的效率高，只需要改变指针的指向就可以进行插入和删除。
  • 内存利用率高，不会浪费内存，可以使用内存中细小的不连续的空间，只有在需要的时候才去创建空间。大小不固定，拓展很灵活。
• 链表缺点：
  • 查找的效率低，因为链表是从第一个节点向后遍历查找。

单链表和双链表的区别：

• 单链表的每一个节点中只有指向下一个结点的指针，不能进行回溯，适用于节点的增加和删除。
• 双链表的每一个节点给中既有指向下一个结点的指针，也有指向上一个结点的指针，可以快速的找到当前节点的前一个节点，适用于需要双向查找节点值的情况。
• 双链表相对于单链表的优点：
  • 删除单链表中的某个节点时，一定要得到待删除节点的前驱，得到其前驱的方法一般是在定位待删除节点的时候一路保存当前节点的前驱，这样指针的总的的移动操作为2n次，如果是用双链表，就不需要去定位前驱，所以指针的总的的移动操作为n次。
  • 查找时也是一样的，可以用二分法的思路，从头节点向后和尾节点向前同时进行，这样效率也可以提高一倍，但是为什么市场上对于单链表的使用要超过双链表呢？从存储结构来看，每一个双链表的节点都比单链表的节点多一个指针，如果长度是n，就需要n*lenght（32位是4字节，64位是8字节）的空间，这在一些追求时间效率不高的应用下就不适用了，因为他占的空间大于单链表的1/3，所以设计者就会一时间换空间。

循环双链表

// 待完善
template<typename T>
struct Node{
    Node(){}
    Node* pre;
    Node* next;
    T val;
};

template<typename T,typename node=Node<T>>
class List{
    public:
    List():n(0){
        _node=new node();
        _node->pre=_node;
        _node->next=_node;
    }
    bool empty()const{return n==0;}
    int size()const{return n;}
    void push_back(const T& x){
        node* p=new node();
        p->val=x;++n;
        node* pre_node=_node->pre;
        pre_node->next=p;
        p->pre=pre_node;
        p->next=_node;
        _node->pre=p;
    }
    void push_front(const T& x){
        node* p=new node();
        p->val=x;++n;
        p->next=_node->next;
        _node->next->pre=p;
        p->pre=_node;
        _node->next=p;
    }
    T back()const{return _node->pre->val;}
    T front()const{return _node->next->val;}
    void pop_back(){
        --n;
        node* p=_node->pre;
        node* q=p->pre;
        q->next=_node;
        _node->pre=q;
        delete p;
    }
    void pop_front(){
        --n;
        node* p=_node->next;
        node*q =p->next;
        _node->next=q;
        q->pre=_node;
        delete p;
    }
    private:
    node* _node;
    int n;
};