ArrayList
对于ArrayList而言，它实现List接口、底层使用数组保存所有元素。其操作基本上是对数组的操作。
private transient Object[] elementData;
- 构造方法
ArrayList提供了三种方式的构造器。构造初始容量为10的空列表、构造一个指定初始容量的空列表以及构造一个包含指定collection的元素的列表，这些元素按照该collection的迭代器返回它们的顺序排列的。
public ArrayList() {
this(10);
}
public ArrayList(int initialCapacity) {
super();
if (initialCapacity < 0)
throw new IllegalArgumentException("Illegal Capacity: "+ initialCapacity);
this.elementData = new Object[initialCapacity];
}
public ArrayList(Collection<? extends E> c) {
elementData = c.toArray();
size = elementData.length;
// c.toArray might (incorrectly) not return Object[] (see 6260652)
if (elementData.getClass() != Object[].class)
elementData = Arrays.copyOf(elementData, size, Object[].class);
}
- 存储：
用得比较多的是add方法
// 将指定的元素添加到此列表的尾部。
public boolean add(E e) {
ensureCapacity(size + 1);
elementData[size++] = e;
return true;
}
// 将指定的元素插入此列表中的指定位置。
// 如果当前位置有元素，则向右移动当前位于该位置的元素以及所有后续元素（将其索引加1）。
public void add(int index, E element) {
if (index > size || index < 0)
throw new IndexOutOfBoundsException("Index: "+index+", Size: "+size);
// 如果数组长度不足，将进行扩容。
ensureCapacity(size+1); // Increments modCount!!
// 将 elementData中从Index位置开始、长度为size-index的元素，
// 拷贝到从下标为index+1位置开始的新的elementData数组中。
// 即将当前位于该位置的元素以及所有后续元素右移一个位置。
System.arraycopy(elementData, index, elementData, index + 1, size - index);
elementData[index] = element;
size++;
}
其中有一个判断容量的方法：
public void ensureCapacity(int minCapacity) {
modCount++;
int oldCapacity = elementData.length;
if (minCapacity > oldCapacity) {
Object oldData[] = elementData;
int newCapacity = (oldCapacity * 3)/2 + 1;
if (newCapacity < minCapacity)
newCapacity = minCapacity;
// minCapacity is usually close to size, so this is a win:
elementData = Arrays.copyOf(elementData, newCapacity);
}
}
数组进行扩容时，会将老数组中的元素重新拷贝一份到新的数组中，每次数组容量的增长大约是其原容量的1.5倍。这种操作的代价是很高的，因此在实际使用时，我们应该尽量避免数组容量的扩张。当我们可预知要保存的元素的多少时，要在构造ArrayList实例时，就指定其容量，以避免数组扩容的发生。
ArrayList还给我们提供了将底层数组的容量调整为当前列表保存的实际元素的大小的功能。它可以通过trimToSize方法来实现。代码如下：
public void trimToSize() {
modCount++;
int oldCapacity = elementData.length;
if (size < oldCapacity) {
elementData = Arrays.copyOf(elementData, size);
}
}
- 删除
// 移除此列表中指定位置上的元素。
public E remove(int index) {
RangeCheck(index);
modCount++;
E oldValue = (E) elementData[index];
int numMoved = size - index - 1;
if (numMoved > 0)
System.arraycopy(elementData, index+1, elementData, index, numMoved);
elementData[--size] = null; // Let gc do its work
return oldValue;
}
从数组中移除元素的操作，也会导致被移除的元素以后的所有元素的向左移动一个位置。
注：ArrayList为线程不安全，允许元素为null，如果需要在多线程中使用，可以采用
list<Object> list =Collections.synchronizedList(new ArrayList<Object>)
来创建一个ArrayList对象以解决线程安全问题。
LinkedList
LinkedList内部是一个双端链表结构，有两个变量，first指向链表头部，last指向链表尾部。
LinkedtList内部的成员变量如下：
transient int size = 0;
transient Node<E> first;
transient Node<E> last;
- 节点结构
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;
}
}
- 构造方法
/**
* 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);
}
- 添加操作
public boolean add(E e) {
linkLast(e);
return true;
}
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++;
}
首先指向链表的尾部last，然后新建一个node节点以last为首节点，同时将此node定义为当前链表的尾节点，也就是last，若l为空也就是插入前链表尾部为空，也就是为空链表，那么插入的节点是首节点也是尾节点，若不是那插入前链表尾部的后继节点就是当前newNode。
指定位置插入：
public void add(int index, E element) {
checkPositionIndex(index); //检查索引是否处于[0-size]之间
if (index == size)//添加在链表尾部
linkLast(element);
else//添加在链表中间
linkBefore(element, node(index));
}
linkBefore()
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++;
}
当向指定节点之前插入一个节点时，当前节点的后继为指定节点，而前驱结点为指定节点的前驱节点。此外，还要修改前驱节点的后继为当前节点，以及后继节点的前驱为当前节点。
- 删除操作
public E remove(int index) {
//判断index是否越界
checkElementIndex(index);
return unlink(node(index));
}
//删除指定节点，返回指定元素的值
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;
}
- 查询
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
//获取指定下标的元素
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为线程不安全，允许元素为null，如果需要在多线程中使用，可以采用
list<Object> list =Collections.synchronizedList(new LinkedList<Object>)
来创建一个LinkedList对象以解决线程安全问题。
由上可知ArrayList 增删麻烦，需要移动数组。查询快，直接根据下标获取。
LinkedList增删快，直接根据下标更换节点的首尾节点。查询慢，需要遍历小于半个链表长度的数据。
网友评论