[数据结构与算法]List接口实现：ArrayList、LinkedList、Vector

List

List 介绍

list集合每个元素都对应索引，索引从0开始
list集合中元素有序（添加和取出顺序一致），可重复

常用方法

 get 获取
 set 修改
 indexOf 返回在集合中首次出现的位置
 lastIndexOf 返回在集合中最后一次出现的位置
 subList 返回从fromIndex到toIndex位置的子集合，包括前面

List接口练习

 使用 list接口实现类添加三本书，并遍历
 要求：
       1.按价格排序，从低到高（冒泡排序）
 
public class list接口练习 {
    public static void main(String[] args) {

        List list = new ArrayList();

        list.add(new Book("三国演义","罗贯中",50.0));
        list.add(new Book("红楼梦","曹雪芹",100.0));
        list.add(new Book("西游记","吴承恩",30.0));
        list.add(new Book("水浒传","施耐庵",60.0));

        for (Object o : list) {
            System.out.println(o);
        }

        System.out.println("----------------排序后");
        for (Object o : list) {
            System.out.println(o);
        }
    }

    //冒泡排序，从低到高
    public static void sort(List list){
        int size = list.size();
        for (int i = 0; i <size -1; i++) {
            for (int j = 0; j < size -i -1; j++) {
                Book book = (Book) list.get(j);
                Book book1 =(Book) list.get(j + 1);
                if (book.getPrice() > book1.getPrice()){
                    list.set(j,book1);
                    list.set(j+1,book);
                }
            }
        }
    }
}
class Book {...}

ArrayList

1.ArrayList是由 数组 来实现数据存储的
2.ArrayList等同于Vector，ArrayList是线程不安全(执行效率高)；在多线程情况下，不建议使用ArrayList

ArrayList 底层机制 和 源码分析

1.ArrayList中维护了一个Object类型的数组 elementData
2.当创建ArrayList对象时，如果使用的是无参构造器，则初始elementData的容量为0，第一次添加则扩容elementData为10，如需要再次扩容，则扩容elementData的1.5倍
3.如果使用的是指定大小的构造器，则初始elementData容量为指定大小，如果需要扩容，则直接扩容elementData的1.5倍

扩容机制 流程图示

ArrayList add() 扩容机制：如果 需要的最小容量 比 默认容量大，执行grow(int minCapacity)方法扩容

//1 走 ensureCapacityInternal()方法 确认内部容量，此时size默认为0，初始容量elementData默认为0
public boolean add(E e) {
    ensureCapacityInternal(size + 1);  // minCapacity= size + 1 = 1
    elementData[size++] = e;
    return true;
}

//2 先走 calculateCapacity()方法 计算容量，此时初始容量elementData默认为0，需要的最小容量minCapacity为1
private void ensureCapacityInternal(int minCapacity) {
    ensureExplicitCapacity(calculateCapacity(elementData, minCapacity));
}

//3 走calculateCapacity()方法，DEFAULTCAPACITY_EMPTY_ELEMENTDATA默认为0，DEFAULT_CAPACITY默认容量为10
//  if判断：初始容量elementData为0，则返回DEFAULT_CAPACITY=10
private static int calculateCapacity(Object[] elementData, int minCapacity) {
    if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA) {
        return Math.max(DEFAULT_CAPACITY, minCapacity);
    }
    return minCapacity;
}

