上篇文章讲到数组和链表的区别，但是大多数同学可能都没有认真思考。目前数据在内存里只有这两种排列方式，要不是数组，要不是链表，再复杂就是数组和链表的（例如HashMap）组合。

数据结构的数据储存方式也是上文说的，例如完美二叉树，数组和链表存储都可以实现。通常对数据进行的操作就是增删改查，但是两种存储方式上的时间和空间复杂度是有区别的。数组初始化的时候就要和操作系统（JVM）约定好多大的空间，而链表则没有这种硬性规定。那这两种存储方式具体的区别，我们可以从ArrayList（数组实现）、LinkedList（链表实现）源码来进行分析。

ArrayList源码

ArrayList源码

上图为ArrayList的构造方法源码，可以明确看出内部数据存储在elementData数组里。

LinkedList源码

LinkedList源码

上图源码可以看出LinkedList源码实现为链表。那这两个类的实现方式具体区别可以在增删操作中明确看出来。

ArrayList源码

LinkedList源码

上图为相关新增数据源码，相关子方法就一一截图了。ArrayList新增数据，先判断空间是否足够，如果不够，需要对现有数组进行扩容（新建一个数组，把老数组的数据copy过来）然后插入元素。LindedList新增数据就简单多了，新建一个链表元素挂在最后一个数据上就可以了。

删除数据原理也简单，ArrayList删除节点i，那（size-i）的剩余节点就要一一移上来，LindedList只需关联下i节点上下关系就可以了。

看到这，好像数组实现的List比较复杂一点。那读者可能忘了数组内存空间连续性的优点，我们看下get源码。

ArrayList源码

LinkedList源码

可以明显看出获取速度（时间复杂度）上，数组实现的list非常快的。数组和链表是数据在内存储存的基础，大家必须先了解这两种方式的优缺点，才能进一步快速的成长。

本文的题目还有两个java类，一个是vector，一个是CopyOnWriteArrayList。这两个都是ArrayList的线程安全升级版，但是实现方式不一样，vector用的是synchronized关键字，而CopyOnWriteArrayList用的是ReentrantLock锁来实现的。多线程及线程安全会单独进行讲解，大家目前先了解一下。