1、链式存储结构线性表的实现：
LinkList设计要点：类模板
通过头结点访问后继节点
定义内部结点类型Node，用于描述数据域和指针域
实现线性表的关键操作（增、删、改、查等）
2、LinkList template <typename T> class LinkList : public List<T> { protected: struct Node : public Object { T value; Node* next; }; Node m_header; int m_length; public: LinkList() {} };具体实现
template <typename T> class LinkList : public List<T> { protected: struct Node : public Object { T value; // 数据域 Node* next; // 指针域 }; mutable Node m_header; // 头结点，是不是弄成指针更方便点儿 int m_length; // 记录链表长度 public: LinkList() { m_header.next = NULL; m_length = 0; } // 链表末尾插入元素 bool insert(const T& e) { return insert(m_length, e); } // 指定位置插入元素 bool insert(int i, const T& e) { // 注意i的范围 bool ret = ((i>=0) && (i<=m_length)); cout << "ret = " << ret << endl; if (ret) { Node* node = new Node(); if (node != NULL) { // current的目标指向其实都是目标位置的前一个，比如：在第0个位置增加元素，current指向的是header Node* current = &m_header; for(int p = 0; p < i; p++) { current = current->next; } node->value = e; node->next = current->next; current->next = node; m_length++; } else { cout << "THROW_EXCEPTION" << endl; THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element"); } } return ret; } // 删除指定位置元素 bool remove(int i) { // 注意i的范围 bool ret = ((i>=0) && (i<m_length)); if (ret) { Node* current = &m_header; for(int p = 0; p < i; p++) { current = current->next; } Node* toDel = current->next; current->next = toDel->next; delete toDel; m_length--; } return ret; } // 设定指定位置的元素 bool set(int i, const T& e) { // 注意i的范围 bool ret = ((i>=0) && (i<m_length)); if (ret) { Node* current = &m_header; for(int p = 0; p < i; p++) { current = current->next; } current->next->value = e; } return ret; } // get函数用起来不方便，重载一下 T get(int i) const { T ret; if (get(i, ret)) { return ret; } else { THROW_EXCEPTION(IndexOutOfBoundsException, "Invalid parameter i to get element..."); } } // 获取指定位置的元素 bool get(int i, T& e) const { bool ret = ((i>=0) && (i<m_length)); if (ret) { Node* current = &m_header; for(int p = 0; p < i; p++) { current = current->next; } e = current->next->value; // get是const成员函数，按理来说不能修改成员变量的值，Node* current=&m_header，会被误认为要更改成员变量的值，故报错 // 解决方案是对m_header加上mutable，开一个例外 } return ret; } int length() const { return m_length; } void clear() { // 释放每一个结点 while(m_header.next) { Node* toDel = m_header.next; m_header.next = toDel->next; delete toDel; } m_length = 0; } ~LinkList() { clear(); } };问题：头结点隐患，实现代码优化
创建m_header时，会调用T value，用泛指类型创建头结点的数据域，当泛指类型为用户自定义类型时，用用户自定义的类类型在库中创建对象，就有可能出错了，而且在外部看来，并没有用该类型创建对象，问题定位很麻烦。
解决办法：构造头结点时，不调用泛指类型创建头结点，而是按内存分布自己重建构造一个类对象，注意一定要和以前的头结点的内存分布一样，不仅是成员变量的内存大小，同样也要和以前一样继承于Object
// 直接创建头结点，存在隐患 mutable Node m_header; // 重新构造之后的头结点 mutable struct : public Object { char reserved[sizeof(T)]; // 没实际作用，占空间 Node* next; } m_header;重新构造后的头结点在内存布局上和之前没有差异，差异在于不管泛指类型是什么，都不会去调用泛指类型的构造函数了。虽然它们在内存布局上是一样的，但是新构造的头结点是个空类型，不能直接用，使用时要进行类型转换
Node* ret = reinterpret_cast<Node*>(&m_header);优化后的完整代码：
template <typename T> class LinkList : public List<T> { protected: struct Node : public Object { T value; // 数据域 Node* next; // 指针域 }; // 重新构造头结点 mutable struct : public Object { char reserved[sizeof(T)]; // 没实际作用，占空间 Node* next; } m_header; int m_length; // 记录链表长度 // 位置定位函数，重复使用，进行抽象，方便使用 Node* position(int i) const { Node* ret = reinterpret_cast<Node*>(&m_header); for(int p = 0; p < i; p++) { ret = ret->next; } return ret; } public: LinkList() { m_header.next = NULL; m_length = 0; } bool insert(const T& e) { return insert(m_length, e); } bool insert(int i, const T& e) { // 注意i的范围 bool ret = ((i>=0) && (i<=m_length)); cout << "ret = " << ret << endl; if (ret) { Node* node = new Node(); if (node != NULL) { Node* current = position(i); node->value = e; node->next = current->next; current->next = node; m_length++; } else { THROW_EXCEPTION(NoEnoughMemoryException, "No memory to insert new element"); } } return ret; } bool remove(int i) { // 注意i的范围 bool ret = ((i>=0) && (i<m_length)); if (ret) { Node* current = position(i); Node* toDel = current->next; current->next = toDel->next; delete toDel; m_length--; } return ret; } bool set(int i, const T& e) { bool ret = ((i>=0) && (i<m_length)); if (ret) { position(i)->next->value = e; } return ret; } // get函数用起来不方便，重载一下 T get(int i) const { T ret; if (get(i, ret)) { return ret; } else { THROW_EXCEPTION(IndexOutOfBoundsException, "Invalid parameter i to get element..."); } } bool get(int i, T& e) const { bool ret = ((i>=0) && (i<m_length)); if (ret) { e = position(i)->next->value; } return ret; } int length() const { return m_length; } void clear() { // 释放每一个结点 while(m_header.next) { Node* toDel = m_header.next; m_header.next = toDel->next; delete toDel; } m_length = 0; } ~LinkList() { clear(); } };注意每次代码修改之后都要进行测试，有可能由于修改的代码引入了新的bug
3、小结通过类模板实现链表，包含头结点和长度成员
定义结点类型，并通过堆中的结点对象构成链式存储
为了避免构造错误的隐患，头结点类型需要重定义
代码优化是编码完成后必不可少的环节