对于每一种数据结构的实现，我都会把核心完整代码放到这里。
链表是最常见的数据结构之一，面试时经常会拿来和数组进行比较，要理解数组和链表的内存布局，以及什么场景用什么数据结构进行存储，那么你的思维将不受限制。
学习链表一定要结合数组进行对比，才能看出来链表优劣，明确各自适应场景。
所申请的内存空间，必须是线性连续，且申请的空间大小必须提前确定。
插入和删除操作代价比较大，需要该位置后面的数据都向后移动，留出一个空位进行插入，或者都向前移动，把该空位的数据进行覆盖（也就是删除）；
查询代价较小，数组是连续存储的，知道该数组名称，可根据下标直接查询；
不利于扩展，数组空间是提前申请的，当存储空间不够时，需要重新申请空间。
申请内存中存储空间，不要求连续，只需要保存下一个存储空间的内存地址即可。
插入和删除操作比较容易，只需要改变指针的指向即可；
查询代价较大，不具备随机访问能力，需要从头到尾遍历查找；
扩展性较好，不用提前指定大小，插入删除比较随意。
| 数组 | 链表 | |
|---|---|---|
| 查询 | O(1) | O(n) |
| 插入 | O(n) | O(1) |
| 删除 | O(n) | O(1) |
对于频繁查询的场景，选用数组；对于频繁插入删除的场景，选用链表；频繁查询也频繁增删呢？选用数组链表。
如果你有创造性思维的话，数组链表其实是一种更好的数据结构，集数组和链表优点于一身的数据结构，有兴趣的读者下来自行研究（这绝对是亮点）。
内存空间利用率：每一个数组单元是 100% 存储数据，每一个链表单元是存储数据 + 存储指针，数组对于内存的利用上大于链表（当然了，还需要看是否提前知道要存储数据个数）。
链表所分配的空间在内存上不一定连续，但是链表具有其天然优势。
链表分为 4 种情况：单链表，单循环链表，双链表，双循环链表，一定要反复琢磨，理解清楚我下面画的模型，这些模型是本文核心所在。
各自模型如下：
单链表分为 2 种情况：带头结点链表 + 不带头结点链表。
带头结点链表：第一个节点不存储真实数据；
不带头结点链表：第一个节点存储真实数据；
链表上常见操作：创建链表、插入链表，删除链表，查找数据，修改数据，销毁链表。。。
对单链表的操作，以后有时间我在代码实现，其实这 4 种链表实现机制差不多，对其操作的思想也都一样，掌握了一种实现方式，懂得了原理，那么实现其它的就大致相同。
由于篇幅有限，我不可能把 4 种模型，以及每种带头结点、不带头结点都实现代码（这将是 8 种情况），在这里我就只实现双向循环链表，为啥选择实现这个？是因为这种链表在其中比较难，我选择实现较难的模型，简单的就交给你们了。
思路：链表结点类型，然后就是双向循环链表的控制头，在进行具体的各种函数的编写。
C++写函数，最好类内声明函数，类外定义函数；
关于其下的函数名称：保持与 STL 中的函数名称一致，更利于学习 STL；
我所实现的数据结构是面向对象的思想，面向给别人提供工具的思维，你直接把我的代码、以及测试用例拷贝下去就可以跑通，让你真正理解从头到尾的代码逻辑，而不是给出一个模块函数就应付了事，这是数据结构的设计，是需要完整性，工具性的理念。
这不是算法，学习算法和学习数据结构的理念完全不同！
只提供模块的话，那样你根本不知道上下文，是比较懵的，有了完整的代码，认真花时间研究研究肯定是能看通的，如果有兴趣可以打包做自己的静态库，提供一系列工具 + 说明书发布出去，那样你就牛逼了，这就是工具化思维。
有了工具 + 说明书，相当于你提供了 API 和文档，别人就可以按照你的设计，遵从你的规范进行开发，来提升工作效率。
学习数据结构，如果没有面向对象的思维、没有提供工具的思维，那么学习数据结构纯粹就是为了应付面试，这样的话对于数据结构的理解容易受局限，对于工程架构难以深入，距离优秀开发者仍有较大差距，这就是思维、意识上的差距。
#ifndef _DCLINK_H_
#define _DCLINK_H_
#include<iostream>
#include<stdlib.h>
using namespace std;
template<typename Type>
class DCLink;
template<typename Type>
class DCLinkNode{ //这是双向循环链表的结点类型
friend class DCLink<Type>;
public:
DCLinkNode(Type x = 0){
prev = next = NULL;
data = x;
}
~DCLinkNode(){
}
private:
Type data; //数据域
DCLinkNode *prev; //前驱结点指针
DCLinkNode *next; //下一个结点指针
};
template<typename Type>
class DCLink{
public:
DCLink(){ //初始化对象的构造函数
DCLinkNode<Type> *s= new DCLinkNode<Type>;
first = last = s;
s->next = first;
s->prev = last;
size = 0;
}
~DCLink(){
}
public:
bool push_back(const Type &); //尾随函数
void show_link()const; //显示链表
bool push_front(const Type &); //前插函数
bool insert_val(); //根据值得插入
bool pop_back(); //删除最后一个结点
private:
bool insert_pos();
private:
DCLinkNode<Type> *first; //永远指向链表第一个结点
DCLinkNode<Type> *last; //永远指向链表的最后一个结点
size_t size; //统计结点个数，不算没有数据的第一个;
};
template<typename Type>
bool DCLink<Type>::push_back(const Type &x){
DCLinkNode<Type> *s = new DCLinkNode<Type>(x);
if(s == NULL){
return false;
}
s->next = first;
s->prev = last;
last->next = s;
first->prev = s;
last = s;
size++;
return true;
}
template<typename Type>
void DCLink<Type>::show_link()const{
DCLinkNode<Type> *p = first->next;
while(p != first){
cout<<p->data<<"--> ";
p = p->next;
}
cout<<"NULL"<<endl;
}
template<typename Type>
bool DCLink<Type>::push_front(const Type &x){
DCLinkNode<Type> *s = new DCLinkNode<Type>(x);
if(s == NULL){
return false;
}
s->next = first->next;
first->next->prev = s;
s->prev = first;
first->next = s;
size++;
return true;
}
template<typename Type>
bool DCLink<Type>::insert_val(){
int number1;
int number2;
cout<<"请输入要插入位置的值 :";
cin>>number1;
cout<<"请输入要插入的数据";
cin>>number2;
DCLinkNode<Type> *p = first->next;
DCLinkNode<Type> *s = new DCLinkNode<Type>(number2);
while(p != first){
if(p->data == number1){
s->prev = p->prev;
s->next = p;
p->prev->next = s;
p->prev = s;
size++;
}
p = p->next;
}
return true;
}
template<typename Type>
bool DCLink<Type>::pop_back(){
DCLinkNode<Type> *tmp = last->prev;
DCLinkNode<Type> *tmp1 = last;
tmp->next = first;
first->prev = tmp;
last = tmp;
size--;
delete tmp1;
tmp1 = NULL;
return true;
}
#endif#include<iostream>
#include"dclink.h"
using namespace std;
int main(void){
DCLink<int> dc;
for(int i = 0; i < 10; i++){
dc.push_back(i);
}
dc.push_front(-1);
dc.show_link();
dc.insert_val(); //均是前插
dc.show_link();
dc.pop_back();
cout<<"删除最后一个结点时如下: "<<endl;
dc.show_link();
return 0;
}链表操作：插入、删除、销毁、查找之类的关键操作，需要先在纸上画出模型，充分理解指针指向的改变，即可解决（参照我上面给出的模型 + 部分代码）。
链表销毁：从头往后一个一个删除链表结点，只要对下一个节点的地址空间进行保存，这样循环下去就一一释放了;
链表排序：指针的指向不变，即整个链表的结构不变，不会有增删操作，只是交换存储空间的数据即可。
玩数组就是玩下标，玩链表就是玩指针！
原创文章链接：从零开始学习数据结构-->链表