Java.util.ArrayList跟LinkedList的区

常用集合类的继承结构如下：

Collection<--List<--Vector 底层是数组
Collection<--List<--Vector <--Stack（就是调用vector的方法，线程安全）
Collection<--List<--ArrayList 底层是数组
Collection<--List<--LinkedList 底层有node类存储了父节点和子节点
Collection<--Set<--HashSet 底层是HashMap，且只使用HashMap的key
Collection<--Set<--HashSet<--LinkedHashSet
Collection<--Set<--SortedSet<--TreeSet
Map<--SortedMap<--TreeMap
Map<--HashMap

ArrayList与LinkedList区别：

1. ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2. 对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3. 对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据。
4. Vector是线程同步的(sychronized)的，这也是Vector和ArrayList（不同步） 的一个的重要区别。

ArrayList实现：

1. ArrayList底层基于Object类型的数组实现，初始大小为10。使用modCount实现快速失败，非同步。
2. ArrayList如果构造函数不传入初始大小，则object类型数组先赋值为一个空数组，在add方法时才真正构造（使用Arrays.copyOf方法）。如果传入初始大小，则直接new初始大小的数组。
3. ArrayList删除，使用system.arraycopy，把原数组index+1往后的数据，复制到原数组从开始index的位置，并把最后一个元素赋为null。

LinkedList实现：

1. LinkedList是双向链表，node节点里有next和prev指针以及自身的值，在LinkedList中有First和Last两个节点，用于指向链表的头和尾，如果调用add()方法，直接在Last节点后面添加，并把Last赋为新加的结点。
2. 在之前版本的jdk中，只有一个header指针，header的next即为头节点，header的prev即为尾节点，header本身值为空。环形的。