黑马程序员技术交流社区

标题: 【上海校区】java集合系列——List集合总结（六） [打印本页]

作者: 不二晨 时间: 2018-10-22 12:04
标题: 【上海校区】java集合系列——List集合总结（六）
一.总结概述

List继承了Collection，是有序的列表。
实现类有ArrayList、LinkedList、Vector、Stack等
ArrayList是基于数组实现的，是一个数组队列。可以动态的增加容量！
LinkedList是基于链表实现的，是一个双向循环列表。可以被当做堆栈使用！
Vector是基于数组实现的，是一个矢量队列，是线程安全的！
Stack是基于数组实现的，是栈，它继承与Vector，特性是FILO（先进后出）！
二.使用场景

在实际的应用中如果使用到队列，栈，链表，首先可以想到使用List。不同的场景下面使用不同的工具，效率才能更高！
1. 当集合中对插入元素数据的速度要求不高，但是要求快速访问元素数据，则使用ArrayList！
2. 当集合中对访问元素数据速度不做要求不高，但是对插入和删除元素数据速度要求高的情况，则使用LinkedList！
3.当集合中有多线程对集合元素进行操作时候，则使用Vector！但是现在BVector现在一般不再使用，如需在多线程下使用，可以用CopyOnWriteArrayList，在java.util.concurrent包下。
4.当集合中有需求是希望后保存的数据先读取出来，则使用Stack！

三.性能测试

/*
* @author 阿飞
* 性能测试，通过插入、随机读取和删除对ArrayList、LinkedList、Vector和Stack进行测试！
* 结论：看LinkedList
*  插入10万个元素，LinkedList所花时间最短：17 ms。
*  删除10万个元素，LinkedList所花时间最短： 9 ms。
*  遍历10万个元素，LinkedList所花时间最长：10255 ms；而ArrayList、Stack和Vector则相差不多，都只用了几秒。
*  (1) 对于需要快速插入，删除元素，应该使用LinkedList。
*  (2) 对于需要快速随机访问元素，应该使用ArrayList。
*
*/
public class ListTest {

private static final int COUNT = 100000; //十万

private static ArrayList<Object> arrayList = new ArrayList<Object>();
private static LinkedList<Object> linkedList = new LinkedList<Object>();
private static Vector<Object> vector = new Vector<Object>();
private static Stack<Object> stack = new Stack<Object>();

public static void main(String[] args) {
      System.out.println("....开始测试插入元素..........");

      // 插入元素测试
      insertData(arrayList,"ArrayList") ;
      insertData(linkedList,"LinkedList") ;
      insertData(vector,"Vector") ;
      insertData(stack,"Stack") ;

      System.out.println("....开始测试读取元素..........");

      // 随机读取元素测试
      readAccessData(arrayList,"ArrayList") ;
      readAccessData(linkedList,"LinkedList") ;
      readAccessData(vector,"Vector") ;
      readAccessData(stack,"Stack") ;

      System.out.println("....开始测试删除元素..........");

      // 随机读取元素测试
      deleteData(arrayList,"ArrayList") ;
      deleteData(linkedList,"LinkedList") ;
      deleteData(vector,"Vector") ;
      deleteData(stack,"Stack") ;

}

/**
   * 指定的List 的子类中插入元素，并统计插入的时间
   * @param list List 的子类
   * @param name 子类的名称
   */
private static void insertData(List<Object> list,String name) {
      long startTime = System.currentTimeMillis();

      // 向list的位置0插入COUNT个数
      for (int i=0; i<COUNT; i++){
         list.add(0, i);
      }

      long endTime = System.currentTimeMillis();
      long interval = endTime - startTime;
      System.out.println(name + " : 插入 "+COUNT+"元素，使用的时间是 " + interval+" ms");
}

/**
   * 指定的List 的子类中删除元素，并统计删除的时间
   * @param list List 的子类
   * @param name 子类的名称
   */
private static void deleteData(List<Object> list,String name) {
      long startTime = System.currentTimeMillis();

      // 删除list第一个位置元素
      for (int i=0; i<COUNT; i++)
         list.remove(0);

      long endTime = System.currentTimeMillis();
      long interval = endTime - startTime;
      System.out.println(name + " : 删除 "+COUNT+"元素，使用的时间是 " + interval+" ms");
}

/**
   * 指定的List 的子类中读取元素，并统计读取的时间
   * @param list List 的子类
   * @param name 子类的名称
   */
private static void readAccessData(List<Object> list,String name) {
      long startTime = System.currentTimeMillis();

      // 读取list元素
      for (int i = 0; i < COUNT; i++)
         list.get(i);

      long endTime = System.currentTimeMillis();
      long interval = endTime - startTime;
      System.out.println(name + " : 随机读取 "+COUNT+"元素，使用的时间是 " + interval+" ms");
}
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
运行结果：

....开始测试插入元素..........
ArrayList : 插入 100000元素，使用的时间是 970 ms
LinkedList : 插入 100000元素，使用的时间是 17 ms
Vector : 插入 100000元素，使用的时间是 968 ms
Stack : 插入 100000元素，使用的时间是 888 ms
....开始测试读取元素..........
ArrayList : 随机读取 100000元素，使用的时间是 6 ms
LinkedList : 随机读取 100000元素，使用的时间是 10255 ms
Vector : 随机读取 100000元素，使用的时间是 8 ms
Stack : 随机读取 100000元素，使用的时间是 4 ms
....开始测试删除元素..........
ArrayList : 删除 100000元素，使用的时间是 1460 ms
LinkedList : 删除 100000元素，使用的时间是 9 ms
Vector : 删除 100000元素，使用的时间是 1472 ms
Stack : 删除 100000元素，使用的时间是 894 ms
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

4.分析ArrayList和LinkedList运行结果

从运行的结果可以看出，ArrayList和LinkedLis适用各自的场景中！
为什么ArrayList读取速度快于LinkedList，而插入和删除速度又慢于LinkedList？
前面章节分析了这两个类的源码！

（1）ArrayList随机读取的时候采用的是get(index),根据指定位置读取元素，而LinkedList则采用size/2 ,二分法去加速一次读取元素！
源代码如下：
ArrayList：

public E get(int index) {
      rangeCheck(index);

      return elementData(index);
}
E elementData(int index) {
      return (E) elementData[index];//直接通过数组的下标来读取元素
}
1
2
3
4
5
6
7
8
LinkedList：

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;
      }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
（2）ArrayList插入时候要判断容量，删除时候要将数组移位，有一个复制操作！而LinkedList直接插入，不用判断容量，删除的时候也是直接删除跳转指针节点，没有复制的操作！
源代码如下：
ArrayList：

public boolean add(E e) {
      ensureCapacityInternal(size + 1);  // 判断是否要增容
      elementData[size++] = e;
      return true;
}
1
2
3
4
5
LinkedList：

public boolean add(E e) {
      linkLast(e);
      return true;
}

  void linkLast(E e) {
      final Node<E> l = last;
      final Node<E> newNode = new Node<>(l, e, null);
      last = newNode;
      if (l == null)
         first = newNode;
      else
         l.next = newNode;
      size++;
      modCount++;
}
---------------------
【转载】
作者：每天都在变得更好的阿飞
原文：https://blog.csdn.net/u010648555/article/details/59708627

作者: 小影姐姐 时间: 2018-10-25 09:50

作者: 不二晨 时间: 2018-10-25 10:39

作者: 魔都黑马少年梦 时间: 2018-10-25 14:40

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

黑马程序员IT技术论坛 X3.2