1、静态单链表的提出

需要频繁增删数据元素，可以选择单链表，如果数据元素的最大个数是固定的，可能需要一种新的数据结构

单链表的一个缺陷

• 触发条件：长时间使用单链表对象频繁增删数据元素
• 可能结果：堆空间产生大量的内存碎片，导致系统运行缓慢

原因：每增加一个数据元素，都会在堆空间中创建一个数据结点，程序上看没问题，但是在一些系统中，长时间频繁增删堆空间结点，堆空间就可能产生大量内存碎片，直接结果就是系统运行缓慢。

解决方案：设计一种新的线性表

设计思路：在单链表的内部增加一片预留的空间，所有的Node对象都在这篇空间中动态创建和动态销毁

静态单链表需要的只是预留一片固定大小的连续存储空间（栈、堆、全局），不管出处只要是连续的就行，插入数据元素的时候就去这片连续空间中去看，是否有空闲的空间，找到之后就在这个空间中创建Node对象；删除的时候，现在这个内存空间中调用Node对象的析构函数，将这片内存空间标志为可用就行。

除了内存分布的不同，静态单链表和单链表是一样的，从代码上看，只需要更改creat和destory这样个函数就行了，以前操作的是堆空间中内存，现在操作的是那一片连续的内存空间了。

2、静态单链表的继承层次结构

3、静态单链表的实现

实现思路：

• 通过模板定义静态单链表类StaticLinkList
• 在类中定义固定大小的空间unsigned char[]
• 重写creat和destory函数，改变内存的分配和归还的方式
• 在Node类中重载operator new操作符，用于在指定内存上创建对象

template <typename T, int N> class StaticLinkList : public LinkList<T> {     typedef typename LinkList<T>::Node Node; protected:     unsigned char m_space[sizeof(Node) * N];    // 定义内存空间     int m_used; // 状态标记            // 分配内存单元，创建Node对象     Node* create()     {         Node ret = NULL;                  // 遍历判断m_used是否可用         for(int i = 0; i < N; i++)         {             if ( !m_used[i])    // 当前内存可用的时候，就可以用来分配使用了             {                 ret = reinterpret_cast<Node*>(m_used) + i;  // 找到未使用的一个内存空间                 // 步长为sizeof(Node)                 m_used[i] = 1;  // 标记使用                 break;             }         }                  return ret;     }          void destroy(Node* pn)     {              }    };

注意这里会存在一个问题， 由于Node存在着一个泛指类类型成员变量value

struct Node : public Object {     T value;    // 数据域     Node* next; // 指针域 };