黑马程序员技术交流社区

标题: 关于数组和链表增删元素的问题 [打印本页]
作者: 冷叙辰    时间: 2013-3-12 19:55
标题: 关于数组和链表增删元素的问题

  2.                 Random r = new Random();
  3.                 List<String> arrayList = new ArrayList<String>();
  4.                 List<String> linkedList = new LinkedList<String>();
  5.                 for (int i = 0; i < 10000; i++) {
  6.                         arrayList.add("string" + i);
  7.                 }
  8.                 for (int i = 0; i < 10000; i++) {
  9.                         linkedList.add("string" + i);
  10.                 }
  11.                 long start = 0;
  12.                 long end = 0;
  13.                 start = System.currentTimeMillis();
  14.                 for (int i = 0; i < 10000; i++) {
  15.                         arrayList.remove(r.nextInt(10000));
  16.                         arrayList.add(r.nextInt(10000), "string" + i);
  17.                 }
  18.                 end = System.currentTimeMillis();
  19.                 System.out.println("arrayList的时间"+(end - start));
  20.                 start = System.currentTimeMillis();
  21.                 for (int i = 0; i < 10000; i++) {
  22.                         linkedList.remove(r.nextInt(10000));
  23.                         linkedList.add(r.nextInt(10000), "string" + i);
  24.                 }
  25.                 end = System.currentTimeMillis();
  26.                 System.out.println("linkedList的时间"+(end - start));
  27.        
复制代码
在链表和数组中的随机位置增删元素，大家都说是链表的速度快，但是我发现实际情况却是数组的耗时比较短啊

这个原因是什么啊？
作者: 彭颖    时间: 2013-3-12 20:51
这种说法是在只考虑数据结构的情况下是如此
而你这里使用的是java包装的类  当然 实现不一样 执行性能也就不一样了


这是arraylist的remove
  1.     public E remove(int index) {
  2.         RangeCheck(index);

  4.         modCount++;
  5.         E oldValue = (E) elementData[index];

  7.         int numMoved = size - index - 1;
  8.         if (numMoved > 0)
  9.             System.arraycopy(elementData, index+1, elementData, index,
  10.                              numMoved);
  11.         elementData[--size] = null; // Let gc do its work

  13.         return oldValue;
  14.     }
复制代码
这是linkedlist 的remove
  1.     private E remove(Entry<E> e) {
  2.         if (e == header)
  3.             throw new NoSuchElementException();

  5.         E result = e.element;
  6.         e.previous.next = e.next;
  7.         e.next.previous = e.previous;
  8.         e.next = e.previous = null;
  9.         e.element = null;
  10.         size--;
  11.         modCount++;
  12.         return result;
  13.     }
复制代码
下面这个是用对象模仿的指针  执行效率 肯定要低些
作者: 李辉    时间: 2013-3-13 06:28
对于那些告诉你链表比数组随机访问快的人，下次就别听他们忽悠了。
数组以及和数组类似的ArrayList 在随机访问方面都比链表快，但是这两个数据结构的插入移除操作要比链表慢很多。在应用时，根据要用这些数据实现的功能以及常用的操作来综合考虑 要选择的数据结构。
链表不光有插入移除快的优点，还能轻松的用作栈、队列等，是一个比较灵活的数据结构。
作者: 猫腻    时间: 2013-3-13 09:43
楼主，请及时结贴。



欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2