[单选题]
牛客-007
答案：D
这个说法说反了
Arraylist的内存结构是数组，当超出数组大小时创建一个新的数组，吧原数组中元素拷贝过去。其本质是顺序存储的线性表，插入和删除操作会引发后续元素移动，效率低，但是随机访问效率高
LinkedList的内存结构是用双向链表存储的，链式存储结构插入和删除效率高，不需要移动。但是随机访问效率低，需要从头开始向后依次访问
编辑于 2015-01-10 21:34:39
回复(5)
解析：
//ArrayList源码
public class ArrayList<E> extends AbstractList<E>
implements List<E>, RandomAccess, Cloneable, java.io.Serializable
//LinkedList源码
public class LinkedList<E>
extends AbstractSequentialList<E>
implements List<E>, Deque<E>, Cloneable, java.io.Serializable
所以，A正确。
---------------------------------------------------------------------------------------------------------------------------------
ArrayList的大小是可以改变的，通过源码可以发现，它是基于数组实现的，往ArrayList里添加数据时，它首先会判断数组大小，是否已满（这个与HashMap不同，那个有装载因子），如果满了，则扩充数组，其实就是新建一个数组，然后把数据拷贝过去，新数组的大小与旧数组的大小关系如下。相信大伙都看得懂。
int newCapacity = oldCapacity + (oldCapacity >> 1);
LinkedList是节点结构如下，可以看出，item是存储数据的，next是指向下一个Node，prev是指向前一个Node的，所以说，LinkedList是双向的
Node(Node<E> prev, E element, Node<E> next) {
this.item = element;
this.next = next;
this.prev = prev;
}
因此，B正确。
---------------------------------------------------------------------------------------------------------------------------------
ArrayList是基于数组的，所以，具备随机访问特点，但LinkedList就不一样了，虽然，也可以通过也支持随机访问，但却付出了一定的代价。在LInkedLIst中，如果想返回某个位置的元素，就是从前往后遍历。如下。很明显，LinkedLIst不支持高效的随机访问。因此，C错误。
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;
}
}
---------------------------------------------------------------------------------------------------------------------------------
LinkedList是基于双链表的，增加是在尾部增加，增加和删除都只需要修改指针，不需要移动元素。
ArrayList插入或删除一个元素的开销不是固定的。在插入时，如果索引正确，容量够，则直接插入，插入位置之后的都需要移动，如果容易不够，还得扩充容量，开销当然不一样。删除操作同理。
所以，D错误，相当于说反了。
发表于 2015-08-17 12:49:27
回复(5)
D.
ArrayList的底层用的是数组，LinkedList底层使用的是链表
数组通过索引可以快速进行查找，查找效率高，但是增删要移动元素，所以增删的效率低
链表查找只能进行顺序查找，所以对随机查找一个元素的效率较低，但是增删的效率高。
发表于 2015-08-14 17:04:04
回复(0)
ArrayList和LinkedList在性能上各 有优缺点,都有各自所适用的地方,总的说来可以描述如下： 1．对ArrayList和LinkedList而言,在列表末尾增加一个元素所花的开销都是固定的.对 ArrayList而言,主要是在内部数组中增加一项,指向所添加的元素,偶尔可能会导致对数组重新进行分配；而对LinkedList而言,这个开销是统一的,分配一个内部Entry对象. 2．在ArrayList的 中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的. 3．LinkedList不 支持高效的随机元素访问. 4．ArrayList的空 间浪费主要体现在在list列表的结尾预留一定的容量空间,而LinkedList的空间花费则体现在它的每一个元素都需要消耗相当的空间 可以这样说：当操作是在一列数据的后面添加数据而不是在前面或中间,并且需要随机地访问其中的元素时,使用ArrayList会提供比较好的性能；当你的操作是在一列数据的前面或中间添加或删除数据,并且按照顺序访问其中的元素时,就应该使用LinkedList了. reference：http://zhidao.baidu.com/link?url=9zY7VV2CgyyDMunNLyfSM5BZgVvXcRtMLx8nec_wAEttKveZqeSMx5m1ytbCLb17iP94HijYC9NodlsKsww_vTfCrXBszFt7JirCYL6WJju
发表于 2016-06-27 12:30:55
回复(0)
考虑到线性表和链表，这道题就很同意求解。在ArrayList的中间插入或删除一个元素意味着这个列表中剩余的元素都会被移动；而在LinkedList的中间插入或删除一个元素的开销是固定的。
发表于 2017-01-12 16:02:59
回复(0)
arraylist底层使用数组进行实现的，当我们插入和删除的的时候，会创建一个新的数组进行操作，插入和删除比较消性能 listlink底层使用链表进行实现的，因此当我们对其进行插入的时候，是非常方便的，但是当我们想要遍历链表里面值得时候就没有那么方便了，因为链表的存储比较分散，不方便对其进行遍历
发表于 2024-10-12 21:00:26
回复(0)
答案d。 想选c，但是和c比起来，d错的更离谱。
c，链表支持高效的随机元素访问？ 和数组直接地址寻找比起来，链表的挨个遍历去访问元素，哪有高效可言？
如果随机访问元素的场景较多，一般使用数组。
d，说反了。
数组中插入一个元素，要把数组中插入位置后面的元素都向后挪一个位置，然后把要插入的元素放到该位置上。
链表在中间插入一个元素，那么太简单了， 修改插入位置的几个指针方向就完事了，开销就是固定常数级别的。
发表于 2022-09-07 09:44:57
回复(0)
ArrayList通过索引检索元素，速度快；而LinkedList遍历检索元素，速度慢；ArrayList插入元素的速度需要分情况（不考虑扩容），如果是在尾部插入，则无需移动元素，直接插入即可，速度快；若是在非尾部插入元素，则需要移动元素，速度慢；LinkedList插入元素，只需要修改插入元素前后元素的首尾只想即可，速度快。
发表于 2022-08-26 09:21:01
回复(0)
问题信息
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
