A股上市公司传智教育(股票代码 003032)旗下技术交流社区北京昌平校区

 找回密码
 加入黑马

QQ登录

只需一步,快速开始

本帖最后由 耿晓波 于 2013-4-14 15:49 编辑

答案为什么是不一定啊?查了好多资料,都觉得应该是对的啊?高手指教一下。

评分

参与人数 1技术分 +1 收起 理由
冯海霞 + 1

查看全部评分

5 个回复

倒序浏览
举个列子吧:
假设链表中有一删除数据在链表末尾,
而你删除的时候你得从头开始遍历所有元素吧?
就是有这种特例存在,所以就说不一定咯。

评分

参与人数 1技术分 +1 收起 理由
冯海霞 + 1

查看全部评分

回复 使用道具 举报
我也认为一般情况下链表在增删元素的时候是优于数组的,如果非要说不一定  那么想我想应该是删除集合中最后一个元素的时候  数组的效率就高于链表了
回复 使用道具 举报
数组中的数据在内存中的按顺序存储的,而链表是随机存储的!   

要访问数组中的元素可以按下标索引来访问,速度比较快,如果对他进行插入操作的话,就得移动很多元素,所以对数组进行插入操作效率很低!

由于链表是随机存储的,链表在插入,删除操作上有很高的效率(相对数组),如果要访问链表中的某个元素的话,那就得从链表的头逐个遍历,直到找到所需要的元素为止,所以链表的随机访问的效率就比数组要低

评分

参与人数 1技术分 +1 收起 理由
冯海霞 + 1

查看全部评分

回复 使用道具 举报
这个问题的答案确实是不一定哦,我以前也在书上看到过这道题,做过笔记:你要考虑到这个问题,首先要查找被插入或者删除的位置,这个我们往往忽略掉了。

其实数组在计算机中的存储是一块连续的内存,通过索引访问;而链表则是不连续的存储单元,通过指针关联,这个基本知识大家都明白,数组中执行插入操作时,将插入点之后的元素依次后移一位,然后将新元素插入到腾出的位置。而进行删除操作时则是将指定位置的元素删掉,之后的元素依次前移一位,这看起来是是一个比较繁琐的过程,而对于链表,处理方式就很简单了,需要在某个节点之后插入节点的时候,只需要将新节点的后继指向该节点原本的后继,再将该节点的后继指向新节点即可,删除节点则更为简单,只需要让被删借点的前驱指向他的后继即可。

稍微思考一下,所有人都会认为数组在这方面的效率很差,但是这份比较从根本上说来说是不公平的,无论是链表还是数组,插入和删除都要两个步骤,查找位置,和插入删除,我们只关注了后者,那查找的实践却没有计算在内,对于数组来说查找位置就是查找索引的位置,这在计算机的计算中可以忽略不计,而链表只要找到了位置,插入和删除也就差不多完成了,所以二者的侧重点有所不同。下面是我写的代码验证一下二者的区别:就是随机访问10000次所需要的时间

package com.heima.jianjian;


import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;
import java.util.Random;


public class TimeTest
{
public static void main(String[] args)
{
long[] timeBegin = new long[2];// 记录开始时间
long[] timeEnd = new long[2];
Integer[] ia = new Integer[5000];
for (int i = 0; i < 5000; i++)
{
ia = i;
}
int tempi;
Random r = new Random();
// 对ArrayList数组进行随机访问
List list = new ArrayList(Arrays.asList(ia));
timeBegin[0] = System.currentTimeMillis();
for (int i = 0; i < 10000; i++)
{
tempi = (Integer) list.get(r.nextInt(5000));


}
timeEnd[0] = System.currentTimeMillis();
// 对LinkedList进行随机访问


list = new LinkedList(Arrays.asList(ia));
timeBegin[1] = System.currentTimeMillis();
for (int i = 0; i < 10000; i++)
{
tempi = (Integer) list.get(r.nextInt(5000));


}
timeEnd[1] = System.currentTimeMillis();

System.out.println(timeEnd[0] - timeBegin[0]);
System.out.println(timeEnd[1] - timeBegin[1]);



}
}

输出的结果分别是:5 和51毫秒 ;

希望能对你有所帮助,大家一起加油!

评分

参与人数 2技术分 +1 黑马币 +10 收起 理由
冯海霞 + 1
耿晓波 + 10 很给力! 谢谢你,好详细啊!加好友一起努力.

查看全部评分

回复 使用道具 举报
LS+~0U>>1.
回复 使用道具 举报
您需要登录后才可以回帖 登录 | 加入黑马