ArrayList和LinkedList的区别(面试必问的ArrayList和LinkedList知识)

 分类:IT知识时间:2022-08-22 07:30:05点击:

问到ArrayList和LinkedList的区别,这个是我曾经面试真实被问到的一个问题,其实也完全可以换一个问法:数组和链表有什么区别。

数据结构

ArrayList 的内部数据结构就是数组(一块连续的存储空间)。

LinkedList 的结构是一个双向链表(不连续的存储空间)。


通过 Java 源码可以看得出来 LinkedList 的数据结构是一个双向链表,每个节点是一个 Node,节点中有 3 个属性:

  1. item : 实际存放的内容;

  2. prev : 指向前一节点的指针;

  3. next : 指向后一节点的指针。


  1. head 和 tail 分别作为头、尾节点,不包含数据。

及格答案

ArrayList:是连续的内存空间,所以查找快,方便寻址;但删除、插入慢,因为需要发生数据迁移;


LinkedList:需要通过指针一个个寻找,查找慢;但删除、插入快,因为只要改变前后节点的指针指向即可。


在这里在大部分情况下其实是没有什么问题的,但毕竟世上没有什么绝对的事!

特殊情况查找

如果说的是,帮我查找出第 n 个元素,那就是 ArrayList 更占优势,因为它是连续的内存空间,可计算的,可以算内存偏移多少就可以定位到第 n 个。

LinkedList 不连续,无法计算偏移量,只能一个个往下找。

但如果说我要查找具体的比如 "A" 在哪,那这时候就不是按位置查找了,是按内容查找,这时候就只有遍历了,ArrayList 就发挥不了它的内存优势,没法计算,只能遍历,一个一个比较,这时候 ArrayList 和 LinkedList 就都是半斤八两了。

插入

当从中间插入,ArrayList 的优势就变成劣势,中间插入的数据会导致后面大量的数据往后挪,而 LinkedList 就只需要改变指针指向就好了。

当往末尾插入,ArrayList 可计算的优势就出来了,往里扔就行了。

但 LinkedList 也不傻,也不会真的从第一个开始找,一直找到最后一个再加上去,它有两个指针,一个指向头部,一个指向尾部,所以每次要加新的元素可以把 tail 指向改一下,重新指向最新的节点,这时候两个其实也差不多。

附加分

其实在 JDK 1.6 中,LinkedList 是一个双向循环链表的数据结构。

如果你还能说出这里的不同,那简直。。。。

除注明外的文章,均为来源:老汤博客,转载请保留本文地址!
原文地址: