Java集合框架源码解析之数组与链表
本系列文章会陆续对 Java 集合框架（Java Collections Framework，JDK1.8）中的几个常用容器结合源码进行介绍，帮助读者建立起对 Java 集合框架清晰而深入的理解，也算是对自己所学内容的一个总结归纳
因为数组与链表是 Java 集合框架中很多地方都涉及到的知识点，此篇文章作为开头，就先对数组与链表这两种数据结构进行介绍
数组与链表是两种差别较大的数据结构，在内存空间上的存储方式也有很大区别
数组
假设现在有6个元素存放在数组中，则数组在内存中的存储结构就如下图所示
- 数组是一块连续的内存空间，包含的元素按照坐标索引依次排列，可以直接通过坐标定位到每一个数据的内存地址，例如可以直接通过坐标 3 获取到 element4，省去了链表中的遍历过程，因此随机读取数据的效率较高
- 相对应的，由于要求数组中的元素是连续的，在添加数据或移除数据时，有可能会导致大量数据在内存中的前后移动，因此数组在添加和移除数据时效率较低
- 数组在使用前需要先指定其空间大小，如果我们在使用前已知待存入的数据量，自然可以直接以此进行初始化而不会浪费内存空间，但实际数据量往往是未知的，通常会因为申请了较大的内存空间导致浪费或者是申请少了导致数据无法存放，而数组在声明空间大小后是无法再次修改的
在 ArrayList 与 HashMap 等容器类中，其底层实际用来存放数据的结构都是数组
链表
假设现在有4个元素依靠链表来存放，则链表在内存中的存储结构就如下所示
- 图中所展示的是一个双向链表，即每个结点除了要包含实际的数据外，还需要两个引用分别用于指向上一个结点（prev）和下一个结点（next），此外还需要有两个引用分别指向头结点（first）和尾结点（last），方便进行正向遍历和反向遍历
- 链表不要求有连续的内存空间，新添加的结点可以在内存中的任何位置，只要上一个结点保存有下一个结点的引用即可
- 由于链表的内存空间不是连续的，因为在随机访问数据时只能选择遍历整个链表，在最坏的情况下需要遍历整个链表。当然，可以根据实际情况来选择是正向遍历还是反向遍历，以此提高访问效率
- 在添加或移除元素时，只需要修改相邻结点对指定结点的引用即可，而不需像数组那样需要移动元素，因此链表在添加和移除元素时的效率较高
- 链表不需事先申请内存空间，根据实际使用情况可以进行动态申请
在 HashMap 中，其底层在存放数据时就使用到了链表
