一、实现链表

1. 什么是链表

百度百科

链表是一种物理存储单元上非连续、非顺序的存储结构，数据元素的逻辑顺序是通过链表中的指针链接次序实现的。链表由一系列结点（链表中每一个元素称为结点）组成，结点可以在运行时动态生成。每个结点包括两个部分：一个是存储数据元素的数据域，另一个是存储下一个结点地址的指针域。
相比于线性表顺序结构，操作复杂。由于不必须按顺序存储，链表在插入的时候可以达到O(1)的复杂度，比另一种线性表顺序表快得多，但是查找一个节点或者访问特定编号的节点则需要O(n)的时间，而线性表和顺序表相应的时间复杂度分别是O(logn)和O(1)。

简单的说，就是用指针把储存每一个数据的节点连起来，像一条链子，比起数组更灵活，但是指针访问会相对慢一些。

2. 单向链表和双向链表

单向链表

每个节点都只有一个指向后一个节点的指针。

单向链表（单链表）是链表的一种，其特点是链表的链接方向是单向的，对链表的访问要通过顺序读取从头部开始；链表是使用指针进行构造的列表；又称为结点列表，因为链表是由一个个结点组装起来的；其中每个结点都有指针成员变量指向列表中的下一个结点；
链表是由结点构成，head指针指向第一个成为表头结点，而终止于最后一个指向NULL的指针。

双向链表

既有指向前一个节点的指针，也有指向后一个的，比单链表多用了一倍的指针，但是访问起来更方便。

双向链表也叫双链表，是链表的一种，它的每个数据结点中都有两个指针，分别指向直接后继和直接前驱。所以，从双向链表中的任意一个结点开始，都可以很方便地访问它的前驱结点和后继结点。一般我们都构造双向循环链表。

3. 代码实现

头文件定义（List.hpp）

本次实现用双向链表，同时用一个空节点连接头尾。

定义链表节点，有前驱和后继指针。

template <class T>
//节点的定义
class list_node
{
   
public:
    list_node();
    list_node* pre;
    list_node* next;
    T data;
};

链表定义，用一个空节点（connectNode）连接头尾。
画成图大概是这样：

template <class T>
//链表定义
class List
{
   
private:
    list_node<T>* connectNode;
    int list_len;
    //记一下链表的长度
    
public:
    
    List();
    
    void pushBack(T data);
    void pushFront(T data);
    void pushCmp(T data,bool(*cmp)(T,T));
    bool swapNode(list_node<T>*,list_node<T>*);
    bool del(list_node<T>*);
    //链表快速排序
    list_node<T>* partition(list_node<T>*,list_node<T>*,bool(*cmp)(T,T));
    void listSort(list_node<T>*,list_node<T>*,bool(*cmp)(T,T));
    
    list_node<T>* begin() const;
    list_node<T>* end() const;
    
    int size() const;
    bool empty() const;
    
    
};

实现代码(List.cpp)

//
// List.cpp
// Created by Concyclics
// List template, Queue and Stack based on List
//

#include "List.hpp"

template <class T>
list_node<T>::list_node()
{
   
    pre=NULL;
    next=NULL;
}

template <class T>
List<T>::List()
{
   
    connectNode=new list_node<T>;
    connectNode->next=connectNode;
    connectNode->pre=connectNode;
    list_len=0;
}

template <class T>
void List<T>::pushBack(T data)
{
   
    list_node<T>* thisNode=new list_node<T>;
    thisNode->pre=connectNode->pre;
    connectNode->pre->next=thisNode;
    thisNode->next=connectNode;
    connectNode->pre=thisNode;
    thisNode->data=data;
    list_len++;
    return;
}

template <class T>
void List<T>::pushFront(T data)
{
   
    list_node<T>* thisNode=new list_node<T>;
    thisNode->next=connectNode->next;
    connectNode->next->pre=thisNode;
    thisNode->pre=connectNode;
    connectNode->next=thisNode;
    thisNode->data=data;
    list_len++;
    return;
}

template <class T>
void List<T>::pushCmp(T data,bool(*cmp)(T,T))
{
   
    if(size()==0)
    {
   
        pushFront(data);
        return;
    }
    list_node<T>* thisNode=new list_node<T>;
    thisNode->data=data;
    
    for(list_node<T>* i=begin();i!=end();i=i->next)
    {
   
        if(cmp(data,i->data))
        {
   
            thisNode->next=i;
            thisNode->pre=i->pre;
            i->pre->next=thisNode;
            i->pre=thisNode;
            list_len++;
            return;
        }
    }
    
    thisNode->pre=connectNode->pre;
    connectNode->pre->next=thisNode;
    thisNode->next=connectNode;
    connectNode->pre=thisNode;
    list_len++;
    return;
}

template <class T>
list_node<T>* List<T>::begin() const
{
   
    return connectNode->next;
}

template <class T>
list_node<T>* List<T>::end() const
{
   
    return connectNode;
}

template <class T>
int List<T>::size() const
{
   
    return list_len;
}


template <class T>
bool List<T>::empty() const
{
   
    return this->begin()==this->end();
}

template <class T>
bool List<T>::del(list_node<T>* node)
{
   
    if(node==connectNode)return 1;
    node->pre->next=node->next;
    node->next->pre=node->pre;
    delete node;
    list_len--;
    return 0;
}

template <class T>
bool List<T>::swapNode(list_node<T>* a,list_node<T>* b)
{
   
    if(a==connectNode||b==connectNode)return 1;
    T data=a->data;
    a->data=b->data;
    b->data=data;
    return 0;
}

链表快排

template <class T>
list_node<T>* List<T>::partition(list_node<T>* left,list_node<T>* right,bool(*cmp)(T,T))
{
   
    list_node<T>* slow=left;
    list_node<T>* fast=left->next;
    T val=left->data;
    while (fast!=right)
    {
   
        if (cmp(fast->data,val))
        {
   
            slow=slow->next;
            swapNode(slow,fast);
        }
        fast=fast->next;
    }
    swapNode(left,slow);
    return slow;
}

template <class T>
void List<T>::listSort(list_node<T>* left,list_node<T>* right,bool(*cmp)(T,T))
{
   
    if (left!=right)
    {
   
        list_node<T>* tmp=partition(left,right,cmp);
        listSort(left,tmp,cmp);
        listSort(tmp->next,right,cmp);
    }
}