//4 走ensureExplicitCapacity() 判断是否需要扩容，此时需要的最小容量minCapacity=10，如果需要的最小容量比初始容量elementData要大，执行grow()扩容
private void ensureExplicitCapacity(int minCapacity) {
    modCount++;
    // overflow-conscious code
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

//5 走grow()扩容方法，传入需要的最小容量10，这里初始elementData为0，所以newCapcity还为10
//  如果elementData里面有值，则按elementData的1.5倍进行扩容
private void grow(int minCapacity) {
    // overflow-conscious code
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + (oldCapacity >> 1);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    // minCapacity is usually close to size, so this is a win:
    elementData = Arrays.copyOf(elementData, newCapacity);
}

最后返回到add方法，把add的值添加进行数组

ArrayList源码总结

1.创建无参构造方法时，数组的容量elementData默认为0
2.如果 需要的最小容量（minCapacity）比 默认容量（elementData） 大，则进行扩容操作

Vector

1.Vector底层也是一个对象数组，protected Object[] elementData;
2.Vector是线程同步的，即线程安全，Vector类的操作方法带有 synchronized
3.需要线程同步安全时，需要考虑使用Vector

Vector和ArrayList比较

Vector 源码解析

无参构造器vector初始化后，初始容量为10，后面按2倍扩容

// 1.不传参数，默认走Vector的无参构造器，初始容量给 10
public Vector() {
    this(10);
}
// 2
public Vector(int initialCapacity) {
    this(initialCapacity, 0);
}

Vector 扩容机制

// 1 判断扩容方法 ensureCapacityHelper(最小容量) 

public synchronized boolean add(E e) {
    modCount++;
    ensureCapacityHelper(elementCount + 1);
    elementData[elementCount++] = e;
    return true;
}

// 2 判断条件：当 需要的最小容量比数组容量大时，执行grow()方法扩容，

private void ensureCapacityHelper(int minCapacity) {
    if (minCapacity - elementData.length > 0)
        grow(minCapacity);
}

// 3 grow()方法，扩容到2倍

private void grow(int minCapacity) {
    int oldCapacity = elementData.length;
    int newCapacity = oldCapacity + ((capacityIncrement > 0) ?
                                     capacityIncrement : oldCapacity);
    if (newCapacity - minCapacity < 0)
        newCapacity = minCapacity;
    if (newCapacity - MAX_ARRAY_SIZE > 0)
        newCapacity = hugeCapacity(minCapacity);
    elementData = Arrays.copyOf(elementData, newCapacity);
}

LinkedList

1.LinkedList 底层实现了（ 双向链表 + 双端队列 ）
2.可以添加任意元素（元素可以重复），包括null
3.线程不安全，没有实现同步

LinkedList 底层结构

1.LinkedList 底层维护了一个双向链表
2.LinkedList中维护了两个属性 first 和 last 分别指向首节点和尾节点
3.每个节点（Node对象），里面又维护了prev、next、item三个属性，通过prev指向前一个，通过next指向后一个，实现双向链表
4.所以LinkedList的元素增加和删除，相较于效率较高

双向链表图示

LinkedList 源码解析

LinkedList 创建无参构造器过程；此时，size为0，first、last为Null

//1 走LinkedList的无参构造器 初始化 size=0
    public LinkedList() {}
    
//  transient int size = 0;
    

LinkedList 扩容机制

linkedList.add(12);

//1 走 linkLast(e)方法
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

//2 第一次添加： last=null，l也为null，此时first、last都指向新节点
    多次添加：last不为null，此时新节点的prev指向最后节点，最后节点的next指向新节点
    
    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++;
    }

remove()方法，默认删除首节点

//1 走 removeFirst()方法
public E remove() {
    return removeFirst();
}

//2 第一个节点不为null，执行unlinkFirst(f)方法，删除第一个节点
public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

//3 unlinkFirst() 删除首节点f，先把f的值赋给element，再把f.next赋给一个新next节点，把f的值和next赋为空，
//此时first.next指向新next节点，再把next的prev赋为空，该操作就是把first指向首节点的next，再把首节点的prev赋为空

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node<E> next = f.next;
    f.item = null;
    f.next = null; // help GC
    first = next;
    if (next == null)
        last = null;
    else
        next.prev = null;
    size--;
    modCount++;
    return element;
}

ArrayList 和 LinkedList 比较

如何选择？

1.如果改查多，选择ArrayList
2.如果增删多，选择LinkedList
3.一般大部分都是改查，大部分情况都会选ArrayList