JAVA 源码之(ArrayList VS LinkedList

ArrayList

• 默认构造一个空的数组

• 默认大小为DEFAULT_CAPACITY(10)，在首次调用add方法时进行初始化
• 自动扩展方法:当数组满时，进行1.5倍扩容
• 特殊方法说明
  • add(index,element):将element添加到index位置，原来index元素依次进行后移动，元素size++
• modCount 记录了队列的变化次数(具体指List大小发生变化的次数)，list在遍历之前记录下当前mod，遍历过程随时检查mod是否变化，当发生变化是将抛出异常
• 通过迭代器的方式进行List的遍历，可以进行List的mode追踪
• 内部迭代器
  • Itr
    • 通过iteator()方法获取
    • 由第一个元素开始向后遍历
  • ListItr
    • 通过listIterator(index)进行获取
    • 随机指定位置的迭代器访问，可以向前也可以向后
    • 迭代器可以获取当前位置，前置元素和后置元素
  • Spliterator 为并行遍历数据设计的迭代器
    • Java8新增接口
    • trySplit尝试对现在的list进行1/2分割，如果无法分割将返回null
    • tryAdvance 处理所有元素，当没有元素处理时，返回false
• 元素的移除
  • remove(index) 一次的元素移动(拷贝index之后的数据,数组并不会进行回收,队形空间将被回收)
  • remove(Object) 删除第一个相等的对象，一次的数据移动
  • removeAll 删除多个元素多个元素，相同的也将被删除，可能有一次的数组拷贝动作(发生异常的情形下)
  • removeIf
  • trimToSize List
• retainAll 取集合之间交集
• SubList List的一个子集，和List共同使用数据，subList的变更将影响list的数据；list变更将导致subList无法正常使用(抛出ConcurrentModificationException异常)

LinkedList

• 其实现是一个双向链表
• 内部数据结构
  • Node
    • 保存节点数据
    • 保存一个向前指针和向后指针
  • ListItr 顺序迭代器
  • DescendingIterator 倒序迭代器

ArrayList VS LinkedList

• 内部事项方式的差异
  • 以数组为基础的ArrayList
  • 以链表为节点的LinkedList
• 随机访问性能对比: ArrayList优于LinkedList
• 节点的插入和删除
  • ArrayList需要进行数组的自动扩展和数组的拷贝
  • LinkedList 对于内存使用更加充分
• 通过modCount 对List的追踪，对List进行非读操作时，mod将进行变化
• 通过迭代器进行访问，可是追踪到List是否有其他线程进行操作