ArrayList、Vector和LinkedList区别浅谈

ArrayList、Vector和LinkedList区别浅谈

ArrayList、Vector和LinkedList区别浅谈

这是一个老生常谈的问题了，现在尝试从阅读源码的方式解释。

源码阅读

从初始化、数据容器、放入数据和获取数据这几个方面的源码

ArrayList

private static final int DEFAULT_CAPACITY = 10;
...
transient Object[] elementData;
...
/*** Constructs an empty list with the specified initial capacity.** @param  initialCapacity  the initial capacity of the list* @throws IllegalArgumentException if the specified initial capacity*         is negative*/public ArrayList(int initialCapacity) {if (initialCapacity > 0) {this.elementData = new Object[initialCapacity];} else if (initialCapacity == 0) {this.elementData = EMPTY_ELEMENTDATA;} else {throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);}}/*** Constructs an empty list with an initial capacity of ten.*/public ArrayList() {this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;}/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.** @param c the collection whose elements are to be placed into this list* @throws NullPointerException if the specified collection is null*/public ArrayList(Collection<? extends E> c) {elementData = c.toArray();if ((size = elementData.length) != 0) {// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, size, Object[].class);} else {// replace with empty array.this.elementData = EMPTY_ELEMENTDATA;}}...
public E get(int index) {rangeCheck(index);return elementData(index);
}
...
public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;
}

分析：

1. 从源码中看出ArrayList的底层结构是数组Object[]，默认的容量是DEFAULT_CAPACITY=10。
2. 其构造器也是可以指定容器大小的。
3. 获取数据是通过索引获取的，获取之前会检查索引是否超出数组大小
4. 放入数据之前会检查容量大小，如果超了会进行扩容

LinkedList

/*** 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;
...
/*** Constructs an empty list.*/
public LinkedList() {
}/*** Constructs a list containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.** @param  c the collection whose elements are to be placed into this list* @throws NullPointerException if the specified collection is null*/
public LinkedList(Collection<? extends E> c) {this();addAll(c);
}
...
/**
* Inserts the specified element at the beginning of this list.
*
* @param e the element to add
*/
public void addFirst(E e) {linkFirst(e);
}/**
* Appends the specified element to the end of this list.
*
* <p>This method is equivalent to {@link #add}.
*
* @param e the element to add
*/
public void addLast(E e) {linkLast(e);
}
...
public boolean add(E e) {linkLast(e);return true;
}
...
public E get(int index) {checkElementIndex(index);return node(index).item;}
...
/**
* 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;
}
...
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;}
}

分析：

1. LinkedList的底层结构是双链表，从Node类就可以看出来
2. 放入数据add是可以放在首位，也可以放在末尾，不指定默认放在末尾， 同时放在使用set指定位置放入
3. 获取数据需要指定索引

Vector

protected Object[] elementData;
...
public Vector(int initialCapacity, int capacityIncrement) {super();if (initialCapacity < 0)throw new IllegalArgumentException("Illegal Capacity: "+initialCapacity);this.elementData = new Object[initialCapacity];this.capacityIncrement = capacityIncrement;
}/*** Constructs an empty vector with the specified initial capacity and* with its capacity increment equal to zero.** @param   initialCapacity   the initial capacity of the vector* @throws IllegalArgumentException if the specified initial capacity*         is negative*/
public Vector(int initialCapacity) {this(initialCapacity, 0);
}/*** Constructs an empty vector so that its internal data array* has size {@code 10} and its standard capacity increment is* zero.*/
public Vector() {this(10);
}/*** Constructs a vector containing the elements of the specified* collection, in the order they are returned by the collection's* iterator.** @param c the collection whose elements are to be placed into this*       vector* @throws NullPointerException if the specified collection is null* @since   1.2*/
public Vector(Collection<? extends E> c) {elementData = c.toArray();elementCount = elementData.length;// c.toArray might (incorrectly) not return Object[] (see 6260652)if (elementData.getClass() != Object[].class)elementData = Arrays.copyOf(elementData, elementCount, Object[].class);
}
...
/**
* 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);
}
...
/**
* 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;
}

分析：

1. Vector的底层原理是数组，构造器可指定容量大小，如果不指定，默认10
2. 放入数据synchronized同步方法
3. 获取数据synchronized同步方法

总结

1. ArrayList和Vector的底层结构是数组，LinkedList的底层是双链表
2. 查询的性能ArrayList和Vector比LinkedList高，因为是随机查询；一般的情况下频繁的插入和删除是LinkedList更高
3. 查询的性能ArrayList比Vector高，Vector有同步操作
4. ArrayList和LinkedList线程不安全，Vector线程安全