数据结构图文解析之：数组、单链表、双链表介绍及C++模板实现

1. 线性表简介

2. 数组

数组在实际的物理内存上也是连续存储的，数组有上界和下界。C语言中定义一个数组：

3. 单向链表

单向链表是链表的一种。链表由节点所构成，节点内含一个指向下一个节点的指针，节点依次链接成为链表。因此，链表这种数据结构通常在物理内存上是不连续的。链表的通常含有一个头节点，头节点不存放实际的值，它含有一个指针，指向存放元素的第一个节点。

3.1 单向链表的节点结构

//节点结构 template <typename T> class Node { public :     T _value;     Node* _next; public:     Node() = default;     Node(T value, Node * next)         : _value(value), _next(next){} };

1. _value: 节点的值
2. _next： 指针，指向下一个节点

3.2 单向链表的抽象数据结构

//单链表 template <typename T> class SingleLink { public:     typedef Node<T>*  pointer;     SingleLink();     ~SingleLink();       int size();                         //获取长度     bool isEmpty();                     //判空       Node<T>* insert(int index, T t); //在指定位置进行插入     Node<T>* insert_head(T t);         //在链表头进行插入     Node<T>* insert_last(T t);         //在链表尾进行插入       Node<T>*  del(int index);         //在指定位置进行删除     Node<T>*  delete_head();         //删除链表头     Node<T>*  delete_last();         //删除链表尾       T get(int index);                 //获取指定位置的元素     T get_head();                     //获取链表头元素     T get_last();                     //获取链表尾元素       Node<T>* getHead();                 //获取链表头节点   private :     int count;     Node<T> * phead;                   private :     Node<T> * getNode(int index);      //获取指定位置的节点 };

1. phead: 链表的头节点。
2. count: 链表元素个数。

3.3 单链表添加节点

链表的插入元素操作时间复杂度O（1），只需要进行指针的指向修改操作。

在2之后添加7：

1. 为元素7构建节点 。
2. 将节点2 的next指针指向节点7。
3. 将节点7的next指向节点3。（节点3 的位置要先保留起来）

/* 在指定位置插入新节点 */ template <typename T> Node<T>* SingleLink<T>::insert(int index, T t) {     Node<T> * preNode = getNode(index);     if (preNode)     {         Node<T> *newNode = new Node<T>(t,preNode->_next);         preNode->_next = newNode;         count++;         return newNode;     }     return nullptr; }; /* 从头部插入 */ template <typename T> Node<T>* SingleLink<T>::insert_head(T t) {     return insert(0, t); }; /* 从尾部进行插入 */ template <typename T> Node<T>* SingleLink<T>::insert_last(T t) {     return insert(count, t); };

3.4 单链表删除节点

单链表的删除操作同样是一个时间复杂度O（1）的操作，它也只需要修改节点的指针指针后即可销毁被删除节点。例如我们删除链表元素7：

相应的代码：

/* 删除链表指定位置元素 */ template <typename T> Node<T>* SingleLink<T>::del(int index) {     if (isEmpty())         return nullptr;     Node<T>* ptrNode = getNode(index);     Node<T>* delNode = ptrNode->_next;     ptrNode->_next = delNode->_next;     count--;     delete delNode;     return ptrNode->_next; }; /* 删除头节点 */ template<typename T> Node<T>* SingleLink<T>::delete_head() {     return del(0); }; /* 删除尾节点 */ template<typename T> Node<T>*SingleLink<T>::delete_last() {     return del(count); };

3.5 单链表代码测试

int main() {     SingleLink<int> link;     for (int i = 0; i < 10; i++)     {         link.insert(i, i);     }     cout << link.size() << endl;       link.insert_head(1111);     link.insert_last(2222);       SingleLink<int>::pointer ptr = link.getHead();     while (ptr != nullptr)     {         cout << ptr->_value << endl;         ptr = ptr->_next;     }       getchar();     return 0; }

测试结果：

其他的操作较为简单，不在这里贴出代码，文章底部有完整链表类的代码链接。

4. 双向链表

单链表的节点链接是单方向的，要得到指定节点的前一个节点，必须从头遍历链表。

双向链表是链表的一种。与单链表一样，双向节点由节点链接而成，每个节点含有两个指针，分别指向直接前驱与直接后继。从双向链表的任何一个节点开始都能够遍历整个链表。

我们将双向链表实现为双向循环链表，也即是最后一个元素的后继将指向头节点，整个链表形成一个循环

例如，我们为元素1，2，3，4，5 构建一个双向循环链表

4.1 双向链表节点结构

双向循环的节点中，比单向链表中多了一个指向直接前驱的指针

/* 双向链表的节点结构 */ template <typename T> struct Node { public:     Node()= default;     Node(T value, Node<T>* preptr, Node<T>* nextptr)         :_value(value), pre_ptr(preptr), next_ptr(nextptr){}   public:     T _value;     Node<T>* pre_ptr;     Node<T>* next_ptr; };

