让星星⭐月亮告诉你，LinkedList和ArrayList底层数据结构及方法源码说明

本文主要是介绍让星星⭐月亮告诉你，LinkedList和ArrayList底层数据结构及方法源码说明，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

一、⭐⭐⭐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);//这个方法逻辑很简单,就是判断索引下标是否在链表长度范围内,超出范围则报IndexOutOfBoundsExceptionreturn 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);//这个方法逻辑很简单,就是判断索引下标是否在链表长度范围内,超出范围则报IndexOutOfBoundsExceptionif (index == size)linkLast(element);//若index等于size,说明要在末位增加元素,直接调用末位增加元素的指定方法linkLast(element)即可,这样可以避免走下面的逻辑,避免多绕弯儿elselinkBefore(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;elsepred.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 codeif (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 codeint 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) // overflowthrow 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 workreturn 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&nbsp;?&nbsp;get(i)==null&nbsp;:&nbsp;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;}