对于每一种数据结构的实现，我都会把核心完整代码放到这里。
链表是最常见的数据结构之一，面试时经常会拿来和数组进行比较，要理解数组和链表的内存布局，以及什么场景用什么数据结构进行存储，那么你的思维将不受限制。
学习链表一定要结合数组进行对比，才能看出来链表优劣，明确各自适应场景。
数组VS链表
1、数组
所申请的内存空间，必须是线性连续，且申请的空间大小必须提前确定。
插入和删除操作代价比较大，需要该位置后面的数据都向后移动，留出一个空位进行插入，或者都向前移动，把该空位的数据进行覆盖（也就是删除）；
查询代价较小，数组是连续存储的，知道该数组名称，可根据下标直接查询；
不利于扩展，数组空间是提前申请的，当存储空间不够时，需要重新申请空间。
2、链表
申请内存中存储空间，不要求连续，只需要保存下一个存储空间的内存地址即可。
插入和删除操作比较容易，只需要改变指针的指向即可；
查询代价较大，不具备随机访问能力，需要从头到尾遍历查找；
扩展性较好，不用提前指定大小，插入删除比较随意。
3、时间复杂度
数组
链表
查询
O(1)
O(n)
插入
O(n)
O(1)
删除
O(n)
O(1)
对于频繁查询的场景，选用数组；对于频繁插入删除的场景，选用链表；频繁查询也频繁增删呢？选用数组链表。
如果你有创造性思维的话，数组链表其实是一种更好的数据结构，集数组和链表优点于一身的数据结构，有兴趣的读者下来自行研究（这绝对是亮点）。
内存空间利用率：每一个数组单元是%存储数据，每一个链表单元是存储数据+存储指针，数组对于内存的利用上大于链表（当然了，还需要看是否提前知道要存储数据个数）。
链表
链表所分配的空间在内存上不一定连续，但是链表具有其天然优势。
链表分为4种情况：单链表，单循环链表，双链表，双循环链表，一定要反复琢磨，理解清楚我下面画的模型，这些模型是本文核心所在；
各自模型如下：
(1)、单链表
(2)、单循环链表
(3)、双链表
(4)、双循环链表
链表上的操作
1、单链表单链表分为2种情况：带头结点链表+不带头结点链表。
带头结点链表：第一个节点不存储真实数据
不带头结点链表：第一个节点存储真实数据
链表上常见操作：创建链表、插入链表，删除链表，查找数据，修改数据，销毁链表.......
对单链表的操作，以后有时间我在代码实现，其实这4种链表实现机制差不多，对其操作的思想也都一样，掌握了一种实现方式，懂得了原理，那么实现其它的就大致相同。
由于篇幅有限，我不可能把4种模型，以及每种带头结点、不带头结点都实现代码（这将是8种情况），在这里我就只实现双向循环链表，为啥选择实现这个？是因为这种链表在其中比较难，我选择实现较难的模型，简单的就交给你们了。
2、双向循环链表
(1)、模型如下：
思路：链表结点类型，然后就是双向循环链表的控制头，在进行具体的各种函数的编写。
C++写函数，最好类内声明函数，类外定义函数;
关于其下的函数名称：保持与STL中的函数名称一致，更利于学习STL;
我所实现的数据结构是面向对象的思想，面向给别人提供工具的思维，你直接把我的代码、以及测试用例拷贝下去就可以跑通，让你真正理解从头到尾的代码逻辑，而不是给出一个模块函数就应付了事，这是数据结构的设计，是需要完整性，工具性的理念。
这不是算法，学习算法和学习数据结构的理念完全不同！
只提供模块的话，那样你根本不知道上下文，是比较懵的，有了完整的代码，认真花时间研究研究肯定是能看通的，如果有兴趣可以打包做自己的静态库，提供一系列工具+说明书发布出去，那样你就牛逼了，这就是工具化思维。
有了工具+说明书，相当于你提供了API和文档，别人就可以按照你的设计，遵从你的规范进行开发，来提升工作效率。学习数据结构，如果没有面向对象的思维、没有提供工具的思维，那么学习数据结构纯粹就是为了应付面试，这样的话对于数据结构的理解容易受局限，对于工程架构难以深入，距离优秀开发者仍有较大差距，这就是思维、意识上的差距。C++实现了部分函数功能：
1#ifndef_DCLINK_H_2#define_DCLINK_H_34#includeiostream5#includestdlib.h6usingnamespacestd;78templatetypenameType9classDCLink;templatetypenameType12classDCLinkNode{//这是双向循环链表的结点类型13friendclassDCLinkType;14public:15DCLinkNode(Typex=0){16prev=next=NULL;17data=x;18}19~DCLinkNode(){}22private:23Typedata;//数据域24DCLinkNode*prev;//前驱结点指针25DCLinkNode*next;//下一个结点指针26};templatetypenameType29classDCLink{30public:31DCLink(){//初始化对象的构造函数32DCLinkNodeType*s=newDCLinkNodeType;33first=last=s;34s-next=first;35s-prev=last;36size=0;37}38~DCLink(){}41public:42boolpush_back(constType);//尾随函数43voidshow_link()const;//显示链表44boolpush_front(constType);//前插函数45boolinsert_val();//根据值得插入46boolpop_back();//删除最后一个结点47private:48boolinsert_pos();49private:50DCLinkNodeType*first;//永远指向链表第一个结点51DCLinkNodeType*last;//永远指向链表的最后一个结点52size_tsize;//统计结点个数，不算没有数据的第一个;53};templatetypenameType56boolDCLinkType::push_back(constTypex){57DCLinkNodeType*s=newDCLinkNodeType(x);58if(s==NULL){59returnfalse;60}61s-next=first;62s-prev=last;63last-next=s;64first-prev=s;65last=s;66size++;returntrue;69}templatetypenameType72voidDCLinkType::show_link()const{73DCLinkNodeType*p=first-next;while(p!=first){76coutp-data"--";77p=p-next;78}79cout"NULL"endl;80}templatetypenameType83boolDCLinkType::push_front(constTypex){84DCLinkNodeType*s=newDCLinkNodeType(x);85if(s==NULL){86returnfalse;87}88s-next=first-next;89first-next-prev=s;90s-prev=first;91first-next=s;92size++;returntrue;95}templatetypenameType98boolDCLinkType::insert_val(){99intnumber1;intnumber2;02cout"请输入要插入位置的值:";cinnumber1;cout"请输入要插入的数据";cinnumber2;DCLinkNodeType*p=first-next;DCLinkNodeType*s=newDCLinkNodeType(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;}returntrue;}templatetypenameTypeboolDCLinkType::pop_back(){DCLinkNodeType*tmp=last-prev;DCLinkNodeType*tmp1=last;tmp-next=first;first-prev=tmp;last=tmp;size--;deletetmp1;tmp1=NULL;returntrue;}#endif
(2)、测试代码
1#includeiostream2#include"dclink.h"3usingnamespacestd;45intmain(void){6DCLinkintdc;78for(inti=0;i10;i++){9dc.push_back(i);10}2dc.push_front(-1);13dc.show_link();14dc.insert_val();//均是前插15dc.show_link();16dc.pop_back();17cout"删除最后一个结点时如下:"endl;18dc.show_link();return0;21}22#endif(3)、测试结果分析链表操作：插入、删除、销毁、查找之类的关键操作，需要先在纸上画出模型，充分理解指针指向的改变，即可解决（参照我上面给出的模型+部分代码）。链表销毁：从头往后一个一个删除链表结点，只要对下一个节点的地址空间进行保存，这样循环下去就一一释放了;链表排序：指针的指向不变，即整个链表的结构不变，不会有增删操作，只是交换存储空间的数据即可。玩数组就是玩下标，玩链表就是玩指针！推荐阅读：从零开始学习数据结构--入门篇疫情之下，如何应对远程线上面试？年参加秋招的他们，现在怎么样了？认真的人自带光芒wait
一辈子很长，要和有趣的人在一起