对ArrayList和LinkedList底层实现原理详解

ArrayList

简介

ArrayList是基于动态数组实现的，其最大的特点就是可以随机访问，这也是数组的一个最大优点。另外，ArrayList支持在尾部快速添加元素的操作，当然，如果要在中间插入、删除元素，这是需要移动数组元素，所以操作速度会相对比较慢，并且，在ArrayList中，如果进行了大量的移动元素的操作，这会导致性能下降。

实现原理

ArrayList的底层是一个Object类型的数组，当一个数组对象被创建时，其默认大小为10，我们可以通过构造方法或add等方法进行扩容。每次扩容，容量会翻倍，也可以指定容量大小。可以看下面的示例代码：

ArrayList<String> list = new ArrayList(20);

这里创建了一个初始容量为20的ArrayList。

示例说明

添加元素

ArrayList支持在尾部快速添加元素的操作，我们可以使用该类提供的add()方法进行添加，代码如下：

ArrayList<Integer> list = new ArrayList<>(2);
list.add(1);
list.add(2);

上述代码中，我们创建了一个初始容量为2的ArrayList，添加了1和2两个元素。再看下面的代码：

list.add(3);

上述代码执行后，ArrayList的长度会变成3，同时在数组的第三个位置添加新元素3。

随机访问

ArrayList是基于动态数组实现的，其最大的特点就是可以随机访问，我们可以使用get()方法在ArrayList中访问特定位置的元素，代码如下：

list.get(2); //获取第三个元素

上述代码会返回ArrayList中的第三个元素的索引值，注意索引是从0开始的。

LinkedList

简介

LinkedList是基于链表实现的，其最大的优点就是在中间插入、删除元素时速度非常快，因为只需要改变待操作元素的前驱或后继节点指针即可，而不需要像ArrayList一样移动数组元素。当然，LinkedList无法像ArrayList一样随机访问，必须从头节点开始遍历到指定节点才行。同时，在LinkedList中，在添加、删除元素时，并不需要移动数组元素，所以其性能相对比较稳定。

实现原理

LinkedList的底层是一个双向链表，每个节点保存有前驱节点和后继节点的引用，同时，LinkedList中还有一个指向链表头部和链表尾部的头节点和尾节点的引用。

示例说明

添加元素

LinkedList支持在尾部快速添加元素的操作，我们可以使用该类提供的add()方法进行添加，代码如下：

LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);

上述代码中，我们创建了一个名为list的LinkedList，添加了1和2两个元素。再看下面的代码：

list.add(3);

上述代码执行后，LinkedList的元素个数变成3，同时在链表的尾部添加一个新节点，节点值为3。

中间插入、删除元素

LinkedList在中间插入、删除元素时，速度非常快。我们依然可以使用add()、remove()方法进行操作，例如代码如下：

LinkedList<Integer> list = new LinkedList<>();
list.add(1);
list.add(2);
list.add(3);

list.add(1, 10);//在第二个位置添加元素10

list.remove(0);//在第一个位置删除元素1

上述代码中，我们首先创建了一个名为list的LinkedList，并添加了1、2、3三个元素。接着，在第二个位置插入元素10，即1、10、2、3。删除列表中的第一个元素1。

总结

ArrayList和LinkedList都有自己的优点和缺点，这取决于具体的应用场景。如果需要进行大量随机访问操作，那么应该选择ArrayList；如果需要进行大量中间插入、删除操作，那么应该选择LinkedList。