【朝花夕拾】Java基础第一章_集合_List

本系列文章源码基于Jdk1.8

• List

  
  list.png
  

  从上图List的继承关系中可以看出，List接口继承于Collection集合类，Collection继承于Iterable迭代器接口，jdk1.8中增加了接口默认实现方法的新特性，在这些接口中都有体现。

foreach()以及spliterator()就在Iterable中实现，后者提供了并行遍历的迭代器，这几个方法会在Jdk新特性章节中讲解。

Collection中定义了常用的集合增删改方法，1.8中新增了removeIf()方法用来处理原先java中繁琐的集合遍历时删除元素的功能，同时还有新特性中重点强调的stream()方法，是集合类函数编程的核心

List定义了List类型集合中Index相关的方法以及排序和替换元素的方法。

AbstractList.png

AbstractList继承了AbstractCollection类并实现了List中的方法，这里将set(int index, E element),add(int index, E element),remove(int index)三个默认方法禁用

ArrayList和LinkedList

• ArrayList
  ArrayList的底层是一个数组，数组的特点是在内存中是连续的空间，使用get(index)方法时可以通过数组的首位地址+偏移量直接算出第index个元素在内存中的位置，直接获得，时间复杂度为o(1)

• LinkedList
  LinkedList的底层是一个链表，使用get(index)获取数据的时候是通过顺序遍历的方式，时间复杂度为o(n)

• 常见误区
  ArrayList查询快，LinkedList增删快
  一般情况下，这句话没有问题，但是当指定了插入或者删除的元素的index之后，且数据量较大的情况下，ArrayList可能会比LinkedList要快，因为进行增删操作前，List需要先定位到指定位置的数据，LinkedList定位时间较ArrayList慢，所以LinkedList并不是增删一定比ArrayList快的。