ArrayList与LinkedList

约定不等于承诺〃 2023-09-30 11:15 14阅读 0赞

List 是一个有序、可重复的集合，集合中每个元素都有其对应的顺序索引。List 集合允许使用重复元素，可以通过索引来访问指定位置的集合元素。List 集合默认按元素的添加顺序设置元素的索引，第一个添加到 List 集合中的元素的索引为 0，第二个为 1，依此类推。  
List 实现了 Collection 接口，它主要有两个常用的实现类：ArrayList 类和 LinkedList 类。

ArrayList:

ArrayList 类实现了可变数组的大小，存储在内的数据称为元素。它还提供了快速基于索引访问元素的方式，对尾部成员的增加和删除支持较好。使用 ArrayList 创建的集合，允许对集合中的元素进行快速的随机访问，不过，向 ArrayList 中插入与删除元素的速度相对较慢。

LinkedList:

LinkedList 类采用链表结构保存对象，这种结构的优点是便于向集合中插入或者删除元素。需要频繁向集合中插入和删除元素时，使用 LinkedList 类比 ArrayList 类效果高，但是 LinkedList 类随机访问元素的速度则相对较慢。这里的随机访问是指检索集合中特定索引位置的元素。

### ArrayList 类和 LinkedList 类的区别 ###

ArrayList 与 LinkedList 都是 List 接口的实现类，因此都实现了 List 的所有未实现的方法，只是实现的方式有所不同。  
  
ArrayList 是基于动态数组[数据结构][Link 1]的实现，访问元素速度优于 LinkedList。LinkedList 是基于链表数据结构的实现，占用的内存空间比较大，但在批量插入或删除数据时优于 ArrayList。  
  
对于快速访问对象的需求，使用 ArrayList 实现执行效率上会比较好。需要频繁向集合中插入和删除元素时，使用 LinkedList 类比 ArrayList 类效果高。

在说一下最近在笔试中ArrayList和LinkedList用到的方法：

首先说ArrayList中的add(int index,E element)和set(int index,E element)：

set(int index,E element)：是更新，更新指定下标位置的值。  
add(int index,E element)：是添加，区别于一般的add(E e)，这个就是有个位置的概念，特殊位置之后的数据，依次往后移动。

再说LinkedList中的addFirst(E element)与addLast(E element)：

addFirst(E element)：将给定元素插入LinkedList的开头

addLast(E element)：将给定元素插入LinkedList的结尾

[Link 1]: http://c.biancheng.net/data_structure/