数组和链表在编程语言中的应用

ArrayList

ArrayList是一个动态数组，也是我们最常用的集合。

ArrayList 把很多数组操作的细节封装了起来，包括上一篇提到的插入、删除时迁移数据等。

ArrayList 还有一个优势就是支持动态扩容。

我们都知道数组在定义的时候是需要指定大小的，以便于分配连续的内存空间。

如果定义的时候是申请了20的数组，那么存储第21个数据时，就要重新分配一块更大的内存空间，将原来的数据复制过去，然后将新的数据插入。

ArrayList 底层已经实现扩容逻辑，每次存储空间不足的时候，都会自动扩容1.5倍大小。

扩容操作涉及内存申请和数据迁移，如果能事先确定存储数据的大小，最好在创建ArrayList的时候指定数据的大小。

ArrayList 支持根据下标进行随机查询，时间复杂度为O(1)。

LinkedList

LinkedList是一个双向链表，不支下标随机查询。

所有的操作都是要按照双向链表的需要执行。

在列表中索引的操作将从开头或结尾遍历列表（从靠近指定索引的一端）。

这样做的好处就是可以通过较低的代价在List中进行插入和删除操作。

ArrayList与LinkedList的区别和适用场景

Arraylist：

优点：ArrayList是实现了基于动态数组的数据结构，因为地址连续，一旦数据存储好了，查询操作效率会比较高（在内存里是连着放的）。

缺点：因为地址连续， ArrayList要移动数据,所以插入和删除操作效率比较低。

LinkedList：

优点：LinkedList基于链表的数据结构，地址是任意的，所以在开辟内存空间的时候不需要等一个连续的地址，对于新增和删除操作add和remove，LinkedList比较占优势。LinkedList 适用于要头尾操作或插入指定位置的场景。

缺点：因为LinkedList要移动指针，所以查询操作性能比较低。

适用场景分析：

当需要对数据进行对此访问的情况下选用ArrayList，当需要对数据进行多次增加删除修改时采用LinkedList。