1.List接口

1.1 的概述

有序的 collection（也称为序列）。此接口的用户可以对列表中每个元素的插入位置进行精确地控制。用户可以根据元素的整数索引（在列表中的位置）访问元素，并搜索列表中的元素。

1.2 特点

1、 数据有序

2、 允许存放重复元素

3、 元素都有索引

1.3 常用方法

 ListIterator<E> listIterator()
          返回此列表元素的列表迭代器（按适当顺序）。

 ListIterator<E> listIterator(int index)
          返回列表中元素的列表迭代器（按适当顺序），从列表的指定位置开始。

 void add(int index, E element)
          在列表的指定位置插入指定元素（可选操作）。

 boolean addAll(int index, Collection<? extends E> c)
          将指定 collection 中的所有元素都插入到列表中的指定位置（可选操作）。

 List<E> subList(int fromIndex, int toIndex)
          返回列表中指定的 fromIndex（包括 ）和 toIndex（不包括）之间的部分视图。

 E get(int index)
          返回列表中指定位置的元素。  

 int indexOf(Object o)
          返回此列表中第一次出现的指定元素的索引；如果此列表不包含该元素，则返回 -1。

1.4 案例 测试常用方法

import java.util.ArrayList;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
 
//这类用来测试List接口的常用方法
public class TestList {
 
    public static void main(String[] args) {
       //1、创建List对象
       //特点1：List集合元素都有索引，可以根据索引直接定位元素
       List list = new ArrayList();
      
       //2、常用方法
       list.add(111);
       list.add(222);
       list.add(333);
       list.add(444);
       list.add('a');
       list.add("abc");
      
       list.add(3,666);//在3的索引处添加指定元素
 
       //特点2：元素有序， 怎么存就怎么放
       System.out.println(list);//[111, 222, 333, 666, 444, a, abc]
      
       Object obj = list.get(4);//get(m) m是索引值，获取指定索引位置的元素
       System.out.println(obj);
    
       //3、迭代/遍历集合中的元素
       //使用Collection接口提供的iterator()
       Iterator it = list.iterator();
       while(it.hasNext()) {//判断集合里有没有下个元素
           Object o = it.next();
//         System.out.println(o);
       }
      
       //使用List接口提供的listIterator()
       //interfaceListIterator extends Iterator
       //区别：可以使用父接口的功能，同时拥有自己的特有功能，不仅顺序向后迭代还可以逆向迭代
       ListIterator it2 = list.listIterator();
       while(it2.hasNext()) {
           Object o = it2.next();
//         System.out.println(o);
       }
      
       System.out.println();
      
       List list2 = list.subList(1, 3);//subList(m,n) m是开始索引，n是结束索引，其中含头不含尾类似于String.subString(m,n)
       System.out.println(list2);
      
    }
   
}

2. ArrayList

2.1 概述

1)   存在于java.util包中。

2)   内部用数组存放数据，封装了数组的操作，每个对象都有下标。

3)   内部数组默认初始容量是10。如果不够会以1.5倍容量增长。

4)   查询快，增删数据效率会降低。

2.2 创建对象

new ArrayList()：初始容量是10

2.3 案例 测试常用方法

常用API，包括下标遍历，迭代器遍历

import java.util.ArrayList;
public class TestAL {
       public static void main(String[] args) {
              ArrayList list = new ArrayList();
              list.add("aaa");//存入数据
              list.add("123");
              list.add("ccc");
              list.add("ddd");
              System.out.println(list);//list中内容
              System.out.println(list.size());//集合长度
              System.out.println(list.get(1));//根据下标获取元素
                    
              System.out.println();
              System.out.println(list.remove(2));//移除下标对应的元素
              System.out.println(list);
                    
              //下标遍历
              for (int i = 0; i < list.size(); i++) {
                     System.out.print(list.get(i));
              }
 
              //Iterator迭代遍历，封装了下标
              Iterator<String> it = list.iterator();
              while (it.hasNext()) {//如果有数据
                     String s = it.next();//一个一个向后遍历
                     System.out.println(s);
              }     
     }
}

2.4 ArrayList扩容

