多数人的回答:
1.ArrayList的底层是顺序表,基于数组,而LinkedList底层是一个双向链表;
2.LinkedList增加删除比较快,ArrayList查找比较快;
这样回答真的正确吗?
第一点回答的没有问题,问题就出现在了第二点,第二点回答完全错误!!!
为什么?往下看~
第一,ArrayList查找并不快,只是具有随机访问的能力,什么是随机访问?就是根据下标获取元素,而查找则是需要遍历的,ArrayList的查找的时间复杂度为O(n),并没有优势!
第二,LinkedList增加删除也不快!首删和尾删还可以,时间复杂度为O(1),中间位置的删除虽然不像顺序表那样需要搬运元素,但时间复杂度依然是O(n)!为什么?删除元素你得先找到元素啊,找到了之后才能删除。而LinkedList指定位置增加元素也是这样,add(n, value),这是通过下标来描述的,对于链表来说,依然需要遍历,Java的这种封装,导致没有发挥出链表应有的优势!这中间位置的插入和删除元素不是链表不行,只是LinkedList不太行啊~
再来聊聊C++,C++中STL std : : list的插入元素是需要显式的指定一个迭代器,迭代器就指向了要插入的位置,这里的中间位置插入元素的时间复杂度才是O(1);
那该如何回答?
1.ArrayList的底层是顺序表,基于数组,而LinkedList底层是一个双向链表;
2.对于随机访问,ArrayList要优于LinkedList,ArrayList可以通过下标以O(1)的时间复杂度访问元素,而LinkedList不具备随机访问能力,是需要以O(n)的时间复杂度遍历链表,通过查找,找到元素。说到查找,ArrayList和LinkedList查找所需的时间复杂度是一样的,都为O(n);
3.对于插入和删除元素,LinkedList要优于ArrayList,因为LinkedList插入和删除元素不需要像ArrayList那样去搬运元素,计算大小;
4.LinkedList比ArrayList更占内存,因为LinkedList的结点不光需要ArrayList那样一份空间存储val值,LinkedList还需要另外需要两个空间,一个存储上一个结点的地址,一个存储下面位置的结点;
版权声明:本文内容由互联网用户自发贡献,该文观点仅代表作者本人。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容, 请发送邮件至 举报,一经查实,本站将立刻删除。
文章由极客之音整理,本文链接:https://www.bmabk.com/index.php/post/130451.html