【开题瞎BB】

为什么我们需要不同的数据结构？为了优化你程序的时间复杂度。
虽然不同的数据结构都可以实现同一个功能，但是有时候效率差异会很大，理解每一种数据结构的特点，根据具体情况选择适合的DS（data structure）才是一个聪明的小伙伴应该做的事情。

链表，英语List，是一种常见的线*数据结构，初入门接触JAVA的时候大家都是从Array，既“数组”开始学习的，根本不知道list是什么，而且在学习数据结构的时候还会被教授严令禁止直接使用java里的list数据类型。当时确实对这两个概念很模糊纠缠，其实后来发现，万物本源皆为数组。

Array

对一个Array进行四个基本操作access, search, insert, delete的话：

因为数组对象的获取是通过index的，所以只要你知道下标，对任何一个对象的获取都是一步到位。因此时间复杂度为O(1).搜索一个对象所需时间和数组长度线*相关，因为需要从头开始遍历数组，平均时长为(n+1)/2，取大O为O(n).向一个数组插入数据需要把插入位之后所有的对象一个个后移，这个时间也和数组长度线*相关，平均时长也是(n+1)/2，取大O为O(n).

删除一个数组数据需要把删除位之后所有的对象一个个前移，同上，时间复杂度也为O(n)

ArraySingly Linked List

单链表也是一组有序数据，每一个结点node按照顺序串联起来，虽然Array也是某种意义有序的，但那是数学意义上的有序，因为你知道[3]是[2]后一位，但每一个元素之间并没有指针/明文指示表示它“后面”接的是谁。

单链表的结构则不一样，

singly linked list

单链表的每一个结点都有一个明确指针指向下一个结点，是靠这样的方式串联起来的，所以没有index，而且单链表没有指向前一位的指针，所以无法从当前结点往回退。

对一个单链表进行四个基本操作access, search, insert, delete的话：

因为没有下标，想要获取一个node必须从表头开始遍历，时间和长度线*相关，写作O(n)搜索一个对象和获取一个对象基本一致了，也是从表头开始遍历，时间复杂度O(n)插入一个节点就很简单了，你只用“剪断”一条指针，把新节点插进去，设置新节点指针指向切断处后面的节点，再把你切断的指针指向你插进去的这个节点即可。这里说“剪断”，其实就是重写，所以只用两步。不管你的链表有多长，你在哪一位置插入节点所需要的时间都是一样的，和n无关，因此时间复杂度O(1)
【注意，本文语境下的插入和删除是指你已经停留在你要插入的位置了！如果你只有头指针，那你还当然需要先顺序遍历到你想插入的地方再执行插入操作，这种语境除非你是在头部插入（仍然是O(1)），不然其他位置的插入与删除的时间复杂显然就都是O(n)了！所以请注意语境！】
插入节点删除节点的步骤和插入一样，只不过反过来，时间复杂度也为O(1)Doubly Linked List

双向列表是单链表的变体，加上了一个指向前一节点的指针。

单链表与双向链表
虽然对于基本四项操作来说时间复杂度是完全没有区别的，而且在空间占用上还更大(多了一个存放向前指针的需要)，但它解决了单链表无法倒序的缺陷，在一些特定场景下很有用（其实就是在你需要倒序搜索的时候有用）。堆栈和队列

堆栈，就是往一个细口瓶子里放核桃，一个个放进去一个个反向倒出来，压箱底的只有你倒完其他所有核桃它才能被倒出来；
队列，就是往一个双通的管子里放核桃，放一个进去下面掉一个出来，先进去的先出来，不能后退。

一般来讲这俩都是用链表实现的，甚至我们可以说链表的存在就是为了构造堆栈和队列，因此四项基本操作时间复杂度和链表完全一样，它们可以说并不是优化时间复杂度的数据结构，而是提供特定约束条件的数据结构。

选课排队系统，你要按先来后到的顺序分配空位子，这时候用队列；手算十进制转二进制一般都是连续短除法，再倒着写出所有余数，这个时候你想写一个计算小程序就可以用堆栈；【总结】Array下标索引大法好但是你得知道你有多少个对象要放进去先给个size，Array要你先分配数组大小是因为数组在内存里是一个连续的空间，你每次通过下标索引得到对象们它们是紧密的排在一起的！list遍历查询贼麻烦，但是你可以头尾任意加对象，因为List的每个node虽然是有序的，但在内存空间是东一块西一块以node为一个单元进行（某种意义上的随机）储存的，因此才需要指针，没指针我怎么知道去哪个内存地址找下一个数据呢，在内存里紧挨着当前node的下一位朋友可能是一个完全无关的string或者鬼知道什么东西！