1. _value: 节点元素的值
2. pre_ptr:指向直接前驱的指针
3. next_ptr:指向直接后继的指针

4.2 双向链表的抽象数据结构

双向链表类的定义与单链表相似。

/* * 双向链表类 */ template<typename T> class DoubleLink { public:     typedef Node<T>* pointer; public:     DoubleLink();     ~DoubleLink(){}; public:     Node<T>* insert(int index, T value);     Node<T>* insert_front(T value);     Node<T>* insert_last(T value);       Node<T>* del(int index);     Node<T>* delete_front();     Node<T>* delete_last();       bool isEmpty();     int size();       T get(int index);     T get_front();     T get_last();     Node<T>* getHead();   private:     Node<T>* phead;     int count; private :     Node<T>* getNode(int index); };

4.3 双向链表添加节点

与单链表一样，双向链表添加节点的时间复杂度为O（1），它也只需要修改相关指针的指向。

/* *将新节点插到第一个位置 */ template <typename T> Node<T>* DoubleLink<T>::insert_front(T value) {     Node<T>* newNode = new Node<int>(value, phead, phead->next_ptr);     phead->next_ptr ->pre_ptr= newNode;     phead->next_ptr = newNode;     count++;     return newNode; }; /* *将新节点插到链表尾部 */ template <typename T> Node<T>* DoubleLink<T>::insert_last(T value) {     Node<T> * newNode = new Node<int>(value, phead->pre_ptr, phead);     phead->pre_ptr->next_ptr = newNode;     phead->pre_ptr = newNode;     count++;     return newNode; }; /* *将节点位置插到index位置之前 */   template <typename T> Node<T>* DoubleLink<T>::insert(int index, T value) {     if (index == 0)         return insert_front(value);       Node<T>* pNode = getNode(index);     if (pNode == nullptr)         return nullptr;     Node<T>* newNode = new Node<T>(value, pNode->pre_ptr, pNode);     pNode->pre_ptr->next_ptr = newNode;     pNode->pre_ptr = newNode;     count++;       return newNode; };

4.4 双向链表删除节点

双向链表的删除操作时间复杂度为O（1）.我们删除节点7：

/* *删除链表第一个节点 *返回删除后链表第一个节点 */ template<typename T> Node<T>* DoubleLink<T>::delete_front() {     if (count == 0)     {         return nullptr;     }     Node<T>* pnode = phead->next_ptr;     phead->next_ptr = pnode->next_ptr;     pnode->next_ptr->pre_ptr = phead;     delete pnode;     count--;     return phead->next_ptr; }; /* *删除链表的末尾节点 *返回删除后链表尾部元素 */ template<typename T> Node<T>* DoubleLink<T>::delete_last() {     if (count == 0)     {         return nullptr;     }     Node<T>*pnode = phead->pre_ptr;     pnode->pre_ptr->next_ptr = phead;     phead->pre_ptr = pnode->pre_ptr;     delete pnode;     count--;     return phead->pre_ptr; } /* *删除指定位置的元素 * */ template <typename T> Node<T>* DoubleLink<T>::del(int index) {     if (index == 0)         return delete_front();     if (index == count - 1)         return delete_last();     if (index >= count)         return nullptr;     Node<T>* pnode = getNode(index);     pnode->pre_ptr->next_ptr = pnode->next_ptr;     pnode->next_ptr->pre_ptr = pnode->pre_ptr;       Node<T>* ptemp = pnode->pre_ptr;     delete pnode;     count--;     return ptemp; };

其他的接口实现都很简单，这里不再讲解。下面有提供完整的工程项目及源代码。

4.5 双向链表代码测试

 int main() {     DoubleLink<int> dlink;     //插入测试     for (int i = 0; i < 10; i++)     {         dlink.insert(0, i+10);     }     dlink.insert(0,  100);     dlink.insert_last(1000);     cout <<"链表长度:"<< dlink.size() << endl;       //删除测试     dlink.delete_front();     dlink.delete_last();     dlink.del(3);         DoubleLink<int>::pointer ptr = dlink.getHead();     ptr = ptr->next_ptr;     while (ptr != dlink.getHead())     {         cout << ptr->_value<<endl;         ptr = ptr->next_ptr;     }       getchar();     return 0; }

测试结果：

链表长度:12 19 18 17 15 14 13 12 11 10

5. 单链表、双向链表源代码

另外声明：

1. C++模板不支持分离编译，因此类定义与成员函数的实现都在.h文件中完成；
2. 可以看到代码中new一个新节点之后，并没有使用(prt!=nullptr)来检查内存分配是否成功，这是因为new失败时直接抛出异常，不同于C语言malloc内存分配失败返回NULL。