说的对吗？？？：arraylist 和 linkedlist 的区别

哔哩哔哩（横板）👉 https://b23.tv/kD9wEv5

小红书（竖版）👉 http://xhslink.com/kEspyi

今天我们通过面试常问的：

arraylist 和 linkedlist 的区别

这个问题来学习一下数据结构中

最最最最 最基础的两个

数组 链表

之所以这么说是因为之后的很多数据结构呢

其实都是 数组 + 链表 的不同方式的组合结构

arraylist | 数组

首先 我们知道 arraylist 是基于 数组 这种数据结构来实现的

也就是说 在内存空间中是连续分布的

所以 我们可以通过 数组下标 实现快速随机访问

而为了维持这种连续性

从中间删除或添加元素时

就需要将后面的元素向上或向下移动

这个移动元素的过程就会产生效率问题

而且位置越靠前 效率问题越严重

👉创作不易：点赞分享+关注！！！

linkedlist | 链表

反观linkedlist 则是基于 链表

准确的说 是 双向链表 来实现的

也就是说 在内存空间中是不连续、随机分布的

于是为了定位元素

每个元素除了保存数据本身

还要保存 前面元素 以及 后面元素 的两个地址指针

这也就是 "双向" 的意思了

所以链表的查询就比较麻烦了

需要遍历整个链表，直到命中元素

而对于删除、新增操作就比较简单了

只需改变指针地址即可

以上是通过 数据结构 的角度来分析的 arraylist 和 linkedlist 的区别

除此之外

java在实现它们的代码设计上也有一些 “小细节”需要提一嘴

第一处 扩容机制

在Arraylist的源码中，默认初始大小为 10

/**
* Default initial capacity.
*/
private static final int DEFAULT_CAPACITY = 10;

之后每次添加元素时都会先判断容量是否足够

如果不够了就会触发扩容机制

将容量扩大为原来的1.5倍

整个扩容过程非常耗时

需要重新申请一片空间

然后将原来的数据复制过去

所以如果条件允许，在使用Arraylist时最好先指定大小

第二处 分段遍历

在Linkedlist的源码中有这样一段

/**
* Returns the (non-null) Node at the specified element index.
*/
Node<E> node(int index) {
// assert isElementIndex(index);
if (index < (size >> 1)) {
Node<E> x = first;
for (int i = 0; i < index; i++)
x = x.next;
return x;
} else {
Node<E> x = last;
for (int i = size - 1; i > index; i--)
x = x.prev;
return x;
}
}

我命令我领导帮我看了一下

大概的意思是

如果目标元素位于链表的前半段

则从前面正向遍历

否则就从后面反向遍历

这样能稍微弥补一下链表在查询效率上的不足

好 了解了以上的内容

我们回看一些 面试宝典 上的说法：

两者对比，arraylist查询更快，linkedlist插入删除快

是绝对的吗？

其实受很多因素影响

就像是体育竞技

我们赛前分析 不管是 纸面实力 还是过往战绩

A队都必赢

但实际上却输了

所以你可以实际的去测试一下

我是浩说

帮你入门到放弃