线性表list，有元素组成的有限且有序的序列。
线性表有两种：顺序表（array-based list或sequencetial list）和链表（Linked list）

“栅栏”思维。
image.png
下面把right/left partition简称right/left。注意理解“位置”pos：
left partition的大小一直是等于fence的pos。

ADT

  1. //最基本（抽象）的线性表的C++抽象结构
  2. template <class Elem> class List{
  3. public:
  4.     virtual void clear() = 0;//清空表
  5.     virtual bool insert(const Elem&) = 0;    //right的前面插入
  6.     virtual bool append(const Elem&) = 0;    //right的最后面插入
  7.     virtual bool remove(Elem& elem) = 0;    /删除right的第一个，注意不是删除elem相同的元素
  8.     virtual void setStart() = 0;    //fence在最前面，left为空的时候
  9.     virtual void setEnd() = 0;        //fence在最后面，rihgt为空的时候
  10.     virtual void prev() = 0;        //fence往左移动一个，left大小-1
  11.     virtual void next() = 0;        //fence往右移动一个，right大小-1
  12.     virtual int leftLength() const = 0;        //left的大小
  13.     virtual int rightLength() const = 0;    //right的大小
  14.     virtual bool setPos(int pos) = 0;        //设置fence使leftLength() = pos
  15.     virtual bool getValue(Elem&) const = 0;    //返回right的第一个elem，没有bool=false
  16.     virtual void print() const = 0;    //打印表全部元素
  18.     //此方法非最基础抽象，可加可不加
  19.     bool find(List<int>& L, int K){
  20.         int t;
  21.         for(L.setStart();L.getValue(t);L.next())
  22.             if(t == K) return true;
  23.            return false;
  24.     }
  25. }

1、顺序表AList（UAList）

也是一个无序的顺序表，Unsorted Array List。又是有序又是无序的怎么理解：
一群年龄大小不一的人坐在一排凳子上。
无序：这群人没有按年龄排序坐。
顺序表：他们做在一排凳子上，互相紧挨着。

链表结构C++实现

  1. template<class Elem>
  2. class AList: public List<Elem>{
  3. private:
  4.     int32_t maxSize;
  5.     int32_t listSize;
  6.     int32_t fence;
  7.     Elem* listArray;
  8. public:
  9.     AList(int size = DefaultListSize){
  10.         maxSize = size;
  11.         listSize = fence = 0;
  12.         listArray = new Elem[maxSize];
  13.     }
  14.     ~AList(){
  15.         delete[] listArray;
  16.     }
  17.     //以下全部是线性表List的成员方法。
  18.     virtual void clear(){
  19.         listSize = fence = 0;
  20.         delete[] listArray;
  21.         listArray = new Elem[maxSize];
  22.     }
  23.     virtual bool insert(const Elem& elem){
  24.         if(listSize == maxSize) return false;
  25.         for(int32_t i = listSize; i > fence; i++)
  26.             listArray[i] = listArray[i - 1];
  27.         listArray[fence] = elem;
  28.         listSize++;
  29.         return true;
  30.     }
  31.     virtual bool append(const Elem& elem){
  32.         if(listSize == maxSize) return false;
  33.         listArray[listSize++] = elem;
  34.         return true;
  35.     }
  36.     virtual bool remove(Elem& elem){
  37.         if(rightLenghth() == 0) return false;
  38.         elem = listArray[fence];
  39.         for(int32_t i = fence;i <listSize - 1;i++)
  40.             listArray[i] = listArray[i + 1];
  41.         listSize --;
  42.         return true;
  43.     }
  44.     virtual void setStart(){
  45.         fence = 0;
  46.     }
  47.     virtual void setEnd(){
  48.         fence = listSize;
  49.     }
  50.     virtual void prev(){
  51.         if(fence > 0) fence -- ;
  52.     }
  53.     virtual void next(){
  54.         if(fence<listSize) fence++;
  55.     }
  56.     virtual void leftLength(){
  57.         return fence;
  58.     }
  59.     virtual void rightLength(){
  60.         return listSize - fence;
  61.     }
  62.     virtual bool setPos(int32_t pos){
  63.         if (pos >=0 && pos <=listSize)
  64.             fence = pos;
  65.     }
  66.     virtual bool getValue(Elem& elem){
  67.         if(rightLength() == 0) return false;
  68.         elem = listArray[fence];
  69.         return true;
  70.     }
  71.     virtual void print(){
  72.         for(int32_t i = 0; i < listSize; i++){
  73.             if(i == fence)
  74.                 cout << "|" << " " << listArray[i] << " ";
  75.             else
  76.                 cout << listArray[i] << " ";
  77.         }
  78.     }
  79. }

