底层是基于数组,(数组在内存中分配连续的内存空间)是对数组的升级,长度是动态的。java
数组默认长度是10,当添加数据超越当前数组长度时,就会进行扩容,扩容长度是以前的1.5倍,要对以前的数组对象进行复制,因此只有每次扩容时相对性能开销大一些。node
源码(jdk 1.8):git
// 1. 添加元素 public boolean add(E e) { ensureCapacityInternal(size + 1); // 每次添加元素都要对容量评估 elementData[size++] = e; return true; } // 2. 评估容量 private void ensureCapacityInternal(int minCapacity) { // 若果数组对象仍是默认的数组对象 if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) { minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity); } ensureExplicitCapacity(minCapacity); } // 3. 进一步评估是否要进行扩容 private void ensureExplicitCapacity(int minCapacity) { modCount++; // 记录ArrayList结构性变化的次数 // overflow-conscious code if (minCapacity - elementData.length > 0) grow(minCapacity); }
步骤3中
if (minCapacity - elementData.length > 0) grow(minCapacity);
当 minCapacity
大于当前数组对象长度时 才进行扩容操做,也就是执行步骤 4的代码github
// 4.复制产生新的数组对象并扩容 private void grow(int minCapacity) { // overflow-conscious code int oldCapacity = elementData.length; int newCapacity = oldCapacity + (oldCapacity >> 1); if (newCapacity - minCapacity < 0) newCapacity = minCapacity; if (newCapacity - MAX_ARRAY_SIZE > 0) newCapacity = hugeCapacity(minCapacity); // minCapacity is usually close to size, so this is a win: elementData = Arrays.copyOf(elementData, newCapacity); }
public void add(int index, E element) { // 1 rangeCheckForAdd(index); // 2 ensureCapacityInternal(size + 1); // 3 System.arraycopy(elementData, index, elementData, index + 1,size - index); // 4 elementData[index] = element; // 5 size++; }
rangeCheckForAdd(index);
评估插入元素位置是否合理数组
ensureCapacityInternal(size + 1);
检查数组容量是否有当前元素数量 size +1 个大,由于后续进行数组复制要多出一个元素安全
数组复制数据结构
System.arraycopy(elementData, index, elementData, index + 1,size - index); System.arraycopy(src, srcPos, dest, destPos , length);
src:源数组;srcPos:源数组要复制的起始位置;index 是要插入元素的位置,因此要从当前开始复制
性能
dest:目的数组; destPos:目的数组放置的起始位置;复制好的元素要放在插入位置的后面 因此 index+1
ui
length:复制的长度。包括插入位置和后面的元素 = 当前元素数 - 插入位置
this
步骤执行元素赋值
步骤元素长度+1
若是ArrayLisy集合不指定位置添加元素,默认往数组对象的后面追加,因此数组对象的其余元素位置不变,没有什么性能开销,若是元素插入到数组对象的前面,并且是越往前,从新排序的数组元素就会越多性能开销越大,固然经过上述源码介绍中看到,经过数组复制的方式排序对性能影响也不大,
// 获取指定位置元素的源码 public E get(int index) { rangeCheck(index); return elementData(index); }
直接返回当前查找位置的数组对象对应的下标位置的元素,高性能,速度很快。
ArraList 和 Vector 都是基于数组实现,它俩底层实现原理几乎相同,只是Vector是线程安全的,ArrayLsit不是线程安全的,它俩的性能也相差无几。
双向链表
表项
//1. 添加元素,不指定位置会添加到最后一个 public boolean add(E e) { linkLast(e); return true; } //2. 添加到最后一位(每次添加插入元素都会建立一个Node对象) void linkLast(E e) { final Node<E> l = last; final Node<E> newNode = new Node<>(l, e, null); // 双向链表的最后一个表项没有 后驱指针 last = newNode; if (l == null) first = newNode; else l.next = newNode; size++; modCount++; } //3. 建立表项 private static class Node<E> { E item; Node<E> next; Node<E> prev; Node(Node<E> prev, E element, Node<E> next) { this.item = element; this.next = next; this.prev = prev; } }
public void add(int index, E element) { checkPositionIndex(index); // 检查位置是否合理 if (index == size) linkLast(element); // 若是插入位置等于集合元素长度就日后追加 else linkBefore(element, node(index)); // 不然在当前位置元素前面建立新节点 } void linkBefore(E e, Node<E> succ) { // assert succ != null; // 步骤一 final Node<E> pred = succ.prev; // 步骤二 final Node<E> newNode = new Node<>(pred, e, succ); // 步骤三 succ.prev = newNode; // 步骤四 if (pred == null) first = newNode; else pred.next = newNode; size++; modCount++; }
步骤一:获取当前元素(未插入目前要插入的元素前)前指针指向的节点
步骤二:建立新节点,一个表项,前驱表项是前面的节点 步骤一获得,后驱表项指向的时当前位置的节点(未插入目前要插入的元素前)
步骤三:从新设置当前位置的节点(未插入目前要插入的元素前)的前驱指针指向的节点,也就是刚插入的建立的新节点
步骤四:是对建立新节点的前置节点的后驱表项进行修改设置
总结:对应LinkedList插入任意位置元素 咱们只需建立一个新元素节点和移动先后两个表项的指针,其余表项无需任何操做,性能高;
最后一个元素和第一个元素的位置不须要遍历整个链表获取,每一个LinkedList集合不管是否为空,都会有一个Header表项,Header表项的前驱指针始终指向最后一个元素,后驱指针指向第一个元素,因此能够说LinkedList集合中的第一个和最后一个元素位置是肯定的。
循环双向链表结构中节点位置的肯定须要根据前面的元素日后遍历查找或者后面的元素往前遍历查找
// 1. 获取指定位置元素 public E get(int index) { checkElementIndex(index); // 首先判断位置是否有效 return node(index).item; } // 2. 根据位置对节点遍历查找 Node<E> node(int index) { // assert isElementIndex(index); if (index < (size >> 1)) { // 若是下标位置在总长度中间以前,则从前日后遍历查找 Node<E> x = first; for (int i = 0; i < index; i++) x = x.next; return x; } else { // 若是下标位置在总长度中间以后,则从后往前遍历查找 Node<E> x = last; for (int i = size - 1; i > index; i--) x = x.prev; return x; } }
从上面的源码中能够看出若是LinkedList集合的长度很大,则每次查找元素都会遍历不少次,性能影响也会更大
删除任意位置的元素,是先要找到该元素,因此须要上一步提到的查找操做
public E remove(int index) { checkElementIndex(index); return unlink(node(index)); // node(index) 是查找元素 }
🍡 实现方式
ArrayList 是基于数组实现,内存中分配连续的空间,须要维护容量大小。
LinkedList 是基于循环双向链表数据结构,不须要维护容量大小。
🍪 添加插入删除元素
ArrayList不自定义位置添加元素和LinkedList性能没啥区别,ArrayList默认元素追加到数组后面,而LinkedList只须要移动指针,因此二者性能相差无几。
若是ArrayList自定义位置插入元素,越靠前,须要重写排序的元素越多,性能消耗越大,LinkedList不管插入任何位置都同样,只须要建立一个新的表项节点和移动一下指针,性能消耗很低。
频繁插入删除元素 -> 使用 LinkedList 集合
🚓 遍历查看元素
ArrayList是基于数组,因此查看任意位置元素只须要获取当前位置的下标的数组就能够,效率很高,然而LinkedList获取元素须要从最前面或者最后面遍历到当前位置元素获取,若是集合中元素不少,就会效率很低,性能消耗大。
频繁遍历查看元素 -> 使用 ArrayList 集合
🍝 ArrayList和LinkedList 都时线程不安全的