ArrayList和LinkedList的区别(面试必问的ArrayList和LinkedList知识) | 您所在的位置:网站首页 › linkedlist链表和arraylist数组表有什么不同 › ArrayList和LinkedList的区别(面试必问的ArrayList和LinkedList知识) |
问到ArrayList和LinkedList的区别,这个是我曾经面试真实被问到的一个问题,其实也完全可以换一个问法:数组和链表有什么区别。 数据结构 ArrayList 的内部数据结构就是数组(一块连续的存储空间)。 LinkedList 的结构是一个双向链表(不连续的存储空间)。 通过 Java 源码可以看得出来 LinkedList 的数据结构是一个双向链表,每个节点是一个 Node,节点中有 3 个属性: item : 实际存放的内容; prev : 指向前一节点的指针; next : 指向后一节点的指针。 head 和 tail 分别作为头、尾节点,不包含数据。 及格答案 ArrayList:是连续的内存空间,所以查找快,方便寻址;但删除、插入慢,因为需要发生数据迁移; LinkedList:需要通过指针一个个寻找,查找慢;但删除、插入快,因为只要改变前后节点的指针指向即可。 在这里在大部分情况下其实是没有什么问题的,但毕竟世上没有什么绝对的事! 特殊情况查找 如果说的是,帮我查找出第 n 个元素,那就是 ArrayList 更占优势,因为它是连续的内存空间,可计算的,可以算内存偏移多少就可以定位到第 n 个。 LinkedList 不连续,无法计算偏移量,只能一个个往下找。 但如果说我要查找具体的比如 "A" 在哪,那这时候就不是按位置查找了,是按内容查找,这时候就只有遍历了,ArrayList 就发挥不了它的内存优势,没法计算,只能遍历,一个一个比较,这时候 ArrayList 和 LinkedList 就都是半斤八两了。 插入 当从中间插入,ArrayList 的优势就变成劣势,中间插入的数据会导致后面大量的数据往后挪,而 LinkedList 就只需要改变指针指向就好了。 当往末尾插入,ArrayList 可计算的优势就出来了,往里扔就行了。 但 LinkedList 也不傻,也不会真的从第一个开始找,一直找到最后一个再加上去,它有两个指针,一个指向头部,一个指向尾部,所以每次要加新的元素可以把 tail 指向改一下,重新指向最新的节点,这时候两个其实也差不多。 附加分 其实在 JDK 1.6 中,LinkedList 是一个双向循环链表的数据结构。 如果你还能说出这里的不同,那简直。。。。 爆款服务器 除注明外的文章,均为来源:老汤博客,转载请保留本文地址! 原文地址:https://tangjiusheng.com/it/695.html |
CopyRight 2018-2019 实验室设备网 版权所有 |