Java常见比较二
ArrayList
1.png
ArrayList 在内存中是连续的、单向的、有序的。
ArrayList 中维护了一个按照下标顺序的一组数组，数组中每个 item 指向对应得 value。
private static final int DEFAULT_CAPACITY = 10;
private static final Object[] EMPTY_ELEMENTDATA = {};
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
transient Object[] elementData;
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);
}
}
public ArrayList() {
this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}
当我们通过下标进行指定位置增加或者删除操作时，先由下标 index 从 item 数组找到对应 item，接着从这个下标开始向后，把剩下的 item 通过覆盖复制，向后或者向前移动一位，最后在 index 位置增加一个 item 或者置空末尾 item。
// 增加
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++;
}
// 删除
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);
elementData[--size] = null; // clear to let GC do its work
return oldValue;
}
E elementData(int index) {
return (E) elementData[index];
}
当我们通过下标指定位置查找或者修改操作时，先由下标 index 从 item 数组获取对应item，返回或者修改 item 指向的对象地址。
// 查找
public E get(int index) {
rangeCheck(index);
return elementData(index);
}
// 修改
public E set(int index, E element) {
rangeCheck(index);
E oldValue = elementData(index);
elementData[index] = element;
return oldValue;
}
E elementData(int index) {
return (E) elementData[index];
}
LinkedList
2.png
LinkedList 在内存中时不连续的、双向的、有序的；
LinkedList 中的每个 item，成为 node，它包含三个部分：当前 node 的 value，指向上一个 node 的指针 prev、指向下一个 node 的指针 next。由于 LinkedList 还保存了第一个 node 称为 first 和最后一个 node 称为 last，所以他还是双向的。
transient Node<E> first;
transient Node<E> last;
public 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;
}
}
当我们通过下标进行指定位置增加或者删除操作时，会从 first node 开始（如果下标指向未端，则直接到末端 node），不断地由 node 的 next 找到下一个 node,直到到达目标 node,如果是增加操作，则创建一个 node，将上一个 node 的 next 指向新 node 的 prev，将下一个 node 的 prev 指向新 node 的 next，这样就在 list 中间重新连接起来；如果是删除操作，则删除当前 node，将上一个 node 的 next 指向下一个 node 的 prev。
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;
}
}
// 增加
public void add(int index, E element) {
checkPositionIndex(index);
if (index == size)
linkLast(element);
else
linkBefore(element, node(index));
}
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++;
}
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) {
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;
}
当我们通过下标进行指定位置查询或者修改操作时，会从 first node 或者 last node（LinkedList.get(int index)方法中，会对下标值进行判断，如果小于长度的一半，则从 first 开始，否则从 last 开始，这是对双向性的利用）开始，不断的由 node 的 next 去找下一个 node 的地址，直到到达目标 node，返回 value 或者修改 value 指向的地址
。
// 查找
public E get(int index) {
checkElementIndex(index);
return node(index).item;
}
// 修改
public E set(int index, E element) {
checkElementIndex(index);
Node<E> x = node(index);
E oldVal = x.item;
x.item = element;
return oldVal;
}
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;
}
}
效率对比
- ArrayList的优势在于随机快速读取，其直接在末尾插入元素的效率也很高。唯一需要注意的是，其resize的时候，需要一定的开销。所以如果你提前能预估ArrayList的大小，你可以在实例化时，给他赋一个initialCapacity，可以减小resize的次数。
- LinkedList的优势在于利用Iterator迭代器循环时，其插入和删除的效率都是最高的。
- 在存储空间上，LinkedList相比ArrayList的每个元素都有更多的开销，因为还存储了指向下一个和前一个元素的指针。所以如果你的list很大的话，这一点也需要考虑进去。
网友评论