数据存储的常用结构有：栈、队列、数组、链表、红黑树
时间复杂度：为什么链表的时间复杂度是O（n）呢？而数组的是O(1）呢？
时间复杂度：就是一个算法执行需要消耗的时间。是这个算法每条语句的执行时间之和。
每条语句的执行时间就是这条语句执行的次数 * 执行的一次的时间之和。
（例如数组和链表：10个数据进行查找和修改，数组只执行一次即可，时间为10秒。而链表需要通过指针依次执行，若该值在第九位则执行了九（n）次，时间为90秒）。
链表和数组的性质区分：
数组是静态数据结构，链表是动态数据结构。
由于链表是空间不连续的，所以链表查找值是需要从头或者尾依次访问判断，语句需要执行n次。不像数组是在一块连续空间，语句只执行1次。
从具体实现上来看：链表是在不连续的空间内，需要靠指针来依次递进的判断来获取，数组是在一块连续的空间内，只需要访问一次即可得到想要获取的元素。
结论：链表需要靠指针依次访问和判断，所以执行了n次，所以时间复杂度是O（n），而数组则是在一块连续的空间进行判断。不论数组多长都只需要执行一次，时间复杂度为O（1）。
》》》》》》》》》》》》》》》》》》》》》》》》》》》
1、栈
回顾一下上一章中【数据结构01】数组中，在数组中只要知道数据的下标，便可通过顺序搜索很快查询到数据，可以根据下标不同自由查找，然而今天要讲的“栈”以及队列这两种数据结构访问是受限制的，只允许在一端读取、插入和删除数据，这时候对它存在的意义产生了很大的疑惑。因为会觉得，相比数组和链表，栈带给我的只有限制，并没有任何优势。那我直接使用数组或者链表不就好了吗？为什么还要用这个“操作受限”的“栈”呢？事实上，从功能上来说，数组或链表确实可以替代栈，但你要知道，特定的数据结构是对特定场景的抽象，而且，数组或链表暴露了太多的操作接口，操作上的确灵活自由，但使用时就比较不可控，自然也就更容易出错。
出栈入栈时间复杂度O(1)
栈：又称堆栈，stack，一个容器，箱子，先进后出。
栈顶，栈底。存储元素到集合，压栈（入栈），出栈（弹栈）。
入栈：1、2、3 。出栈：3、2、1
2、用代码谈谈栈
实际上，栈既可以用数组来实现，也可以用链表来实现。用数组实现的栈，我们叫作顺序栈，用链表实现的栈，我们叫作链式栈。不管是顺序栈还是链式栈，我们存储数据只需要一个大小为n的数组就够了。在入栈和出栈过程中，只需要一两个临时变量存储空间，所以空间复杂度是O(1)。
注意，这里存储数据需要一个大小为n的数组，并不是说空间复杂度就是O(n)。因为，这n个空间是必须的，无法省掉。所以我们说空间复杂度的时候，是指除了原本的数据存储空间外，算法运行还需要额外的存储空间。
空间复杂度分析是不是很简单？时间复杂度也不难。不管是顺序栈还是链式栈，入栈、出栈只涉及栈顶个别数据的操作，所以时间复杂度都是O(1)。
还有一点，JVM内存管理中有个“堆栈”的概念。栈内存用来存储局部变量和方法调用，堆内存用来存储Java中的对象。那JVM里面的“栈”跟我们这里说的“栈”是不是一回事呢？如果不是，那它为什么又叫作“栈”呢？知道的大牛请自觉评论区见面~
————————————————
版权声明：本文为CSDN博主「宜春」的原创文章，遵循CC 4.0 BY-SA版权协议，转载请附上原文出处链接及本声明。
原文链接：https://blog.csdn.net/qq_44543508/article/details/100515630
》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》
2、队列
队列：queue，简称队，同堆栈一样，也是一种运算受限的线性表，限制是仅允许在表的一端进行插入，在表的另一端删除。先进先出。如同火车出洞。
存储：1、2、3 取出：1、2、3、
栈只支持两个基本操作：入栈push()和出栈pop()。队列跟栈非常相似，支持的操作也很有限，最基本的操作也是两个：入队enqueue()，放一个数据到队列尾部；出队dequeue()，从队列头部取一个元素。所以，队列跟栈一样，也是一种操作受限的线性表数据结构。队列的概念很好理解，基本操作也很容易掌握。作为一种非常基础的数据结构，队列的应用也非常广泛，特别是一些具有某些额外特性的队列，比如循环队列、阻塞队列、并发队列。它们在很多偏底层系统、框架、中间件的开发中，起着关键性的作用。比如高性能队列Disruptor、Linux环形缓存，都用到了循环并发队列；Java concurrent并发包利用ArrayBlockingQueue来实现公平锁等。
跟栈一样，队列可以用数组来实现，也可以用链表来实现。用数组实现的栈叫作顺序栈，用链表实现的栈叫作链式栈。同样，用数组实现的队列叫作顺序队列，用链表实现的队列叫作链式队列
》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》
3、数组
Array，是有序的元素序列，数组在内存中开辟一段连续的空间，并在此空间存放元素，好像一排出租屋，有100个房间，每个房间都有固定编号，通过编号可以快速找到房间。
数组支持随机访问，根据下标随机访问的时间复杂度为O(1)。
即便是排好序的数组，你用二分查找，时间复杂度也是O(logn)
平均情况时间复杂度为O(n)。
什么是数组？我估计你心中已经有了答案。不过，我还是想用专业的话来给你做下解释。数组（Array）是一种线性表数据结构。它用一组连续的内存空间，来存储一组具有相同类型的数据。这个定义里有几个关键词，理解了这几个关键词，我想你就能彻底掌握数组的概念了。下面就从我的角度分别给你“点拨”一下。
第一是线性表（Linear List）。顾名思义，线性表就是数据排成像一条线一样的结构。每个线性表上的数据最多只有前和后两个方向。其实除了数组，链表、队列、栈等也是线性表结构。而与它相对立的概念是非线性表，比如 二叉树、堆、图等。之所以叫非线性，是因为，在非线性表中，数据之间并不是简单的前后关系。
第二个是连续的内存空间和相同类型的数据。正是因为这两个限制，它才有了一个堪称“杀手锏”的特性：“随机访问”。但有利就有弊，这两个限制也让数组的很多操作变得非常低效，比如要想在数组中删除、插入一个数据，数组为了保持内存数据的连续性，会导致插入、删除这两个操作比较低效,相反的数组查询则高效
特点： 查询快，增删慢
1、 查找元素快，数组的地址是连续的，可通过数组的首地址快速找到数组，通过索引，可以快速访问指定位置的元素
2、增删慢，数组的长度是固定的
指定索引位置增加元素：需要创建一个新数组，将指定新元素存储在指定索引位置，再把原数组元素根据索引，复制到新数组对应索引的位置。
删除一个元素：创建一个新的数组，原数组的长度 - 1 ，把原数组的其他元素复制到新数组中，再把新数组地址赋值给变量array。原数组会在内存中被销毁（垃圾回收）。
数组的增加删除
关于数组，它可以说是最基础、最简单的数据结构了。数组用一块连续的内存空间，来存储相同类型的一组数据，最大的特点就是支持随机访问，但插入、删除操作也因此变得比较低效，平均情况时间复杂度为O(n)。在平时的业务开发中，我们可以直接使用编程语言提供的容器类，但是，如果是特别底层的开发，直接使用数组可能会更合适。
》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》
4、链表
在我们上一章中【从今天开始好好学数据结构02】栈与队列栈与队列底层都是采用顺序存储的这种方式的，而今天要聊的链表则是采用链式存储，链表可以说是继数组之后第二种使用得最广泛的通用数据结构了,可见其重要性！
相比数组，链表是一种稍微复杂一点的数据结构。对于初学者来说，掌握起来也要比数组稍难一些。这两个非常基础、非常常用的数据结构，我们常常将会放到一块儿来比较。所以我们先来看，这两者有什么区别。数组需要一块连续的内存空间来存储，对内存的要求比较高。而链表恰恰相反，它并不需要一块连续的内存空间，它通过“指针”将一组零散的内存块串联起来使用,链表结构五花八门，今天我重点给你介绍三种最常见的链表结构，它们分别是：单链表、双向链表和循环链表。
链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点。
linked list 由一系列结点node（链表中每一个元素称为结点）组成，结点可以在运动时动态生成，每个结点包括两部分：一个是存储数据元素的数据域（一个），另一个是存储下一个结点地址的指针域（两个，用来存储地址）。三种最常见的链表结构，它们分别是：单链表、双向链表和循环链表。
特点：查询慢，增删快。
查询慢：链表中的地址不是连续的，每次查询元素都必须从头开始查询，
增删快：链表结构增加或删除元素对链表的整体结构没有影响。
4.1 单链表
链表通过指针将一组零散的内存块串联在一起。其中，我们把内存块称为链表的“结点”。为了将所有的结点串起来，每个链表的结点除了存储数据之外，还需要记录链上的下一个结点的地址。而尾结点特殊的地方是：指针不是指向下一个结点，而是指向一个空地址NULL，表示这是链表上最后一个结点
链表要想随机访问第k个元素，就没有数组那么高效了。因为链表中的数据并非连续存储的，所以无法像数组那样，根据首地址和下标，通过寻址公式就能直接计算出对应的内存地址，而是需要根据指针一个结点一个结点地依次遍历，直到找到相应的结点。
你可以把链表想象成一个队伍，队伍中的每个人都只知道自己后面的人是谁，所以当我们希望知道排在第k位的人是谁的时候，我们就需要从第一个人开始，一个一个地往下数。
所以，链表随机访问的性能没有数组好，需要O(n)的时间复杂度。
链表
单向链表：链表中只有一条链子，不能保证元素的顺序，存储元素和取出元素顺序有可能不一致。
4.2双链表
时间复杂度O(1)
双向链表：链表中有两条链子，有一条链子专门记录元素的顺序，是一个有序的集合。
单向链表只有一个方向，结点只有一个后继指针next指向后面的结点。而双向链表，顾名思义，它支持两个方向，每个结点不止有一个后继指针next指向后面的结点，还有一个前驱指针prev指向前面的结点。
链表增删
单链表VS双向链表
如果我们希望在链表的某个指定结点前面插入一个结点或者删除操作，双向链表比单链表有很大的优势。双向链表可以在O(1)时间复杂度搞定，而单向链表需要O(n)的时间复杂度，除了插入、删除操作有优势之外，对于一个有序链表，双向链表的按值查询的效率也要比单链表高一些。因为，我们可以记录上次查找的位置p，每次查询时，根据要查找的值与p的大小关系，决定是往前还是往后查找，所以平均只需要查找一半的数据。
现在，你有没有觉得双向链表要比单链表更加高效呢？这就是为什么在实际的软件开发中，双向链表尽管比较费内存，但还是比单链表的应用更加广泛的原因。如果你熟悉Java语言，你肯定用过LinkedHashMap这个容器。如果你深入研究LinkedHashMap的实现原理，就会发现其中就用到了双向链表这种数据结构。实际上，这里有一个更加重要的知识点需要你掌握，那就是用空间换时间的设计思想。当内存空间充足的时候，如果我们更加追求代码的执行速度，我们就可以选择空间复杂度相对较高、但时间复杂度相对很低的算法或者数据结构。相反，如果内存比较紧缺，比如代码跑在手机或者单片机上，这个时候，就要反过来用时间换空间的设计思路。
最后，我们再对比一下数组，数组的缺点是大小固定，一经声明就要占用整块连续内存空间。如果声明的数组过大，系统可能没有足够的连续内存空间分配给它，导致“内存不足（out of memory）”。如果声明的数组过小，则可能出现不够用的情况。这时只能再申请一个更大的内存空间，把原数组拷贝进去，非常费时。链表本身没有大小的限制，天然地支持动态扩容，我觉得这也是它与数组最大的区别。
你可能会说，我们Java中的ArrayList容器，也可以支持动态扩容啊？事实上当我们往支持动态扩容的数组中插入一个数据时，如果数组中没有空闲空间了，就会申请一个更大的空间，将数据拷贝过去，而数据拷贝的操作是非常耗时的。
我举一个稍微极端的例子。如果我们用ArrayList存储了了1GB大小的数据，这个时候已经没有空闲空间了，当我们再插入数据的时候，ArrayList会申请一个1.5GB大小的存储空间，并且把原来那1GB的数据拷贝到新申请的空间上。听起来是不是就很耗时？
除此之外，如果你的代码对内存的使用非常苛刻，那数组就更适合你。因为链表中的每个结点都需要消耗额外的存储空间去存储一份指向下一个结点的指针，所以内存消耗会翻倍。而且，对链表进行频繁的插入、删除操作，还会导致频繁的内存申请和释放，容易造成内存碎片，如果是Java语言，就有可能会导致频繁的GC（Garbage Collection，垃圾回收）
》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》》
网友评论