List接口
- 说明
- List接口方法
List实现类之一：ArrayList
List实现类之二：LinkedList
- 新增方法
- LinkedList的源码分析
List 实现类之三：Vector
- Vector的源码分析
ArrayList/LinkedList/Vector的异同
- ArrayList和LinkedList的异同
- ArrayList和Vector的区别

List接口

说明

鉴于Java中数组用来存储数据的局限性，我们通常使用List替代数组
List集合类中元素有序、且可重复，集合中的每个元素都有其对应的顺序索引。
List容器中的元素都对应一个整数型的序号记载其在容器中的位置，可以根据序号存取容器中的元素。
JDK API中List接口的实现类常用的有：ArrayList、LinkedList和Vector。
List接口方法

List除了从Collection集合继承的方法外，List 集合里添加了一些根据索引来操作集合元素的方法。

int indexOf(Object obj):返回obj在集合中首次出现的位置，如果不存在，返回-1.
int lastIndexOf(Object obj):返回obj在当前集合中末次出现的位置，如果不存在，返回-1.
List subList(int fromIndex, int toIndex):返回从fromIndex到toIndex 位置的子集合
增：boolean add(Object obj)
删：Object remove(int index):移除指定index位置的元素，并返回此元素 / boolean remove(Object obj)
改：Object set(int index, Object ele):设置指定index位置的元素为ele
查：Object get(int index):获取指定index位置的元素
插：boolean addAll(int index, Collection eles):从index位置开始将eles中的所有元素添加进来
void add(int index, Object ele):在index位置插入ele元素
长度：int size()
遍历：① Iterator迭代器方式 ② 增强for循环 ③ 普通的循环

List实现类之一：ArrayList

说明

ArrayList 是 List 接口的典型实现类、主要实现类
本质上，ArrayList是对象引用的一个”变长”数组

Arrays.asList(…) 方法返回的 List 集合，既不是 ArrayList 实例，也不是 Vector 实例。 Arrays.asList(…) 返回值是一个固定长度的 List 集合

ArrayList的源码分析

jdk7情况下：

ArrayList list = new ArrayList();//底层创建了长度是10的Object[]数组elementData
list.add(123);//elementData[0] = new Integer(123);
.....
list.add(11);//如果此次的添加导致底层elementData数组容量不够，则扩容。
          //默认情况下，扩容为原来的容量的1.5倍，同时需要将原有数组中的数据复制到新的数组中。

结论：建议开发中使用带参的构造器：ArrayList list = new ArrayList(int capacity):指定底层数组大小为capacity

jdk 8中ArrayList的变化

ArrayList list = new ArrayList();//底层Object[] elementData初始化为{}.并没创建长度为10的数组
list.add(123);//第一次调用add()时，底层才创建了长度10的数组，并将数据123添加到elementData[0]
      ...
后续的添加和扩容操作与jdk 7 无异。

_小结：_jdk7中的ArrayList的对象的创建类似于单例的饿汉式，而jdk8中的ArrayList的对象的创建类似于单例的懒汉式，延迟了数组的创建，节省内存。

面试题

public void testListRemove() {
        List list = new ArrayList();
        list.add(1);
        list.add(2);
        list.add(3);
        updateList(list);
        System.out.println(list);//[1, 2]
    }
    private static void updateList(List list) {
        list.remove(2);//默认调用的是List接口重载的Object remove(int index)方法
        // list.remove(new Integer(2)):此时调用的才是Collection接口中的remove方法
    }

List实现类之二：LinkedList

对于频繁的插入或删除元素的操作，建议使用LinkedList类，效率较高 ,底层使用双向链表存储

新增方法

void addFirst(Object obj)将指定元素插入此列表的开头。
void addLast(Object obj) 将指定元素添加到此列表的结尾。
Object getFirst()返回此列表的第一个元素。
Object getLast()返回此列表的最后一个元素。
Object removeFirst() 移除并返回此列表的第一个元素。
Object removeLast() 移除并返回此列表的最后一个元素。

LinkedList的源码分析

LinkedList：双向链表，内部没有声明数组，而是定义了Node类型的first和last，用于记录首末元素。

LinkedList list = new LinkedList(); 内部声明了Node类型的first和last属性，默认值为null
list.add(123);//将123封装到Node中，创建了Node对象。
定义内部类Node，作为LinkedList中保存数据的基本结构。
   private static class Node<E> {
        E item;
        Node<E> next;//next变量记录下一个元素的位置
        Node<E> prev;//prev变量记录前一个元素的位置
        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

List 实现类之三：Vector

Vector 是一个古老的集合，JDK1.0就有了。大多数操作与ArrayList 相同，区别之处在于Vector是线程安全的。在各种list中，最好把ArrayList作为缺省选择。当插入、删除频繁时，使用LinkedList；Vector总是比ArrayList慢，所以尽量避免使用。

Vector的源码分析

jdk7和jdk8中通过Vector()构造器创建对象时，底层都创建了长度为10的数组。
在扩容方面，默认扩容为原来的数组长度的2倍。

ArrayList/LinkedList/Vector的异同

ArrayList和LinkedList的异同

二者都线程不安全，相对线程安全的Vector，执行效率高。
ArrayList是实现了基于动态数组的数据结构，LinkedList基于链表的数据结构。
对于随机访问get和set，ArrayList优于LinkedList，因为LinkedList要移动指针。
对于新增和删除操作add(特指插入)和remove，LinkedList比较占优势，因为ArrayList要移动数据。

ArrayList和Vector的区别

Vector和ArrayList几乎是完全相同的,唯一的区别在于Vector是同步类(synchronized)，属于强同步类。因此开销就比ArrayList要大，访问要慢。
正常情况下,大多数的Java程序员使用 ArrayList而不是Vector,因为同步完全可以由程序员自己来控制。Vector每次扩容请求其大小的2倍空间，而ArrayList是1.5倍。Vector还有一个子类Stack。

JavaSE 高级进阶

Collection子接口：List接口