本文详细分析了ArrayList和LinkedList在Java中的实现原理，包括它们的Add、Get、Remove方法，以及扩容和线程安全方面的区别。ArrayList基于动态数组，适合随机访问，扩容时会创建新数组；LinkedList基于链表，适合频繁的增删操作，不存在扩容问题。此外，文章还探讨了ArrayList在循环删除时可能出现的问题以及Arrays.sort的排序方法。
Table of Contents
问题：ArrayList和LinkedList有什么区别，它们是怎么扩容的？
问题：Array和ArrayList有何区别？什么时候更适合用Array？
本篇分析基于jdk1.8。
数组与链表的基本知识在这里不作展开，属于数据结构与算法的重点内容。
ArrayList
ArrayList是一个容器，容器是用来存储对象的，ArrayList当中存储对象的变量是elementData，elementData的定义如下：
/**
* The array buffer into which the elements of the ArrayList are stored.
* The capacity of the ArrayList is the length of this array buffer. Any
* empty ArrayList with elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
* will be expanded to DEFAULT_CAPACITY when the first element is added.
*/
transient Object[] elementData; // non-private to simplify nested class access
非常简单，就是一个对象数组而已。注意，它使用了transient关键字来修饰，这意味着ArrayList不会被序列化。
直接上几个ArrayList里的方法。
Add 方法
/**
* 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;
}忽略返回值做了两件事情。
- 确保当前数组的容量
- 将需要添加的元素，也就是这里的e加到数组的末尾。size当前数组的大小，size＋＋自然就是当前数组的后一位。
其他值得注意的是，此方法并没有做任何同步处理。并且，事实上整个Arraylist里的所有方法都没有做任何同步处理。因此这些涉及数据操作的方法都不是线程安全的。
Get方法
/**
* 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);
}做了两件事情
- 检测传入的参数，即数组的下标，是否越界
- 若通过检测，则返回对应位置的元素即可，因为数组是有序排列的。
remove方法
/**
* 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++)
if (elementData[index] == null) {
fastRemove(index);
return true;
}
} else {
for (int index = 0; index < size; index++)
if (o.equals(elementData[index])) {
fastRemove(index);
return true;
}
}
return false;
}
这个实现很有意思的是它判断了一下要删除的对象是否是null，为什么要做这个判断呢，因为他们判断对象是否相等的方法不一样。null直接用两个等号判断，而非null对象，则是用equals方法判断相等。
遍历数组，找到相等对象，确定下标，然后删除当前数组中该下标的元素。删除方法为fastRemove，实现如下
/*
* 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);
elementData[--size] = null; // clear to let GC do its work
}
由于是删除，所以不需要做越界检查。结构变化数modCount加一，计算需要移动的数据元素，为当前数组大小，减去删除元素位置，再减去1，为什么要减去1因为数组下标从0开始，很好理解，做个草图如下：
当前数组元素一共9个，然后假设我要删除的是第6个元素。即size＝9，index＝5（从0开始）。要删除的元素是6，需要移动的元素即为7，4，8一共三个。
size－index－1 = 9 － 5 －1 ＝ 3.
计算正确，一个测试用例诞生～。
然后将五个参数传入了System类下的arraycopy方法。这个方法的作用就是根据需要移动的元素，重新构造一个没有要删除元素的新数组，也即实现了删除的功能。这里额外插一句，从clean code的角度来讲，这个方法的参数已经太多了，clean code的建议是三个最多，只能说凡事无绝对吧。或者也可以说jdk的代码也并非从各个角度来看都完美无缺。
方法arraycopy在System类看不到实现，它是一个native方法。java众多的底层方法，实现几乎都是native方法，也就是用别的语言实现的。作为一个现代的程序员，或者说作为一个流水线上的程序员，大多数人真的一辈子也许也不需要知道这个方法到底如何实现的。
Vector
那么，如果要使用线程安全的容器，应该使用哪一个呢。答案就是Vector。
Vector的add方法如下：
/**
* Appends the specified element to the end of this Vector.
*
* @param e element to be appended to this Vector
* @return {@code true} (as specified by {@link Collection#add})
* @since 1.2
*/
public synchronized boolean add(E e) {
modCount++;
ensureCapacityHelper(elementCount + 1);
elementData[elementCount++] = e;
return true;
}用了synchronized直接修饰这个方法。除此之外实现逻辑和ArrayList几乎一样。modCount从注释来看这个变量代表的是这个容器的结构变化次数，所谓结构变化很好理解，就是数组中元素增加了一个，减少了一个，就是结构的变化。这里把modCount放在这里做计算，是一个和ArrayList不一样的地方，ArrayList是在check的时候来做。但这仅仅是代码风格的不统一。
Vector的get方法如下：
/**
* Returns the element at the specified position in this Vector.
*
* @param index index of the element to return
* @return object at the specified index
* @throws ArrayIndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index >= size()})
* @since 1.2
*/
public synchronized E get(int index) {
if (index >= elementCount)
throw new ArrayIndexOutOfBoundsException(index);
return elementData(index);
}也是用sychronized修饰了这个方法，然后先检查是否越界，不越界则返回，但是它没有像ArrayList一样将这个check提出一个方法，不太明白为何jdk的两个关联性非常强的类还会存在实现方法不一样，代码风格不一致的问题，虽然从功能上讲没有任何区别。与ArrayList基本一样。
Vector的remove方法如下：
/**
* Removes the first (lowest-indexed) occurrence of the argument
* from this vector. If the object is found in this vector, each
* component in the vector with an index greater or equal to the
* object's index is shifted downward to have an index one smaller
* than the value it had previously.
*
* <p>This method is identical in functionality to the
* {@link #remove(Object)} method (which is part of the
* {@link List} interface).
*
* @param obj the component to be removed
* @return {@code true} if the argument was a component of this
* vector; {@code false} otherwise.
*/
public synchronized boolean removeElement(Object obj) {
modCount++;
int i = indexOf(obj);
if (i >= 0) {
removeElementAt(i);
return true;
}
return false;
}indexOf方法实现如下：
/**
* Returns the index of the first occurrence of the specified element in
* this vector, searching forwards from {@code index}, or returns -1 if
* the element is not found.
* More formally, returns the lowest index {@code i} such that
* <tt>(i >= index && (o==null ? get(i)==null : o.equals(get(i))))</tt>,
* or -1 if there is no such index.
*
* @param o element to search for
* @param index index to start searching from
* @return the index of the first occurrence of the element in
* this vector at position {@code index} or later in the vector;
* {@code -1} if the element is not found.
* @throws IndexOutOfBoundsException if the specified index is negative
* @see Object#equals(Object)
*/
public synchronized int indexOf(Object o, int index) {
if (o == null) {
for (int i = index ; i < elementCount ; i++)
if (elementData[i]==null)
return i;
} else {
for (int i = index ; i < elementCount ; i++)
if (o.equals(elementData[i]))
return i;
}
return -1;
}removeElementAt方法实现如下：
/**
* Deletes the component at the specified index. Each component in
* this vector with an index greater or equal to the specified
* {@code index} is shifted downward to have an index one
* smaller than the value it had previously. The size of this vector
* is decreased by {@code 1}.
*
* <p>The index must be a value greater than or equal to {@code 0}
* and less than the current size of the vector.
*
* <p>This method is identical in functionality to the {@link #remove(int)}
* method (which is part of the {@link List} interface). Note that the
* {@code remove} method returns the old value that was stored at the
* specified position.
*
* @param index the index of the object to remove
* @throws ArrayIndexOutOfBoundsException if the index is out of range
* ({@code index < 0 || index >= size()})
*/
public synchronized void removeElementAt(int index) {
modCount++;
if (index >= elementCount) {
throw new ArrayIndexOutOfBoundsException(index + " >= " +
elementCount);
}
else if (index < 0) {
throw new ArrayIndexOutOfBoundsException(index);
}
int j = elementCount - index - 1;
if (j > 0) {
System.arraycopy(elementData, index + 1, elementData, index, j);
}
elementCount--;
elementData[elementCount] = null; /* to let gc do its work */
}实现原理很简单，根据要删除的对象找到它的下标i，然后根据这个下标删除第i个元素即可。除了加上了锁，以及一些代码风格的，与ArrayList没有区别。
其他的方法不作仔细分析，到这里可以明确的是，对于Arraylist与Vector最常用的方法，以及其实现原理，以及他们之间的差异，都已经非常清楚了。
ArrayList在循环过程中删除，会不会出问题，为什么?
根据ArrayList循环的方式和删除元素的方式，可能会出现各种各样的问题：
public static void main(String[] args) {
List<String> list = new ArrayList<>(Arrays.asList("a1", "ab2", "a3", "ab4", "a5", "ab6", "a7", "ab8", "a9"));
// 迭代删除方式一：报错 java.util.ConcurrentModificationException
for (String str : list) {
System.out.println(str);
if (str.contains("b")) {
list.remove(str);
}
}
// 迭代删除方式二
/*
报错：下标越界 java.lang.IndexOutOfBoundsException
list移除了元素但size大小未响应变化,所以导致数组下标不对；
list.remove(i)必须size--
而且取出的数据的索引也不准确，同时需要做i--操作
*/
int size = list.size();
for (int i = 0; i < size; i++) {
String str = list.get(i);
System.out.println(str);
if (str.contains("b")) {
list.remove(i);
// size--;
// i--;
}
}
// 迭代删除方式三:正常删除，不推荐；每次循环都需要计算list的大小，效率低
for (int i = 0; i < list.size(); i++) {
String str = list.get(i);
System.out.println(str);
if (str.contains("b")) {
list.remove(i);
}
}
// 迭代删除方式四:正常删除，推荐使用
for (Iterator<String> ite = list.iterator(); ite.hasNext(); ) {
String str = ite.next();
System.out.println(str);
if (str.contains("b")) {
ite.remove();
}
}
// 迭代删除方式五:报错- java.util.ConcurrentModificationException
for (Iterator<String> ite = list.iterator(); ite.hasNext(); ) {
String str = ite.next();
if (str.contains("b")) {
list.remove(str);
}
}
}ArrayList的内部实现了一个迭代器：
private class Itr implements Iterator<E> {
int cursor; // index of next element to return
int lastRet = -1; // index of last element returned; -1 if no such
int expectedModCount = modCount;
public boolean hasNext() {
return cursor != size;
}
@SuppressWarnings("unchecked")
public E next() {
checkForComodification();
int i = cursor;
if (i >= size)
throw new NoSuchElementException();
Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length)
throw new ConcurrentModificationException();
cursor = i + 1;
return (E) elementData[lastRet = i];
}
public void remove() {
if (lastRet < 0)
throw new IllegalStateException();
checkForComodification();
try {
ArrayList.this.remove(lastRet);
cursor = lastRet;
lastRet = -1;
expectedModCount = modCount;
} catch (IndexOutOfBoundsException ex) {
throw new ConcurrentModificationException();
}
}
@Override
@SuppressWarnings("unchecked")
public void forEachRemaining(Consumer<? super E> consumer) {
Objects.requireNonNull(consumer);
final int size = ArrayList.this.size;
int i = cursor;
if (i >= size) {
return;
}
final Object[] elementData = ArrayList.this.elementData;
if (i >= elementData.length) {
throw new ConcurrentModificationException();
}
while (i != size && modCount == expectedModCount) {
consumer.accept((E) elementData[i++]);
}
// update once at end of iteration to reduce heap write traffic
cursor = i;
lastRet = i - 1;
checkForComodification();
}
final void checkForComodification() {
if (modCount != expectedModCount)
throw new ConcurrentModificationException();
}
}这个迭代器在里面定义了一个 int expectedModCount = modCount;
即记录当前arraylist对象修改的次数。而从前面remove方法的分析我们看到，在每次remove方法的调用过程中，modCount这个成员变量是会自增长的，但是remove方法里面并不会更新。而我们可以看待迭代器里的next方法的第一步就是调用方法checkForComodification， 去判断这两个count是否相等，不相等就抛出异常。而在remove元素之后此处的modCount已经比expectedModCount大1了，因此会抛出一个ConcurrentModificationException。
因此在使用For-Each快速遍历时，ArrayList内部创建了一个内部迭代器iterator，使用的是hasNext和next()方法来判断和取下一个元素。就可能会出现问题。如何避免这个问题呢？最好的办法就是拿到这个迭代器，即上面代码当中的方法四。
LinkedList
LinskedList作为一个容器，用的是一个链表来存储对象，链表的结点用对象Node来进行抽象，同时定义了头节点和尾节点:
/**
* Pointer to first node.
* Invariant: (first == null && last == null) ||
* (first.prev == null && first.item != null)
*/
transient Node<E> first;
/**
* Pointer to last node.
* Invariant: (first == null && last == null) ||
* (last.next == null && last.item != null)
*/
transient Node<E> last;通过定义头节点和尾节点可以方便再某些时候的一些计算.
Node类的定义如下:
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;
}
}Item属性用于存储节点的对象，同时每个节点类有两个成员变量，next和prev分别指向当前节点的后一个结点和前一个结点。
从上面的信息已经可以判断出jdk的linkedlist采用的是有头尾节点的单链表的设计方式。
LinkedList的get方法实现原理
定义如下：
/**
* 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) {
checkElementIndex(index);
return node(index).item;
}注释已经说的很清楚了，返回list里面指定位置的element。
node(index)方法实现如下：
/**
* Returns the (non-null) Node at the specified element index.
*/
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;
}
}size>>1 即计算size的一半是多少。思想是判断index是否比size的一半小，若是则从前往后找，若不是则从后往前找。
找的方法并不可能逃出链表本身的特性。只能通过前后节点一个一个找。
LinkedList的size方法实现原理
transient int size = 0;
public int size() {
return size;
}size定义成了一个成员变量,每次链表元素增加时它就加一。
LinkedList的add方法实现原理
transient Node<E> last;
public boolean add(E e) {
linkLast(e);
return true;
}
/**
* Links e as last element.
*/
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++;
}代码很简单，添加元素默认是添加在最好，由于linkedlist用一个成员变量来表示当前最后一个元素，因此效率上也非常高。
LinkedList的remove方法实现原理
/**
* Removes the first occurrence of the specified element from this list,
* if it is present. If this list does not contain the element, it is
* unchanged. More formally, removes the element with the lowest index
* {@code i} such that
* <tt>(o==null ? get(i)==null : o.equals(get(i)))</tt>
* (if such an element exists). Returns {@code true} 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 {@code true} if this list contained the specified element
*/
public boolean remove(Object o) {
if (o == null) {
for (Node<E> x = first; x != null; x = x.next) {
if (x.item == null) {
unlink(x);
return true;
}
}
} else {
for (Node<E> x = first; x != null; x = x.next) {
if (o.equals(x.item)) {
unlink(x);
return true;
}
}
}
return false;
}注释已经说明了，删除第一个匹配的元素，如果没有匹配的元素，list不会发生改变。
很有意思的是，null对象是可以存储也可以删除的，并且判断null元素用的是==，而是一般的对象元素则是用的equals方法。
删除的方法unlink实现如下
/**
* Unlinks non-null node x.
*/
E unlink(Node<E> x) {
// assert x != null;
final E element = x.item;
final Node<E> next = x.next;
final Node<E> prev = x.prev;
if (prev == null) {
first = next;
} else {
prev.next = next;
x.prev = null;
}
if (next == null) {
last = prev;
} else {
next.prev = prev;
x.next = null;
}
x.item = null;
size--;
modCount++;
return element;
}实现思想如下图：
删除后
问题：ArrayList和LinkedList有什么区别，它们是怎么扩容的？
事实上就是数组和链表作为两种最核心的数据结构的区别。
1.ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
2.对于随机访问get和set，ArrayList觉得优于LinkedList，因为LinkedList要移动指针。
3.对于新增和删除操作add和remove，LinedList比较占优势，因为ArrayList要移动数据
因此LinkedList不存在扩容的问题。其元素节点定义如下：
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;
}
}对于ArrayList来说，存在扩容的问题。在添加元素时我们从第一节的代码可以知道它会先确保容量是否足够，如果不够则会扩容，实现方法如下：
/**
* 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);
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);
}这个方法大概的意思就是根据现有的元素，和计算出的新的capacity，然后生成一个新的数组，生成新数组的方法最后是System类的arraycopy方法，这是一个native方法。
问题:Arrays.sort的排序方法是什么？
数组的操作可以使用java提供的工具类Arrays，其中Arrays.sort()方法用于数组的排序。
基本数据类型数组的操作，使用经过优化的快速排序算法
当数组的规模较小时，直接插入排序的比较次数并不会比快排或者归并多多少，其效率反而不如简单排序算法，所以在数组规模小于7时，使用直接插入排序，
当数组规模较大时，合理的选择快排的枢轴元素，如在规模小于40时，在数组的首，中，尾三个位置上的数，取中间大小的数做枢轴；在数组规模大于40时，从数组中取位置均匀分布的9个数，然后每三个数一组取中间数，最后三个中间数再取中间数。确定枢轴后，与数组的第一个元素交换，之后的快排与普通快排一样。
当数组中有大量重复元素时，选择重复元素作为枢轴，然后两个端各设置两个工作指针low、high，left、right用于始终指向要交换的元素位置，如5，2，5，6，4，3，5，1，5，7
从high开始判断，low <= high，若high位置的元素 >= 基准元素high–，同时若high位置的元素 == 基准元素，high位置的元素与right位置的元素交换，同时right–，继续直到high位置的元素 < 基准元素。
从low开始判断，low <= high，若low位置的元素 <= 基准元素low++，同时若low位置的元素 = 基准元素，low位置的元素与left位置的元素交换，同时left++，继续直到low位置的元素 > 基准元素。
low、high位置的元素交换，同时low++、high–，然后再从high开始继续上面的过程，最后将重复的元素至于序列的两端，中间的序列分成了两部分，左面的为小于基准元素的，右面的为大于基准元素的，如5，5，2，1，4，3，7，6，5，5，此时low在7位置，high在3位置。
将两端重复的元素都交换到中间后，对两端不等的元素使用快排，左侧外循环从下标0开始判断，若等于枢轴进入内循环，内循环从下标low - 1开始向前找不等于枢轴的，找到交换，直到外循环遇到不等于枢轴的退出；右侧外循环从下标n - 1开始判断，若等于枢轴进入内循环，内循环从下标high + 1开始向后找不等于枢轴的，找到交换，直到外循环遇到不等于枢轴的退出。
引用数据类型数组的排序，使用经过优化的归并排序算法。
当数组规模j较小时，使用直接插入排序。
当属组规模较大时，使用归并排序，且当合并的两个有序序列中，低子序列的最高元素小于高子序列的最低元素时，无序执行合并算法，这个可以在merge算法里判断。
问题：Array和ArrayList有何区别？什么时候更适合用Array？
Array可以容纳基本类型和对象，而ArrayList只能容纳对象。
Array是指定大小的，而ArrayList大小是固定的。
Array没有提供ArrayList那么多功能，比如addAll、removeAll和iterator等。尽管ArrayList明显是更好的选择，但也有些时候Array比较好用。
（1）如果列表的大小已经指定，大部分情况下是存储和遍历它们。
（2）对于遍历基本数据类型，尽管Collections使用自动装箱来减轻编码任务，在指定大小的基本类型的列表上工作也会变得很慢。
（3）如果你要使用多维数组，使用[][]比List
扫一扫
1249
被折叠的 条评论
为什么被折叠?
到【灌水乐园】发言
