1.Arraylist

1.1优点与缺点：

查询效率高，增删效率低，线程不安全。使用频率很高。
无参构造函数会创建空的数组，只有真正添加元素的时候才会分配默认的10的初始容量。
有参构造函数它会按照给定的大小进行创建。
扩容机制：扩容jdk1.8以上会使用位运算，在原有的基础上右移一位，也就相当于除以2。
新增元素：新增，删除元素时都会移动元素。如果移动的元素很多，对整体的性能消耗是很大的。（复制copyOf）
查找元素：因为ArrayList集合实现了RandomAcces接口，支持快速访问（快速随机访问指的是通过元素的下标即可快速获取元素对象，无需遍历）

1.2常用方法

  • boolean add(E e)

将指定的元素添加到此列表的尾部。

  • void add(int index, E element)

将指定的元素插入此列表中的指定位置。

  • boolean addAll(Collection c)

按照指定 collection 的迭代器所返回的元素顺序，将该 collection 中的所有元素添加到此列表的尾部。

  • boolean addAll(int index, Collection c)

从指定的位置开始，将指定 collection 中的所有元素插入到此列表中。

  • void clear()

移除此列表中的所有元素。

  • Object clone()

返回此 ArrayList 实例的浅表副本。

  • boolean contains(Object o)

如果此列表中包含指定的元素，则返回 true。

  • void ensureCapacity(int minCapacity)

如有必要，增加此 ArrayList 实例的容量，以确保它至少能够容纳最小容量参数所指定的元素数。

  • E get(int index)

返回此列表中指定位置上的元素。

  • int indexOf(Object o)

返回此列表中首次出现的指定元素的索引，或如果此列表不包含元素，则返回 -1。

  • boolean isEmpty()

如果此列表中没有元素，则返回 true

  • int lastIndexOf(Object o)

返回此列表中最后一次出现的指定元素的索引，或如果此列表不包含索引，则返回 -1。

  • E remove(int index)

移除此列表中指定位置上的元素。

  • boolean remove(Object o)

移除此列表中首次出现的指定元素（如果存在）。

  • protected void removeRange(int fromIndex, int toIndex)

移除列表中索引在 fromIndex（包括）和 toIndex（不包括）之间的所有元素。

  • E set(int index, E element)

用指定的元素替代此列表中指定位置上的元素。

  • int size()

返回此列表中的元素数。

  • Object[] toArray()

按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组。

  • T[] toArray(T[] a)

按适当顺序（从第一个到最后一个元素）返回包含此列表中所有元素的数组；返回数组的运行时类型是指定数组的运行时类型。

  • void trimToSize()

将此 ArrayList 实例的容量调整为列表的当前大小。

1.3查询效率为什么快？

回答：ArrayList本身的基础数据结构，它是基于数组的数据结构，例如：我们要得到a[5]，那么我们是用a[0]的地址加上4乘以每个数组元素的字节长度。

2.LinkedList

1.1优点与缺点

  • LinkedList底层采用双向链表结构存储数据，允许重复数据和null值，长度没有限制。
  • 优点
    • 使用链表结构，不需要提前预估长度，可以克服数组需要预先知道数据长度的缺点
    • 链表使用不连续的内存空间，可以充分利用计算机内存空间，实现灵活的内存动态管理
  • 缺点
    • 链表相比于数组会占用更多的空间，因为链表中每个节点中，除了存放元素本身，还有存放指向其他节点的指针
    • 遍历和查找指定元素的速度比较慢

ArrayList&LinkedList - 图1

  • Node节点包含item（存储数据），next（后继节点）和prev（前继节点）。数组内存地址必须连续，而链表就没有这个限制了，Node可以分布于各个内存地址，它们之间的关系通过prev和next维护。 ```java private static class Node { E item; // 存储数据 Node next; // 后继节点 Node prev; // 前继节点

    Node(Node prev, E element, Node next) {

    1.   this.item = element;
    2.   this.next = next;
    3.   this.prev = prev;

    } }

```

  • 空参构造函数，默认size为0，每次添加新元素都要创建Node节点。

    1.2常用方法

    add(E e)
    将指定元素添加到此列表的结尾。
    add(int index, E element)
    在此列表中指定的位置插入指定的元素。
    addAll(int index, Collection<? extends E> c)
    将指定 collection 中的所有元素从指定位置开始插入此列表。
    addFirst(E e)
    将指定元素插入此列表的开头。
    addLast(E e)
    将指定元素添加到此列表的结尾。
    clear()
    从此列表中移除所有元素。
    contains(Object o)
    如果此列表包含指定元素，则返回 true。
    get(int index)
    返回此列表中指定位置处的元素。
    indexOf(Object o)
    返回此列表中首次出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。
    lastIndexOf(Object o)
    返回此列表中最后出现的指定元素的索引，如果此列表中不包含该元素，则返回 -1。
    offer(E e)
    将指定元素添加到此列表的末尾（最后一个元素）。
    peek()
    获取但不移除此列表的头（第一个元素）。
    poll()
    获取并移除此列表的头（第一个元素）
    set(int index, E element)
    将此列表中指定位置的元素替换为指定的元素。
    size()
    返回此列表的元素数。

1.3LinkedList为甚什么删除快？

回答：LinkedList集合首先是基于双向链表的存储结构，在插入或者删除数据时，它需要调整它的前后指向就行。没有指向的关系在一段的时间会被垃圾回收。而且LinkedList在内存中是分散的存储空间，不是连续的，仅靠指向关系连接。在查数据的时候，如果数据量不大的话，查询也还可以。主要针对数量过大，遇到数据在远端的情况，它会造成性能很大的消耗。ArrayList添加删除需要用到扩容,Arrays.copyOf()和System.arraycopy()方法,而LinkedList是链表操作。