扩展：有序顺序表SAList

相比较于

  1. //protected：自主继承，SAList只暴露需要暴露的方法给用户使用。
  2. //如果使用public则顺序表的全部方法都可以使用，这会导致一个问题：
  3. //有序表顺序表的插入只能有一种即按顺序的插入，
  4. //所以有序顺序表就不可以使用比如append方法了。
  5. template<class Elem, class Compare>
  6. class SAList : protected AList<Elem>{
  7. public:
  8.     SAList(int size = DefaultListSize):AList<Elem>(size){};
  9.     ~SAList(){};
  10.     AList<Elem>::clear;
  11.     bool insert(const Elem& elem){
  12.         Elem curr;
  13.         for(setStart(); getValue(curr);next()){
  14.             if(!Compare::lt(curr, elem)) break;
  15.         }
  16.         return AList<Elem>::insert(item);
  17.     }
  18.     AList<Elem>::remove;
  19.     AList<Elem>::setStart;
  20.     AList<Elem>::setEnd;
  21.     AList<Elem>::prev;
  22.     AList<Elem>::next;
  23.     AList<Elem>::leftLength;
  24.     AList<Elem>::rightLenth;
  25.     AList<Elem>::setPos;
  26.     AList<Elem>::getValue;
  27.     AList<Elem>::print;
  28. }

2、链表_单向链表LList

单向链表的节点结构和链表结构如下图，注意链表初始就有一个head首节点也是一个空节点，第一个数据在head节点之后。
image.pngimage.png

节点结构C++实现

  1. //链表节点
  2. template<class Elem>
  3. class Link{
  4.     Link *next;
  5.     Elem element;
  6.     Link(const Elem& elemval, Link* nextval = NULL){
  7.         element = elemval;
  8.         next = nextval;
  9.     }
  10.     Link(Link* nextval = NULL){
  11.         next = nextval;
  12.     }
  13. }

