arrayList和linkedList的相同点
- 都是最终继承于 抽象类 abstractList,anstractCollection,接口 list
arrayList和linkedList的不同点
父类稍加不同
arraylist <--- abstractLIst < --- collection
linkedList <--- abstractSquentialList < ---abstractList <--- collection底层数据存储不同
arrayList是以数组储存数据的
linkedList是以循环双向链表存储数据的
- 内部结构不同
- 添加元素
1、添加尾部元素
arraylist:
从源码中可以看出 只要add 都会走这个方法，arryalist的add的性能取决于ensureCapacityInternal方法。*/ public boolean add(E e) { ensureCapacityInternal(size + 1); // Increments modCount!! elementData[size++] = e; return true; }
如果当前容量足够，则添加到数组末尾（add效率特别高），如果当前容量不足，则就需进行扩容，扩容过程中会进行大量的复制操作，每次扩容都会扩到当前的1.5倍
linkedList:
* @return {@code true} (as specified by {@link Collection#add})
*/
public boolean add(E e) {
linkLast(e);
return true;
}
/**
而linkedlist因为使用了链表结构，因此不需要维护容量大小
总结：linkedList 使用了链表，不需要扩容，所以不存在添加数据是还要存在扩容是否复制数据的问题，所以性能存在优势，但是正因为是链表，所以每次添加都需创建一个entry对象，对性能有一定的影响
2、任意位置添加元素
arrayList:
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacityInternal(size + 1); // Increments modCount!!
System.arraycopy(elementData, index, elementData, index + 1,
size - index);
elementData[index] = element;
size++;
}
arrayList是基于数组实现的，所以每次在一个位置添加元素之后，之后的数据都会往后移动一个位置（需要重新排列），添加的元素越往前，消耗越大（重新排列的数据越多）；
linkedList：
因为linkedList是链表结构，中间添加元素和尾部添加元素的开销是一样的
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
/**
删除元素
arrayList:
arrayList的删除元素和添加元素是雷同的，如果在中间删除元素之后，后面的元素都会向前移动位置，如果在末尾，就不存在；
linkedList:
linkedList的删除元素很快，但是查找元素位置很低效（如果要删除位置处于list的前半段，则从前往后找，如果其位置处于后半段，则从后往前找，如果数据量不大，会很高效，如果数据量很大，且数据如果在中间的话 几乎遍历了半个list，效率很低）修改元素
对于set修改元素，arrayList的效率要高于linkedList，因为linkedList要一种指针查找元素
对于get查找元素，arrayList的效率要高于linkedList，因为linkedList要一种指针扩容机制
因为arrayList是内部基于数组的，所以初始化设置一个合理的大小对性能有很大的提升
eg:现以构造一个拥有100万元素的List为例，当使用默认初始化大小时，其消耗的相对时间为125ms左右，当直接制定数组大小为100万时，构造相同的ArrayList仅相对耗时16ms。-
遍历列表
jdk 1.5之后 都有三种遍历
偷个图展示哈把
image.png 总结
ArrayList和LinkedList在性能上各 有优缺点，都有各自所适用的地方，总的说来可以描述如下：
1．对ArrayList和LinkedList而言，在列表末尾增加一个元素所花的开销都是固定的。对 ArrayList而言，主要是在内部数组中增加一项，指向所添加的元素，偶尔可能会导致对数组重新进行分配；而对LinkedList而言，这个开销是 统一的，分配一个内部Entry对象。
2．在ArrayList的 中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。
3．LinkedList不 支持高效的随机元素访问。
4．ArrayList的空 间浪费主要体现在在list列表的结尾预留一定的容量空间，而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间
可以这样说：当操作是在一列 数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中 间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了。
所以，如果只是查找特定位置的元素或只在集合的末端增加、移除元素，那么使用Vector或ArrayList都可以。如果是对其它指定位置的插入、删除操作，最好选择LinkedList
