java容器-列表和队列

今天介绍一些java内的容器-列表和队列，有些容器会在后续案例中更详细介绍

列表和队列

• ArrayList
  • 实现了Iterable接口，可迭代，
  • 内部有一个数组elementData，一般有些预留空间，有整数size记录实际元素个数；
  • 添加元素时先判断数组是不是空的，如果是空的，则首次至少要分配的大小为DEFAULT_CAPACITY,DEFAULT_CAPACITY的值为10;
  • 有以指定的大小initialCapacity初始化内部的数组大小的构造方法
  • 可以随机访问，按照索引位置进行访问效率很高，用算法描述中的术语，效率是O(1)，简单说就是可以一步到位
  • 除非数组已排序，否则按照内容查找元素效率比较低，具体是O(N), N为数组内容长度，也就是说，性能与数组长度成正比
  • 添加元素的效率还可以，重新分配和复制数组的开销被平摊了，具体来说，添加N个元素的效率为O(N)
  • 插入和删除元素的效率比较低，因为需要移动元素，具体为O(N)
  • 非线程安全的
• LinkedList
  • 实现了Deque和Queue接口，可以按照队列、栈和双端队列的方式进行操作
  • 内部实现是双向链表，每个元素在内存都是单独存放的，元素之间通过链接连在一起
  • 按需分配空间，不需要预先分配很多空间
  • 不可以随机访问，按照索引位置访问效率比较低，必须从头或尾顺着链接找，效率为O(N/2)
  • 不管列表是否已排序，只要是按照内容查找元素，效率都比较低，必须逐个比较，效率为O(N)
  • 在两端添加、删除元素的效率很高，为O(1
  • 在中间插入、删除元素，要先定位，效率比较低，为O(N)，但修改本身的效率很高，效率为O(1)
• ArrayDeque
  • 基于数组实现
  • ArrayDeque实现了Deque接口，同LinkedList一样，它的队列长度也是没有限制的
  • ArrayDeque的高效来源于head和tail这两个变量，它们使得物理上简单的从头到尾的数组变为了一个逻辑上循环的数组，避免了在头尾操作时的移动
  • 在两端添加、删除元素的效率很高，动态扩展需要的内存分配以及数组复制开销可以被平摊，具体来说，添加N个元素的效率为O(N)
  • 根据元素内容查找和删除的效率比较低，为O(N)
  • 与ArrayList和LinkedList不同，没有索引位置的概念，不能根据索引位置进行操作

特别说明

• 关于迭代器，有一种常见的误用，就是在迭代的中间调用容器的删除方法，如

  for(Integer a : list) {
    if(a<=0) {
      list.remove(a);
    }
  }
  

  会抛出一场，可以改用迭代器：

  Iterator<Integer> it = list.iterator();
  while(it.hasNext()) {
  if(it.next() < 0) {
    it.remove();
  }
  }
  

  原理： 迭代器中cursor表示下一个要返回的元素位置，lastRet表示最后一个返回的索引位置，expected-ModCount表示期望的修改次数，初始化为外部类当前的修改次数modCount，回顾一下，成员内部类可以直接访问外部类的实例变量。每次发生结构性变化的时候modCount都会增加，而每次迭代器操作的时候都会检查expectedModCount是否与modCount相同，这样就能检测出结构性变化
• 多线程并发场景下，需要选择线程安全的容器，如ArrayList就不是线程安全的，直接在并发场景使用会有问题