Day15：刀枪与弓箭

初学写程序的时候，常常会用到阵列(array)的概念，当我们想储存一堆有顺序性的值或变数时，就会把它们装进一个阵列之中，後续可以拿来跑回圈或取出需要的值出来。

由於Java有介面与物件继承的概念，当学到集合(collection)的时候，有发现新大陆的感觉(起码对我来说是这样啦)，原来把一堆东西装进某个东西的概念不只有阵列，还有这多麽其他的样式，甚至单单一个串列(List，相当於阵列array，为了和Java阵列的型别作区别)，底下还可以分支出其他实作种类的阵列，整个就像生物学的界门纲目科属种一样。今天这篇就要来谈谈2个最常见的阵列：索引阵列(ArrayList)与链结阵列(LinkedList)。

索引阵列就是大家最熟悉的那种阵列了，而它在底层的实作也就如大家最直觉的想像一样，把所有东西都标上号码(就是索引，index)，然後一个萝卜一个坑放在阵列中；我们可以根据索引(index)直接地拿出该索引代表的物件出来。不过如果我们需要调整阵列中元素的位置时，对电脑来说就是一个大工程了，因为原本的元素都站好茅坑了，假设要在中间插一个元素进来，前面的元素不打紧，但後面的可就累了，要站起来全部往後挪一个位置。因为这样的特性，所以大家常说若这个阵列不太会有写入资料的需求，比较常读取的话，就适用索引阵列(ArrayList)。

为了解决原本阵列这样改动位置就需要全部的元素跟着变动的特性，出现了链结阵列这样的东西，要了解链结阵列，先有类别型态的概念会比较能理解。
废话不多说，我们上图：

链结阵列利用变数(stack memory)存取物件(heap memory)位址值的架构，让阵列不直接存取我们想存放的物件型态本身，而是放入一个类似中介身分的节点物件(node)，而在这个节点之中，存放2个变数，1个存放我们本来想放的元素本身，1个存放下一个node物件的位址值。除了node以外，键结阵列本身也必须要有一个变数first来存放第一个node物件的位址值。

可能有人会想，搞这麽复杂在干嘛，直接放我们想放的元素有甚麽问题吗，还要搞一堆类似路牌的变数存一堆东西干嘛......

其实目的就是当我们要在阵列中间插一个元素进来时，我们不用再像ArrayList一样大风吹了！只要把目标位置前一个node的next变数更换成我们插进来的node，然後插进来的node的next再指向下一个node就搞定了！

不过LinkedList的缺点除了看起来概念复杂外(这是对初学的人来说的缺点哈哈哈)，实际上也有缺点的，大家可以想想看，如果我们要存取比如说第3个索引值所代表的元素时，该怎麽办？相较於ArrayList可以直接秒速取出，LinkedList底层运作会开始很笨的从first，一路count到目标的索引值，再取出目标元素。所以就会有这样的结论：若阵列有大量写入需求，大於读取需求时，推荐使用链结阵列。

其实上文提到的结论也和阵列的大小有关才导致这样的结果，ArrayList在创立的时候，会必须要一个预设的大小的，而若当我们存取超过这个预设大小时，底层就会再创一个更大的阵列，并开始一一把元素复制过来，消耗多余的资源；反观LinkedList，就没有存放大小的问题了。