关于java:Java-中-ArrayList-和-LinkedList-有什么区别

在 Java 中，ArrayList 和 LinkedList 是两种常见的汇合类。它们都实现了 List 接口，提供了相似数组的性能，能够存储任意类型的对象。尽管它们都能够实现雷同的性能，然而它们的底层实现形式有所不同，因而在性能和用处上也存在一些差别。

ArrayList

ArrayList 是一个基于数组实现的动静数组，它能够主动扩大容量以包容新的元素。在 ArrayList 中，元素存储在一个 Object 数组中，能够通过索引拜访数组中的元素。

底层原理

ArrayList 底层应用数组实现，每个 ArrayList 实例都蕴含一个 Object 类型的数组 elementData，用于存储元素。当 ArrayList 中的元素数量超过数组容量时，ArrayList 会主动扩容，创立一个新的数组，并将原数组中的元素复制到新数组中。

private transient Object[] elementData;

在 ArrayList 中，增加元素的操作能够分为两种状况：

• 如果数组容量足够，间接将元素增加到数组开端。
• 如果数组容量有余，须要先对数组进行扩容，而后将元素增加到数组开端。

public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!
    elementData[size++] = e;
    return true;
}

private void ensureCapacityInternal(int minCapacity) {if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {minCapacity = Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    ensureExplicitCapacity(minCapacity);
}

private void ensureExplicitCapacity(int minCapacity) {
    modCount++;

    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

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);
}

在 ArrayList 中，删除元素的操作能够分为两种状况：

• 如果要删除的元素在数组两头，须要将后续的元素向前挪动，笼罩要删除的元素。
• 如果要删除的元素在数组开端，间接将数组长度减一即可。

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;
}

特点

• ArrayList 是一个基于数组实现的动静数组，能够主动扩容以包容新的元素。
• 在 ArrayList 中，元素能够通过索引拜访，因而随机拜访效率较高。
• 在 ArrayList 中，插入和删除操作可能须要挪动后续的元素，因而效率较低。

源码

ArrayList 的源码能够在 JDK 中找到，位于 java.util 包中。

LinkedList

LinkedList 是一个基于链表实现的双向链表，它能够动静地增加、删除元素。在 LinkedList 中，元素存储在一个节点 (Node) 中，每个节点蕴含一个元素和前后指针。

底层原理

LinkedList 底层应用双向链表实现，每个 LinkedList 实例都蕴含一个 Node 类型的 first 和 last 节点，用于示意链表的头和尾。

java

Copy

private transient Node<E> first;
private transient Node<E> last;

在 LinkedList 中，增加元素的操作能够分为三种状况：

• 如果链表为空，将新节点设置为 first 和 last 节点。
• 如果要增加的元素在链表头部，将新节点设置为 first 节点，并将原 first 节点作为新节点的后继。
• 如果要增加的元素在链表尾部，将新节点设置为 last 节点，并将原 last 节点作为新节点的前驱。

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++;
}

在 LinkedList 中，删除元素的操作能够分为三种状况：

• 如果要删除的元素是 first 节点，将 first 节点设置为原 first 节点的后继。
• 如果要删除的元素是 last 节点，将 last 节点设置为原 last 节点的前驱。
• 如果要删除的元素在链表两头，将要删除的节点的前驱和后继节点连接起来，而后将要删除的节点的前驱和后继节点别离指向要删除节点的前驱和后继节点。

public E remove(int index) {checkElementIndex(index);
    return unlink(node(index));
}

E unlink(Node<E> x) {
    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;
}

特点

• LinkedList 是一个基于链表实现的双向链表，能够动静地增加、删除元素。
• 在 LinkedList 中，元素不能通过索引拜访，因而随机拜访效率较低。
• 在 LinkedList 中，插入和删除操作只须要扭转相邻节点的指针，因而效率较高。

源码

LinkedList 的源码能够在 JDK 中找到，位于 java.util 包中。

ArrayList 和 LinkedList 的比拟

从底层实现上来看，ArrayList 和 LinkedList 有以下区别：

• ArrayList 底层应用数组实现，LinkedList 底层应用链表实现。
• 在 ArrayList 中，元素能够通过索引拜访，因而随机拜访效率较高，然而插入和删除操作效率较低。在 LinkedList 中，元素不能通过索引拜访，因而随机拜访效率较低，然而插入和删除操作效率较高。
• 在 ArrayList 中，增加和删除操作须要挪动后续的元素，因而效率较低。在 LinkedList 中，增加和删除操作只须要扭转相邻节点的指针，因而效率较高。
• 在 ArrayList 中，扩容时须要创立一个新的数组，并将原数组中的元素复制到新数组中，效率较低。在 LinkedList 中，不须要扩容，因为链表能够动静地增加、删除节点。

因为 ArrayList 和 LinkedList 的底层实现形式不同，因而它们实用的场景也不同：

• 如果须要频繁拜访汇合中的元素，并且汇合的大小不会常常扭转，抉择 ArrayList 会更加适合，因为 ArrayList 能够通过索引快速访问元素，效率较高。
• 如果须要频繁增加、删除汇合中的元素，抉择 LinkedList 会更加适合，因为 LinkedList 能够疾速地增加、删除节点，效率较高。

总结

ArrayList 和 LinkedList 是 Java 中常见的汇合类，它们都实现了 List 接口，提供了相似数组的性能，能够存储任意类型的对象。ArrayList 底层应用数组实现，LinkedList 底层应用链表实现。