一、LinkedList(同时实现了List< E >接口和Deque< E > implements Queue< E >接口)
1.LinkedList底层数据结构是一个双向链表(每个节点除了本身元素外,还包含了要指向的前一个节点Node< E > prev和后一个节点Node< E > next),双向链表还记录了头节点Node< E > first和尾节点Node< E > last(从JDK1.7才开始有的，之前JDK1.6里只有头节点header，头节点的前一个节点代表的是最后一个节点).
2.链表的数据结构在逻辑上是连续的,但是在物理空间上是不连续的(因此,索引下标和头元素存放的物理内存地址是不相关的,所以不能根据索引下标直接获取到元素,需要根据前后节点关系、索引值以及链表元素总个数size循环遍历才能走访到指定索引位置的元素);
3.LinkedList根据索引下标获取元素get(index)方法的具体逻辑如下:
public E get(int index) {
checkElementIndex(index);//这个方法逻辑很简单,就是判断索引下标是否在链表长度范围内,超出范围则报IndexOutOfBoundsException
return node(index).item;//重点关注这里的node(index)方法采用了优化算法,先用index与链表长度size的一半比较(index < (size>>1)),若小于则从first-index,利用Node.next去一个个从前往后循环遍历直到到达index所在位置;若大于则从last-index,利用Node.prev去一个个从后向前循环遍历直到到达index所在位置.这样可以减少一半的遍历次数,性能有所提升.之所以可以采用这种优化算法,前提是在向链表中新增元素时,size加一和更新next/prev指向会同时执行,从而使得size\first\last之间通过next/prev的逻辑串联起来,第一个索引下标元素first,那么第二个索引下标元素就是first.next,最后一个索引下标元素last,那么倒数第二个索引下标元素就是last.prev.
}
/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
//用index与链表长度size的一半比较,右移>>位运算
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;//从first开始,从前往后一个个遍历直到到达index所在位置
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;//从last开始,从后向前一个个遍历直到到达index所在位置
return x;
}
}
4.LinkedList增加元素到指定索引下标add(index,Node< E > e)方法的具体逻辑如下:
/**
* Inserts the specified element at the specified position in this list.
* Shifts the element currently at that position (if any) and any
* subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public void add(int index, E element) {
checkPositionIndex(index);//这个方法逻辑很简单,就是判断索引下标是否在链表长度范围内,超出范围则报IndexOutOfBoundsException
if (index == size)
linkLast(element);//若index等于size,说明要在末位增加元素,直接调用末位增加元素的指定方法linkLast(element)即可,这样可以避免走下面的逻辑,避免多绕弯儿
else
linkBefore(element, node(index));//该方法分两部分:(1)查到指定index所在位置的元素Node<E> succ,然后再将succ.prev指向要增加的新元素element,这样就在index位置插入了新元素.
}
/**
* Inserts element e before non-null Node succ.
*/
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++;
}
5.LinkedList在首尾增加元素时请务必直接使用addFirst(E e)和addLast(E e)方法,直接对first和last节点进行前prev后next指向的更新操作,这样可以少走一些代码逻辑,执行更快一些,removeFirst(Node< E > l)和removeLast(Node< E > l)也一样.
6.LinkedList更新指定索引位置的元素值时,原理跟增删一样,都需要先根据index循环遍历查找到index位置的节点Node< e >,然后再进行相关处理(节点前后指向的更新或节点元素值的更新)
/**
* Replaces the element at the specified position in this list with the
* specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
7.由于Linked List 也实现了Deque< E > implements Queue< E >接口,所以具有以下相关方法:
(1)add VS offer(注意:LinkedList重写的offer方法体里是直接调用的add方法)：
add()和offer()方法都可以往队列末尾增加元素。当队列已经到达最大容量后,再往里面增加元素,add() 会抛出属于非检查异常的几种RuntimeException(IllegalStateException/ClassCastException/NullPointerException/IllegalArgumentException)，而offer返回false不抛出异常。
(2)element VS peek：
element() 和 peek()方法 都可以查询队列的首位元素。当队列为空时，element()方法会抛出异常，而 peek()返回null不抛出异常。
(3)remove VS poll：
remove() 和 poll() 方法都可以从删除队列的首位元素。当队列为空时，remove()方法会抛出异常，而 poll()返回null不抛出异常。
二、ArrayList
1.ArrayList底层数据结构是基于动态数组，与普通数组相比较而言，动态数组可以实现数组长度的自动扩容。由于是底层是数组结构(Object []),且实现了RandomAccess随机存取标志接口(表明实现这个这个接口的 List 集合是支持快速随机访问的。也就是说，实现了这个接口的集合是支持 快速随机访问策略,而且如果是实现了这个接口的 List，那么使用for循环的方式获取数据会优于用迭代器获取数据【所以大家在看ArrayList源码时能观察到遍历时采用的都是for而非迭代器】，因为for里面利用的就是随机访问(根据下标快速找到指定位置的元素)这一特性);
2.所以其指定索引位置查询get(index)的操作效率就比较高，时间复杂度为O(1)；
/**
* Returns the element at the specified position in this list.
*
* @param index index of the element to return
* @return the element at the specified position in this list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E get(int index) {
rangeCheck(index);//此方法很简单,检查索引是否越界
return elementData(index);//返回数组的指定位置的元素
}
// Positional Access Operations 位置访问操作
@SuppressWarnings("unchecked")
E elementData(int index) {
return (E) elementData[index];
}
3.但其在指定位置的增add(index,E element)删remove(index)操作就性能就比较低，因为会导致后续相关数组元素的位置移动(数据复制,调用System.arraycopy(Object src, int srcPos, Object dest, int destPos, int length))),add(index,E element)可能会引发二次数组复制.
add(index,E element)
/**
* Inserts the specified element at the specified position in this
* list. Shifts the element currently at that position (if any) and
* any subsequent elements to the right (adds one to their indices).
*
* @param index index at which the specified element is to be inserted
* @param element element to be inserted
* @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++;
}
注意:当往数组add元素时,可能会引发数据扩容的相关操作,代码逻辑如下:
(1)private void ensureCapacityInternal(int minCapacity) {
ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}
(2)private static int calculateCapacity(Object[] elementData, int minCapacity) {
if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
return Math.max(DEFAULT_CAPACITY, minCapacity);
}
return minCapacity;
}
(3)private void ensureExplicitCapacity(int minCapacity) {
modCount++;
// overflow-conscious code
if (minCapacity - elementData.length > 0)
grow(minCapacity);
}
(4)
/**
* Increases the capacity to ensure that it can hold at least the
* number of elements specified by the minimum capacity argument.
*
* @param minCapacity the desired minimum capacity
*/
private void grow(int minCapacity) {
// overflow-conscious code
int oldCapacity = elementData.length;
int newCapacity = oldCapacity + (oldCapacity >> 1);//扩容为旧容量的1.5倍
if (newCapacity - minCapacity < 0)//若扩容为原容量的1.5倍后依然不满足要存的元素个数的要求(在往数组中添加集合addAll(Collection<? extends E> c)时可能会出现这种情况)
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);
}
private static int hugeCapacity(int minCapacity) {
if (minCapacity < 0) // overflow
throw new OutOfMemoryError();
return (minCapacity > MAX_ARRAY_SIZE) ?
Integer.MAX_VALUE :
MAX_ARRAY_SIZE;
}
remove(index)
/**
* Removes the element at the specified position in this list.
* Shifts any subsequent elements to the left (subtracts one from their
* indices).
*
* @param index the index of the element to be removed
* @return the element that was removed from the list
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E remove(int index) {
rangeCheck(index);
modCount++;
E oldValue = elementData(index);
int numMoved = size - index - 1;
if (numMoved > 0)//除非要删除的元素是最后一个,否则会发生数组复制
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//数组复制,将数组中原先处于(index+1,index+1+numMoved)的这段元素复制到(index,index+numMoved),相当于这段元素(索引值都减了1)都往前移动了一位.
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
4.[指定删除某个元素数据的方法remove(Object o)效率更低,因为会先去循环遍历找到元素所在索引位置,然后再去进行数组复制,多了一层循环操作];
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If the list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* <tt>i</tt> such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns <tt>true</tt> if this list
* contained the specified element (or equivalently, if this list
* changed as a result of the call).
*
* @param o element to be removed from this list, if present
* @return <tt>true</tt> if this list contained the specified element
*/
public boolean remove(Object o) {
if (o == null) {
for (int index = 0; index < size; index++)//从0开始在0-size范围内循环遍历
if (elementData[index] == null) {
//找到满足条件的元素
fastRemove(index);//开始remove处理,很大可能会引发数组复制,除非要删除的元素是最后一个
return true;
}
} else {
for (int index = 0; index < size; index++)//从0开始在0-size范围内循环遍历
if (o.equals(elementData[index])) {
//找到满足条件的元素
fastRemove(index);//开始remove处理,很大可能会引发数组复制,除非要删除的元素是最后一个
return true;
}
}
return false;
}
/*
* Private remove method that skips bounds checking and does not
* return the value removed.
*/
private void fastRemove(int index) {
modCount++;
int numMoved = size - index - 1;
if (numMoved > 0)//除非要删除的元素非最后一个,否则会发生数组复制
System.arraycopy(elementData, index+1, elementData, index,
numMoved);//数组复制,将数组中原先处于(index+1,index+1+numMoved)的这段元素复制到(index,index+numMoved),相当于这段元素(索引值都减了1)都往前移动了一位.
elementData[--size] = null; // clear to let GC do its work
}
5.而在尾部增add(E element)(不触发扩容时不移动,触发扩容的话就同在指定位置增add(int index,E element)一样,也还是会调用native的System.arraycopy方法发生数组复制)删remove(index)时不用移动。
/**
* Appends the specified element to the end of this list.
*
* @param e element to be appended to this list
* @return <tt>true</tt> (as specified by {@link Collection#add})
*/
public boolean add(E e) {
ensureCapacityInternal(size + 1); // Increments modCount!!可能会引发数据扩容,进而可能出现数组复制(元素个数超过数组目前容量值时)
elementData[size++] = e;
return true;
}
6.更新指定索引位置的元素值set(int index,E element)需要先查找到该索引下的元素(因为需要返回该旧值),然后再更新为新元素,故其效率几乎等同于查找指定索引位置元素的get(index)方法.
/**
* Replaces the element at the specified position in this list with
* the specified element.
*
* @param index index of the element to replace
* @param element element to be stored at the specified position
* @return the element previously at the specified position
* @throws IndexOutOfBoundsException {@inheritDoc}
*/
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