ArrayList相当于在没指定initialCapacity时就是会使用延迟分配对象数组空间，当第一次插入元素时才分配10（默认）个对象空间。假如有20个数据需要添加，那么会分别在第一次的时候，将ArrayList的容量变为10；之后扩容会按照1.5倍增长。也就是当添加第11个数据的时候，Arraylist继续扩容变为10*1.5=15；当添加第16个数据时，继续扩容变为15 * 1.5 =22个

ArrayList没有对外暴露其容量个数，查看源码我们可以知道，实际其值存放在elementData对象数组中，那我们只需拿到这个数组的长度，观察其值变化了几次就知道其扩容了多少次。怎么获取呢？只能用反射技术了。

3. LinkedList

3.1 概述

双向链表，两端效率高。底层就是数组和链表实现的。

3.2 常用方法

void addFirst(E e) 
		 将指定元素插入此列表的开头。 

void addLast(E e) 
         将指定元素添加到此列表的结尾。 
E getFirst() 
         返回此列表的第一个元素。 

E getLast() 
         返回此列表的最后一个元素。 

boolean offer(E e) 
         将指定元素添加到此列表的末尾（最后一个元素）。 

boolean offerFirst(E e) 
         在此列表的开头插入指定的元素。 

boolean offerLast(E e) 
         在此列表末尾插入指定的元素。 

E peek() 
         获取但不移除此列表的头（第一个元素）。 

E peekFirst() 
         获取但不移除此列表的第一个元素；如果此列表为空，则返回 null。 

E peekLast() 
         获取但不移除此列表的最后一个元素；如果此列表为空，则返回 null。 

E poll() 
         获取并移除此列表的头（第一个元素） 

E pollFirst() 
         获取并移除此列表的第一个元素；如果此列表为空，则返回 null。 

E pollLast() 
         获取并移除此列表的最后一个元素；如果此列表为空，则返回 null。 

E pop() 
         从此列表所表示的堆栈处弹出一个元素。 

void push(E e) 
         将元素推入此列表所表示的堆栈。 

E removeFirst() 
         移除并返回此列表的第一个元素。 

E removeLast() 
         移除并返回此列表的最后一个元素。 

3.3 案例 测试迭代器遍历

双向链表：下标遍历效率低，迭代器遍历效率高

import java.util.ArrayList;
import java.util.Iterator;
import java.util.LinkedList;
 
public class Test {
       public static void main(String[] args) throws Exception {
              LinkedList ll = new LinkedList ();
              for (int i = 0; i < 100000; i++) {
                     ll.add(100);
              }
              f1(ll);
              f2(ll);
       }
 
       private static void f2(LinkedList<Integer> ll) {
              long t = System.currentTimeMillis();
              Iterator it = ll.iterator();
              while(it.hasNext()) {
                     it.next();
              }
              t = System.currentTimeMillis()-t;
              System.out.println("=====iterator========="+t);//16
       }
 
       private static void f1(LinkedList<Integer> ll) {
              long t = System.currentTimeMillis();
              for (int i = 0; i < ll.size(); i++) {
                     ll.get(i);
              }
              long t1 = System.currentTimeMillis();
              System.out.println("~~~~for~~~~~~~"+(t1-t));//9078
       }
}

3.3 数组和链表区别

List是一个接口，它有两个常用的子类，ArrayList和LinkedList，看名字就可以看得出一种是基于数组实现另一个是基于链表实现的。

数组ArrayList遍历快，因为存储空间连续；链表LinkedList遍历慢，因为存储空间不连续，要去通过指针定位下一个元素，所以链表遍历慢。

数组插入元素和删除元素需要重新申请内存，然后将拼接结果保存进去，成本很高。例如有100个值，中间插入一个元素，需要数组重新拷贝。而这个动作对链表来说，太轻松了，改变一下相邻两个元素的指针即可。所以链表的插入和修改元素时性能非常高。

实际开发就根据它们各自不同的特点来匹配对应业务的特点。业务一次赋值，不会改变，顺序遍历，就采用数组；业务频繁变化，有新增，有删除，则链表更加适合。