Java集合--List集合接口

内容学习于：edu.aliyun.com

1. List接口简介

  Collction接口中有许多的子接口，但是这些接口里面使用最多的就是List接口，List 实际上就是和之前实现的自定义链表的形式非常相似的一种结构， 此接口定义如下。
  如下图所示：

No.	方法名称	类型	描述
01	boolean add(E e)	普通	在指定的索引位置上添加内容
02	E get(int index)	普通	获取指定索引位置上的数据
03	int indexOf(Object o)	普通	查找指定对象的索引位置
04	ListIterator listIterator()	普通	获取ListIterator接口实例
05	@SafeVarargs static List of(E… elements)	普通	通过指定的内容创建List集合
06	E set(int index, E element)	普通	修改指定索引位置的数据
07	default void sort(Comparator<? super E> c)	普通	实现List集合数据排序

  在JDK 1.9之后，List 接口做了改进，追加了一个of() 方法，可以实现内容的添加。

创建List集合代码：

public class JavaAPIDemo {

    public static void main(String[] args) throws Exception {
        List<String> all = List.of("Hello","MLDN","Hello");
        System.out.println(all);
    }

}

结果：

[Hello, MLDN, Hello]

  通过此时的操作可以在List集合中保存的数据可以存放有重复的数据内容，但是需要记住的是，利用of()方法所创建的List集合只是一个只读的集合，不能够对数据进行修改处理，一旦使用了remove()、add()、 set()等方法进行集合内容修改的时候会直接抛出“java.lang.UnsupportedOperationException" (不支持的操作异常)，此方法属于未实现的操作。
正常的设计来讲，如果要想使用List接口，往往都需要利用它的子类来进行接口对象的实例化处理，而在List 中有三个常用子类: ArrayList、 LinkedList、 Vector

2. ArrayList子类(90%)

  在使用List接口的时候最为常见的一一个子类就是ArrayList子类，这个类基本上会大量的出现在框架和自己所写的代码之中，首先来观察此类的继承结构:

• public class ArrayList extends AbstractList implements List

  ArrayList类继承了AbstractList 父类同时实现了List 接口，AbstractList 类定义如下:

• public abstract class AbstractList extends AbstractCollectionimplements List

  于是可以得到如下的继承关系。

  此时ArrayList 类继承了AbstractList, 而AbstractList 类又是List 接口的子类，同时ArrayList又重复实现了一个List接口，这样设计的目的只是对结构的继承关系做出明确的标记。
  由于所有的子类的对象都可以利用向上转型的关系为父接口进行实例化处理操作，所以对于ArrayList类而言，只关心它的构造方法，以及具体的功能实现形式，而所有的使用上都以List接口的方法为主，ArrayList 类构造:

No. 方法名称 类型 描述
01 public ArrayList() 普通 使用默认容量
02 public ArrayList(Collection<? extends E> c) 普通 设置一个初始化容量

  实际上ArrayList类的使用并不复杂，但是复杂的因素在于，需要清楚ArrayList类的实现原理，那么就必须来观察源代码。

无参构造：

public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}	
private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};

有参构造：

