Java数据结构（二）- ArrayList和LinkedList

1. ArrayList和LinkedList都实现了List接口，核心区别在于ArrayList是动态数组的数据结构，LinkedList是链表的数据结构。数组和链表的本质区别在于，数组在逻辑内存上的存储是连续的，而链表是非连续的，每一个节点通过指针指向下一个节点，数组和链表的所有性能上的不同都是由这一点造成的。

Q：数组在物理内存上的空间也是连续的吗？
A：不，进程有自己虚拟内存，通过页表和物理内存形成映射，程序并不能也不需要知道自己用的到底是物理内存的哪些部分。

2. ArrayList和LinkedList操作效率上的差别，ArrayList进行get和set操作时的效率更高，可以直接通过下标随机查找，效率为O(1)，LinkedList则需要从头结点开始不断访问下一个节点查找，效率为O(n)。LinkedList进行remove和add操作时效率更高，因为ArrayList在操作之后还需要对其它元素进行复制/移动的额外操作。

3. ArrayList的扩容机制，本质上是把当前数组复制到一个更大的数组中去，ArrayList的初始默认大小为10，每次扩容后的大小为newCapacity = oldCapacity + oldCapacity>>1; 所有新的容量为旧容量的1.5倍。而LinkedList本就是动态大小，也就没有扩容一说了。

4.ArrayList和LinkedList都不是线程安全的数据结构。ArrayList的线程不安全性主要在于add方法并不是一个原子操作。ArrayList的add方法分为两步，第一步为判断是否还有空间，如果没有了则先扩容，第二步才是加入新元素。现在如果有A和B两个线程各自想要添加一个元素，而ArrayList当前容量为9/10。假如A线程先执行完第一步发现不需要扩容，此时B线程也执行第一步发现也不需要扩容，于是B线程执行第二步将元素放入了ArrayList，这时A线程再执行第二步时数组实际上已经没有空间了，此时就会报错。LinkedList也没有任何维护线程安全的措施，同样也不是线程安全的数据结构。

Q: ArrayList有没有类似的线程安全的数据结构？
A：同样实现了List结构的Vector内部方法都用了Synchronized关键字进行修饰，是线程安全的，另外还有CopyOnWriteArraylist。COW的核心思想是，如果有多个调用者（Callers）同时要求相同的资源（如内存或者是磁盘上的数据存储），他们会共同获取相同的指针指向相同的资源，直到某个调用者视图修改资源内容时，系统才会真正复制一份专用副本（private copy）给该调用者，而其他调用者所见到的最初的资源仍然保持不变。这过程对其他的调用者都是透明的（transparently）。此做法主要的优点是如果调用者没有修改资源，就不会有副本（private copy）被创建，因此多个调用者只是读取操作时可以共享同一份资源。CopyOnWriteArraylist只有在添加的时候会加锁，而读的时候是不加锁的，如果读的时候还有其他线程在添加数据，那他依旧会读到旧数据。

Q: ArrayList有没有类似的线程安全的数据结构？有没有类似的线程安全的数据结构？
A: 有用SynchronizedList，以及ConcurrentLinkedQueue， ConcurrentLinkedQueue是用基于CAS的非阻塞队列实现的。