Arraylist与LinkedList的区别

Arraylist和LinkedList都是Java中的集合框架，它们都实现了List接口，拥有类似的功能。但是，它们之间仍存在一些本质的区别，主要表现在以下几个方面：

1、存储结构不同

Arraylist是基于数组结构实现的，内部维护一个Object数组，每次添加元素，都会将元素添加到数组中，如果数组满了，就需要扩容，耗费额外的时间和空间；LinkedList是基于链表结构实现的，内部维护一个Node类型的对象，它是一个双向链表，每次添加元素，都会在链表中添加一个Node，不需要额外的时间和空间。

2、查询效率不同

Arraylist的查询效率比较高，因为它是基于数组结构实现的，可以使用下标快速定位到指定的元素，查询效率是O(1)；LinkedList的查询效率比较低，因为它是基于链表结构实现的，要定位到指定的元素，需要从头开始遍历，直到找到指定的元素，查询效率是O(n)。

3、插入/删除效率不同

Arraylist的插入/删除效率比较低，因为它是基于数组结构实现的，每次插入/删除，都需要移动指定位置之后的所有元素，耗费额外的时间；LinkedList的插入/删除效率比较高，因为它是基于链表结构实现的，每次插入/删除，只需要修改指针指向，不需要移动元素，所以插入/删除效率较高。

4、空间利用率不同

Arraylist的空间利用率比较高，因为它是基于数组结构实现的，数组中的每个元素都是有效的，没有浪费；LinkedList的空间利用率比较低，因为它是基于链表结构实现的，每个节点除了存储元素值之外，还需要存储两个指针，所以空间利用率较低。