public ArrayList(int initialCapacity) {
        if (initialCapacity > 0) {//容量是否大于0，如果大于直接开辟
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {//如果为0，则使用空元素数组
            this.elementData = EMPTY_ELEMENTDATA;
        } else {//如果小于0，则无法开辟，抛出异常
            throw new IllegalArgumentException("Illegal Capacity: "+
                                               initialCapacity);
        }
}
private static final Object[] EMPTY_ELEMENTDATA = {};

数据添加：

public boolean add(E e) {
        modCount++;//计数的操作，线程同步保护
        add(e, elementData, size);
        return true;
    }

private void add(E e, Object[] elementData, int s) {//s是当前的数据个数
        if (s == elementData.length)//如果数据存满了
            elementData = grow();//开辟数组，会产生垃圾
        elementData[s] = e;
        size = s + 1;//数据个数的统计
    }


private Object[] grow() {//返回一个新的对象数组
        return grow(size + 1);
    }


private Object[] grow(int minCapacity) {
        int oldCapacity = elementData.length;
        if (oldCapacity > 0 || elementData != DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
            int newCapacity = ArraysSupport.newLength(oldCapacity,
                    minCapacity - oldCapacity, /* minimum growth */
                    oldCapacity >> 1           /* preferred growth */);
            return elementData = Arrays.copyOf(elementData, newCapacity);
        } else {
            return elementData = new Object[Math.max(DEFAULT_CAPACITY, minCapacity)];
        }
    }

  通过分析可以针对于ArrayList得出如下的结论:

• ArrayList 本身是基于数组的形式实现的集合操作，数组最大优势在于根据索引访问的时候时间复杂度为“O(1)”;当ArrayList中保存的容量不足时，每一次扩充“50%”;
• 所以在每一次使用ArrayList的时候一定要考虑好长度的存储问题，如果你保存的数据的长度在10或以内使用无参构造即可。

3. 自定义类对象存储

  在之前实现的全部都是String类对象的存储，但是在类集里面经常可以存放自定义类的对象，但是如果要想让所有的自定义类对象的集合可以正常操作，一定要在类中覆写equals()方法。

equals方法覆写：

class Ball{
    private String brand;
    private double price;

    public Ball(String brand, double price) {
        this.brand = brand;
        this.price = price;
    }

    @Override
    public String toString() {
        return "Ball{" +
                "brand='" + brand + '\'' +
                ", price=" + price +
                '}';
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;
        Ball ball = (Ball) o;
        return Double.compare(ball.price, price) == 0 &&
                Objects.equals(brand, ball.brand);//新的比较被string类型的equals方法覆写
    }
    
}


public class JavaAPIDemo {

    public static void main(String[] args) throws Exception {
        List<Ball> balls = new ArrayList<Ball>();
        balls.add(new Ball("aaa",1.2));
        balls.add(new Ball("bbb",2.4));
        balls.add(new Ball("ccc",3.6));
        System.out.println(balls.contains(new Ball("bbb",2.4)));
        balls.remove(new Ball("aaa",1.2));
        System.out.println(balls);
    }

}

结果：

true
[Ball{brand=‘bbb’, price=2.4}, Ball{brand=‘ccc’, price=3.6}]

  在以后进行项目开发的过程里面，List集合经常会用于进行数据的存储，对于需要动态查询或者删除的自定义类对象里面就一定要提供有equals()方法，但是如果此时只是进行存储而不进行contains()和remove()操作的时候，那么就不再需要使用到equals()方法了。

4. LinkedList子类

  LinkedList实际上通过名称就可以发现其是基于链表的方案实现的集合存储，首先来观察此类的继承结构:

• public class LinkedList
  extends AbstractSequentialList
  implements List, Deque, Cloneable, Serializable

  如下图所示

  在LinkedList类里面提供有节点处理类，这个类的定义如下:

Node类定义：

private static class Node<E> {
        E item;
        Node<E> next;
        Node<E> prev;

        Node(Node<E> prev, E element, Node<E> next) {
            this.item = element;
            this.next = next;
            this.prev = prev;
        }
    }

  既然LinkedList中的内容全部基于链表的形式存储，所以无参构造实际上什么都不会去做，每一次在进行新数据增加的时候只需要创建节点，并设计好节点之间的关系即可。

### 代码：
public class JavaAPIDemo {

    public static void main(String[] args) throws Exception {
        List<String>  data = new LinkedList<>();
        data.add("Hello");
        data.add("MLDN");
        System.out.println(data);
        System.out.println(data.get(1));
    }

}

结果：

[Hello, MLDN]
MLDN

add方法源代码：

  public boolean add(E e) {
        linkLast(e);
        return true;
    }

void linkLast(E e) {
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        size++;
        modCount++;
    }

get 方法源代码：

public E get(int index) {
        checkElementIndex(index);//检查index是否有误
        return node(index).item;
    }

  Node<E> node(int index) {
        // assert isElementIndex(index);

        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

  任何情况只要是链表操作就都会存在有“O(n)”性能问题。

5. Vector子类

  Vector类是最早的实现集合处理的操作类，其是在JDK 1.0 的时候提供的概念，表示的“向量”，但是到了JDK 1.2之后由于类集框架的出现之后类集的操作有了更加明确的规范化，所以让Vector多实现了一个List接口，这样才得以保存，而保留它的目的更多的情况下是处于“情怀”，因为太多的系统类和用户编写代码之中使用到了Vector, Vector 类的定义结构如下:

• public class Vector
  extends AbstractList
  implements List, RandomAccess, Cloneable, Serializable

  如下图所示

  Vector和ArrayList 虽然继承结构上相同，但是两者最大的区别在于，Vector 类中的方法采用的是synchronized同步处理机制，而ArrayList并未采用同步。

  由于一切的子类都向List接口进行实例化处理，所以使用那一个子类最终的效果都是相同，只不过每一个子类有每一个子类自己实现的操作机制，这一点是不同的，在开发更如果单论使用肯定就是List和ArrayList搭配最为常见，但是如果要问到原理的时候要将三个子类的实现原理详细说明

面试题:请解释ArrayList、LinkedList区别？

• ArrayList 是基于数组实现的集合类，而LinkedList是基于链表实现的集合类;
• ArrayList 类在根据索引查询的时候时间复杂度为“O(1)”，而LinkedList时间复杂度为“O(n)”;

面试题:请解释ArrayList 与Vector 区别?

• ArrayList是在JDK1.2提出集合框架的时候定义的，其内部的方法未使用同步处理，属于非线程安全的操作
• Vector是在JDK 1.0的时候提供的类，在JDK 1.2之后增加到集合框架之中，所有方法使用synchronized同步，属于线程安全的操作;
  ArrayList 和Vector 一样都是基于数组实现的动态存储。