一、相同点

1.两者都实现了Java的 List 接口，可以包含重复元素，并保持元素的顺序。
2.它们都是非线程安全的集合，即在多线程环境中共享时需要外部同步。

图1 ArrayList 

图2 LinkedList 

二、不同点

1.底层数据结构

ArrayList在Java中是基于动态数组实现的。它内部维护一个Object类型的数组来存储列表中的元素。这个数组在创建ArrayList实例时初始化为一定的大小，并且可以根据需要自动扩展以容纳更多的元素。

从下图可以看出，无论是ArrayList的有参构造还是无参构造，都会初始化一个Object类型的elementData数组。

有参构造会将一个Object类型的DEFAULTCAPACITY_EMPTY_ELEMENTDATA数组给elementData。

有参构造传入的参数为0时会将一个Object类型的EMPTY_ELEMENTDATA数组给elementData。

总之，这两个数组都是空数组，长度为0。

当我们使用add方法首次向集合（使用无参构造创建了一个ArrayList对象）中添加数据时，可以发现数据被保存在了elementData数组中。

// 创建一个ArrayList对象
ArrayList<String> list = new ArrayList<String>();

// 添加元素
list.add("关羽");
list.add("张飞");

而LinkedList在Java中是基于双向链表实现的。每个节点包含三部分信息：存储的元素、指向前一个节点的引用和指向下一个节点的引用。与ArrayList不同，LinkedList不需要预先分配固定大小的空间，它可以灵活地在链表的头部或尾部添加或删除元素。 

当我们使用add方法首次向集合（使用无参构造创建了一个LinkedList对象）中添加元素时，可以发现数据是存储在Node类型的节点中的。

// 创建一个LinkedList对象
LinkedList<String> linkList = new LinkedList<String>();
// 添加元素
linkList.add("宋江");
linkList.add("晁盖");

 进入到add方法。

再进入到add方法中调用的linkLast方法中 ，可以发现有Node类型的节点。

再进入到Node类型的节点中，可以发现这个节点包含三部分的信息：存储的元素（item）、指向前一个节点的引用（prev）和指向下一个节点的引用（next）。数据就是存储在这样类型的节点中的。

 2.性能差异

（1）对于随机访问（通过索引来获取元素），ArrayList的性能通常优于LinkedList，因为它可以直接通过索引访问数组中的元素。相比之下，LinkedList需要从头节点或尾节点开始遍历。
（2）对于元素的插入和删除操作，LinkedList通常优于ArrayList，尤其是在列表中间位置进行操作时。LinkedList的插入和删除操作只需改变相邻节点的引用，而不需要移动其他元素。而ArrayList在插入或删除元素时可能需要移动大量元素。

 3.内存占用

 ArrayList在内部维护一个数组，可能会有未使用的空间，而LinkedList的每个节点除了存储数据外，还存储前后节点的引用，因此总体上可能占用更多内存。

 4.扩容机制

 ArrayList在添加元素时，如果数组满了，会进行扩容操作，创建一个更大的数组并复制旧数据，扩容策略通常是原容量的1.5倍。

首先，进入到add方法中（使用无参构造创建了一个ArrayList对象），ArrayList将数据存储到elementData之前，会先调用ensureCapacityInternal方法。

让我们再进入到ensureCapacityInternal方法中，可以看到ensureCapacityInternal方法中调用了ensureExplicitCapacity方法，ensureExplicitCapacity方法中又调用了calculateCapacity方法。

首次添加元素时，calculateCapacity方法返回的值为10（因为DEFAULT_CAPACITY的值为10），然后再回到ensureExplicitCapacity方法中，进入到if判断，符合条件，进入到grow方法中。

在grow方法中，我们可以看到，element数组的初始长度为10。

  

当我们所需的长度超过10时，我们可以看到，elementData的长度变成了15，扩容了1.5倍。

 而LinkedList没有固定大小限制，不需要像ArrayList那样进行扩容操作。

我们来简单看一下linkedList中的添加元素操作。

若我们使用boolean add(E e)方法添加元素，元素会按顺序添加在上一个元素的末尾。

首先，当我们进入到boolean add(E e)方法中，可以发现add方法中调用了linkLast方法。

再进入到linkLast方法中，可以发现LinkedList将数据存在了双选链表的第一个位置，以此类推。

last和first为Node类型的对象，初始化默认值为null。

若我们使用void add(int index, E element)方法添加元素，就是将元素添加到指定下标位置，可以发现add方法中调用了linkLast和linkBefore方法，前者就和添加元素到末尾一样，后者则是将元素添加到中间。 

进入到linkBefore方法中，可以看到元素被添加到了指定下标位置。 

 三、判断使用ArrayList还是LinkedList的依据

在选择使用ArrayList还是LinkedList时，根据我们上述的介绍，应该考虑以下几个关键因素：

1.随机访问性能：如果需要频繁通过索引访问列表中的元素，ArrayList由于其基于数组的实现，提供了常数时间复杂度的访问性能（O(1)），而LinkedList在进行随机访问时需要从头节点或尾节点开始遍历，时间复杂度为O(n)。
2.插入和删除操作：如果需要在列表的中间频繁插入或删除元素，LinkedList通常会提供更好的性能，因为它不需要移动其他元素，插入和删除操作的时间复杂度为O(1)。相比之下，ArrayList在进行这些操作时可能需要移动大量元素，时间复杂度为O(n)。
3.内存使用：ArrayList在内部维护一个数组，可能会有未使用的空间，而LinkedList的每个节点除了存储数据外，还存储前后节点的引用，因此总体上可能占用更多内存。
4.扩容成本：ArrayList在添加元素时，如果数组满了，需要进行扩容操作，这涉及到创建新数组和复制现有元素，可能会影响性能。LinkedList没有固定大小限制，不需要进行类似的扩容操作。

根据上述因素，如果应用场景侧重于列表的尾部添加和随机访问，以及对内存使用有严格要求，ArrayList是更合适的选择。

如果应用场景涉及到大量的中间插入和删除操作，LinkedList可能会提供更佳的性能。

四、方法 

1.相同的方法

ArrayList和LinkedList都实现了Java的List接口，因此它们共享许多相同的方法。这些方法包括但不限于：

add(E e)：向列表末尾添加单个元素。
addAll(Collection<? extends E> c)：将指定集合的所有元素添加到列表的末尾。
clear()：从列表中移除所有元素。
contains(Object o)：检查列表中是否包含指定元素。
indexOf(Object o)：返回列表中首次出现的指定元素的索引，如果没有出现则返回-1。
get(int index)：返回列表中指定位置的元素。
set(int index, E element)：用指定的元素替换列表中指定位置的元素。
remove(Object o)：从列表中移除单个元素（可选操作）。
remove(int index)：移除列表中指定位置的元素。
size()：返回列表中的元素数量。
subList(int fromIndex, int toIndex)：返回列表的一部分，作为一个新的列表视图。
toArray()：返回一个包含列表所有元素的数组。
toString()：返回列表的字符串表示。

2. LinkedList独有的方法

LinkedList除了实现List接口的共同方法外，还提供了一些额外的方法，这些方法利用了LinkedList基于双向链表的数据结构特点。这些方法包括但不限于：

addFirst(E e)：将元素添加到列表的开头。
addLast(E e)：等价于add(E e)，将元素添加到列表的末尾。
remove()：移除列表头部的元素。
removeFirst()：等同于remove()，移除列表头部的元素。
getFirst()：返回列表头部的元素。
getLast()：返回列表尾部的元素。