Java集合框架之争：ArrayList vs LinkedList

由于ArrayList由动态数组实现，LinkedList由双向链表实现，这里将它们的对比归类于数组与链表的区别

一、相同点

• 数组和链表都是线性表，所谓线性，即结构像一条直线一样；

• 这与非线性结构是不一样的，例如二叉树，它的结构是一个树状图，那必然不是线性的

二、不同点

1）在空间上

• 数组使用连续空间存储，且数组容量往往会大于数据存储量，这就会有空间浪费

• 链表（多个链表节点）使用非连续的空间，通过链表节点地址连接，对空间利用率很高

2）在时间上

1. 按下标查询时

   数组查询数据时（get方法）直接根据下标访问，时间复杂度为O(1)

   链表查询数据时需要从头节点查找一直到找到目标元素，时间复杂度为O(n)

2. 添加或删除时

   数组添加（而且添加有扩容操作）和删除时找到目标元素后需要移动目标元素后面的所有元素，也就是对后面的元素都需要操作一次，那么时间复杂度为O(n)

   链表添加和删除时链表找到目标节点后可以直接改变next和pre指向，时间复杂度为O(1)

所以在多用查询操作时选择数组效率更高，在使用添加和删除操作频繁时选择链表效率更高

如果您觉得该文章有用，欢迎点赞、留言并分享给更多人。感谢您的支持！