链表结构C++实现

  1. template<class Elem>
  2. class LList : public List<Elem>{
  3. private:
  4.     Link<Elem> *head;
  5.     Link<Elem> *tail;
  6.     Link<Elem> *fence;
  7.     int leftcnt;
  8.     int rightcnt;
  9.     void init(){
  10.         fence = tail = head = new Link<Elem>;
  11.         leftcnt = rightcnt = 0;
  12.     }
  13.     void removeall(){
  14.         while(head != NULL){
  15.             fence = head;
  16.             head = head->next;
  17.             delete fence;
  18.         }
  19.     }
  20. public:
  21.     LList(int size = DefaultListSize){
  22.         init();
  23.     }
  24.     ~LList(){
  25.         removeall();
  26.     }
  27.     virtual void clear(){
  28.         removeall();
  29.         init();
  30.     }
  31.     bool insert(const Elem& elem){
  32.         fence->next = new Link(elem, fence->next);
  33.         rightcnt++;
  34.         return true;
  35.     }
  36.     bool append(const Elem& elem){
  37.         tail->next = new Link(elem, NULL);
  38.         rightcnt++;
  39.         return true;
  40.     }
  41.     bool remove(Elem& elem){
  42.         if(fence->next == NULL) return false;
  43.         elem = fence->next->element;
  44.         Link<Elem>* ltemp = fence->next;
  45.         fence->next = fence->next->next;
  46.         if(tail == ltemp) tail = fence;
  47.         delete ltemp;
  48.         rightcnt--;
  49.         return true;
  50.     }
  51.     void setStart(){
  52.         fence = head;
  53.         rightcnt += leftcnt;
  54.         leftcnt = 0;
  55.     }
  56.     void setEnd(){
  57.         fence = tail;
  58.         leftcnt += rightcnt;
  59.         rightcnt = 0;
  60.     }
  61.     void prev(){
  62.         if(fence == head) return;
  63.         Link<Elem*> temp = head;
  64.         while(temp->next != fence) temp = temp->next;
  65.         fence = temp;
  66.         rightcnt--;
  67.         leftcnt++;
  68.     }
  69.     void next(){
  70.         if(fence ~= tail){
  71.             fence = fence->next;
  72.             rightcnt--;
  73.             leftcnt++;
  74.         }
  75.     }
  76.     int leftLength() { return leftcnt; }
  77.     int rightLength() { return rightcnt; }
  78.     bool setPos(int32_t pos){
  79.         if((pos < 0) || (pos > (rightcnt + leftcnt))) return false;
  80.         fence = head;
  81.         for(int32_t i = 0; i < pos; i++) fence = fence->next;
  82.         rightcnt = rightcnt + leftcnt - pos;
  83.         leftcnt = pos;
  84.         return true
  85.     }
  86.     bool getValue(Elem& elem){
  87.         if(rightLength() == 0) return false;
  88.         elem = fence->element;
  89.         return true;
  90.     }
  91.     void print(){
  92.         Link<Elem>* temp = NULL;
  93.         for(temp = head; temp != fence; temp = temp->next){
  94.             cout << temp->next->element << " ";
  95.         }
  96.         cout << "| ";
  97.         for(;temp->next != NULL;temp = temp->next){
  98.             cout << temp->next->element << " ";
  99.         }
  100.     }

扩展：有“缓存池”的链表

Link：链表节点类。
用一个Link* freeelist作为节点“缓存池”，freelist其实是一个链表表头，这个链表缓存了可用的链表节点。重载节点的new/delete：
new时：从缓存池去先尝试获取（从freelist的表头获取），如果freelist空了，就调用默认new直接返回内存地址。
delete时：放入缓存池（插入到freelist的表头）。

  1. template<class Elem> class Link{
  2. private:
  3.     static Link<Elem>* freelist;
  4. public:
  5.     Elem element;
  6.     Link* next;
  7.     Link(const Elem& elemval, Link* nextval = NULL){
  8.         element = elemval;
  9.         next = nextval;
  10.     }
  11.     Link(Link* nextval = NULL){
  12.         next = nextval;
  13.     }
  14.     void* operator new(size_t);        //先从缓存池获取，不然就new
  15.     void* operator delete(void *);    //回收给缓存池
  16. }
  18. //Link.cpp
  19. template<class Elem>
  20. Link<Elem>* Link<Elem>::freelist = NULL;
  22. template<Elem>
  23. void* Link<Elem>::operator new(size_t){
  24.     if(freelist == NULL) return ::new Link;    //这里new的最终会在delete的时候回收给freelist
  25.     Link<Elem>* temp = freelist;
  26.     freelist = freelist->next;
  27.     return temp;
  28. }
  30. template<Elem>
  31. void Link<Elem>::operator delete(void* ptr){
  32.     ((Link<Elem>*)ptr)->next = freelist;
  33.     freelist = (Link<Elem>*)ptr;
  34. }

3、链表_双向链表LList

双向链表结构以及节点结构如下图，注意链表初始就有一个head节点，第一个数据在head节点之后。
image.png

双向链表的插入

image.png

双向链表的删除

image.png

节点结构C++实现

  1. template<class Elem> class Link{
  2. private:
  3.     static Link<Elem>* freelist;    //节点缓存池
  4. public:
  5.     Elem element;
  6.     Link* next;
  7.     Link* prev;
  8.     Link(const Elem& e, Link* prev = NULL, Link* next = NULL){
  9.         element = e;
  10.         this->prev = prev;
  11.         this->next = next;
  12.     }
  13.     Link(Link* prev = NULL, Link* next = NULL){
  14.         prev = prev;
  15.         next = next;
  16.     }
  17.     void* operator new(size_t){
  18.         if(freelist == NULL) return ::new Link;
  19.         Link<Elem>* temp = freelist;
  20.         freelist = freelist->next;
  21.     }
  22.     void operator delete(void* ptr){
  23.         ((Link<Elem>*)ptr)->next = freelist;
  24.         freelist = (Link<Elem>*)ptr;
  25.     }
  26. }

链表结构C++实现

  1. template<class Elem>
  2. class LList : public List<Elem>{
  3. private:
  4.     Link<Elem> *head;
  5.     Link<Elem> *tail;
  6.     Link<Elem> *fence;
  7.     int leftcnt;
  8.     int rightcnt;
  9.     void int(){
  10.         fence = tail = head = new Link<Elem>;
  11.         leftcnt = rightcnt = 0;
  12.     }
  13.     void removeall(){
  14.         while(head != NULL){
  15.             fence = head;
  16.             head = head->next;
  17.             delete fence;
  18.         }
  19.     }
  20. public:
  21.     LList(int size = DefaultListSize){
  22.         init();
  23.     }
  24.     ~LList(){
  25.         removeall();
  26.     }
  27.     virtual void clear(){
  28.         removeall();
  29.         init();
  30.     }
  31.     bool insert(const Elem& elem){
  32.         fence->next = new Link(elem, fence,fence->next);
  33.         if(fence->next->next != NULL)
  34.             fence->next->next->prev = fence->next;
  35.         if(tail == fence)
  36.             tail = fence->next;
  37.         rightcnt++;
  38.         return true;
  39.     }
  40.     bool append(const Elem& elem){
  41.         tail = tail->next = new Link<Elem>(elem, tail, NULL);
  42.         rightcnt++;
  43.         return true
  44.     }
  45.     bool remove(Elem& elem){
  46.         if(fence->next == NULL) return false;    //rightcnt == 0
  47.         elem = fence->next->element;
  48.         Link<Elem>* temp = fence->next;
  49.         if(temp->next != NULL) temp->next->prev = fence;
  50.         else tail = fence;
  51.         fence->next = temp->next;
  52.         delete temp;
  53.         rightcnt--;
  54.         return true;
  55.     }
  56.     void setStart(){
  57.         fence = head;
  58.         rightcnt += leftcnt;
  59.         leftcnt = 0;
  60.     }
  61.     void setEnd(){
  62.         fence = tail;
  63.         leftcnt += rightcnt;
  64.         rightcnt = 0;
  65.     }
  66.     void prev(){
  67.         if(fence == head) return;
  68.         fence = fence->prev;
  69.         rightcnt--;
  70.         leftcnt++;
  71.     }
  72.     void next(){
  73.         if(fence ~= tail){
  74.             fence = fence->next;
  75.             rightcnt--;
  76.             leftcnt++;
  77.         }
  78.     }
  79.     int leftLength() { return leftcnt; }
  80.     int rightLength() { return rightcnt; }
  81.     bool setPos(int32_t pos){
  82.         //使用leftcnt == pos
  83.         if((pos < 0) || (pos > (rightcnt + leftcnt))) return false;
  84.         fence = head;
  85.         for(int32_t i = 0; i < pos; i++) fence = fence->next;
  86.         rightcnt = rightcnt + leftcnt - pos;
  87.         leftcnt = pos;
  88.         return true
  89.     }
  90.     bool getValue(Elem& elem){
  91.         if(rightLength() == 0) return false;
  92.         elem = fence->element;
  93.         return true;
  94.     }
  95.     void print(){
  96.         Link<Elem>* temp = NULL;
  97.         for(temp = head; temp != fence; temp = temp->next){
  98.             cout << temp->next->element << " ";
  99.         }
  100.         cout << "| ";
  101.         for(;temp->next != NULL;temp = temp->next){
  102.             cout << temp->next->element << " ";
  103.         }
  104.     }

扩展：“节省空间”的双向链表

参考：https://www.cnblogs.com/tiny656/p/4108976.html
一般双向链表节点保存prev和next两个指针，空间两倍于单向链表。
根据异或函数（XOR）的如下性质：
（L^R）^R = L
（L^R）^L = R
如下是链表结构，每个节点保存一个Link*指针xorPtr，值为前后两个节点的异或。则：
C = B->xorPtr ^ A
A = B->xorPtr ^ C
image.png

  1. //节点结构如下：
  2. template<class Elem>
  3. class Link{
  4. private:
  5.     Link<Elem>* freelist;
  6. public:
  7.     Elem element;
  8.     Link<Elem>* xorPtr;    //保存的是上一个节点和一个节点的异或值。
  9. public:
  10.     Link(const Elem& e,Link* prev, Link* next){
  11.         element = e;
  12.         xorPtr = prev ^ next;
  13.     }
  14.     Link(Link* prev, Link* next){
  15.         xorPtr = prev ^ next;
  16.     }
  17. }