ArrayList和LinkedList异同和效率比较

2020-06-29 本文已影响0人赖征先生

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很大的话，这一点也需要考虑进去。

ArrayList和LinkedList异同和效率比较

Java常见比较二

ArrayList

LinkedList

效率对比

猜你喜欢

热点阅读