这里写自定义目录标题

• 1. 他们的底层结构不同
• 2. ArrayList 和 LinkedList 都实现了 List 接口
• 3. 查询的对比
• • 3.1 ArrayList 类中的查询
  • 3.2 LinkedList 类中的查询
  • • 3.2.1 LinkedList 在查询时存在一种特殊情况
• 4. 添加的对比
• • 4.1 ArrayList 的添加操作
  • • 4.1.1 在最后的位置添加元素
    • 4.1.2 在指定位置添加元素
  • 4.2 LinkedList 的添加操作
  • • 4.2.1 在最后的位置添加元素
    • 4.2.2 在指定位置添加元素
• 5. 总结
• • 5.1 以下情况使用 ArrayList
  • 5.2 以下情况使用 LinkedList

1. 他们的底层结构不同

ArrayList 底层是基于数组实现的，ArrayList 类是一个可以动态修改的数组，与普通数组的区别就是它是没有固定大小的限制，我们可以添加或删除元素。

• LinkedList 底层是基于链表实现的，是一种线性表，但是并不会按线性的顺序存储数据，而是在每一个节点里存到下一个节点的地址。
• 正因为底层数据结构的不同，他们适用的场景不同，ArrayList 更适合随机查找，LinkedList 更适合删除和添加，查询、添加、删除的时间复杂度不同。

2. ArrayList 和 LinkedList 都实现了 List 接口

但是LinkedList还额外实现了Deque接口，正因为 LinkedList 实现了 Deque 接口，所以LinkedList 还可以当作队列来使用。

ArrayList 继承 AbstractList 类，实现 List 等接口

LinkedList 继承 AbstractSequentialList 类，实现 List 和 Deque 等接口

3. 查询的对比

• 指定下标进行查询，ArrayList 优于 LinkedList 。

是由于底层数据结构的原因，数组是提前分配好内存空间的。
对于链表来说，指定下标来查询，是需要遍历链表。

3.1 ArrayList 类中的查询

ArrayList 类中的 get() 方法

    /*** Returns the element at the specified position in this list.** @param  index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E get(int index) {rangeCheck(index);return elementData(index);}

3.2 LinkedList 类中的查询

LinkedList 类中的 get() 方法 和 node() 方法

    /*** Returns the element at the specified position in this list.** @param index index of the element to return* @return the element at the specified position in this list* @throws IndexOutOfBoundsException {@inheritDoc}*/public E get(int index) {checkElementIndex(index);return node(index).item;}

/*** Returns the (non-null) Node at the specified element index.*/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;}}

3.2.1 LinkedList 在查询时存在一种特殊情况

LinkedList 在获取第一个元素和最后一个元素时很快

原因在于，LinkedList 内部有两个属性，分别是 first 和 last 。
这两个属性一直持续的记录着，底层链表里面的第一个元素的位置和最后一个元素的位置在哪里。

/*** 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;

所以 LinkedList 在查询第一个元素和最后一个元素时很快，因为不涉及遍历。

/*** Returns the first element in this list.** @return the first element in this list* @throws NoSuchElementException if this list is empty*/public E getFirst() {final Node<E> f = first;if (f == null)throw new NoSuchElementException();return f.item;}/*** Returns the last element in this list.** @return the last element in this list* @throws NoSuchElementException if this list is empty*/public E getLast() {final Node<E> l = last;if (l == null)throw new NoSuchElementException();return l.item;}

4. 添加的对比

4.1 ArrayList 的添加操作

ArrayList 的添加操作是存在扩容的情况，并且对于 ArrayList 的添加操作要分情况考虑。

4.1.1 在最后的位置添加元素

不需要移动，需要扩容。

   /*** Appends the specified element to the end of this list.** @param e element to be appended to this list* @return true (as specified by {@link Collection#add})*/public boolean add(E e) {ensureCapacityInternal(size + 1);  // Increments modCount!!elementData[size++] = e;return true;}

4.1.2 在指定位置添加元素

指定位置的元素及后面的元素，均往后移动；效率相对较慢。（因为指定了位置，所以不用去遍历查找，但是需要移动元素）

  /*** Inserts the specified element at the specified position in this* list. Shifts the element currently at that position (if any) and* any subsequent elements to the right (adds one to their indices).** @param index index at which the specified element is to be inserted* @param element element to be inserted* @throws IndexOutOfBoundsException {@inheritDoc}*/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++;}

4.2 LinkedList 的添加操作

LinkedList 的添加操作不涉及扩容

4.2.1 在最后的位置添加元素

   /*** Appends the specified element to the end of this list.** 
This method is equivalent to {@link #addLast}.** @param e element to be appended to this list* @return {@code true} (as specified by {@link Collection#add})*/public boolean add(E e) {linkLast(e);return true;}/*** Links e as last element.*/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;elsel.next = newNode;size++;modCount++;}

4.2.2 在指定位置添加元素

需要遍历找到下标，但是插入很快。

    /*** Inserts the specified element at the specified position in this list.* Shifts the element currently at that position (if any) and any* subsequent elements to the right (adds one to their indices).** @param index index at which the specified element is to be inserted* @param element element to be inserted* @throws IndexOutOfBoundsException {@inheritDoc}*/public void add(int index, E element) {checkPositionIndex(index);if (index == size)linkLast(element);elselinkBefore(element, node(index));}/*** Inserts element e before non-null Node succ.*/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;elsepred.next = newNode;size++;modCount++;}

5. 总结

5.1 以下情况使用 ArrayList

• 频繁访问列表中的某一个元素。
• 只需要在列表末尾进行添加和删除元素操作。

5.2 以下情况使用 LinkedList

• 你需要通过循环迭代来访问列表中的某些元素。
• 需要频繁的在列表开头、中间、末尾等位置进行添加和删除元素操作。

与 ArrayList 相比，LinkedList 的增加和删除的操作效率更高，而查找和修改的操作效率较低。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！