LinkedList

常用方法

//add
boolean add(E e)//在链表尾部添加一个元素，如果成功，返回true，否则返回false； 
void addFirst(E e)//在链表头部插入一个元素； 
addLast(E e)//在链表尾部添加一个元素； 
void add(int index, E element)//在指定位置插入一个元素。

//remove
E remove()//移除链表中第一个元素；
boolean remove(Object o)//移除链表中指定的元素； 
E remove(int index)//移除链表中指定位置的元素；  
E removeFirst()//：移除链表中第一个元素，与remove类似； 
E removeLast()//：移除链表中最后一个元素； 
boolean removeFirstOccurrence(Object o)//移除链表中第一次出现所在位置的元素； 
boolean removeLastOccurrence(Object o)//移除链表中最后一次出现所在位置的元素；

//get
E get(int index)//按照下边获取元素； 
E getFirst()//获取第一个元素； 
E getLast()//获取第二个元素；
--------------------------------------------
//掌握上面一组增删查就够用了
//offer
boolean offer(E e)//与add一样 
boolean offerFirst(E e)//与addFirst一样
boolean offerLast(E e)//与addLast一样

//push pop poll
void push(E e)//与addFirst一样
E pop()//与removeFirst一样
E poll()//查询并移除第一个元素
//链表为空时，poll返回null, pop产生异常

//peek
E peek()//获取第一个元素，但是不移除； 
E peekFirst()//获取第一个元素，但是不移除； 
E peekLast()//获取最后一个元素，但是不移除；
---------------------------------------------
//其他 
int size();
boolean isEmpty();
boolean contains(Object o);//判断是否包含某元素
void set(int index,E element);//修改指定位置元素
List subList(int fromIndex,int toIndex);//返回[,from,to)区间的新链表，不会修改原链表
clear();//清空

源码分析

继承于AbstractSequentialList的双向链表:可以被当作堆栈、队列或双端队列进行操作。
实现 List 接口，能进行队列操作。

实现 Deque 接口，能将LinkedList当作双端队列使用

1
2
3

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable{...}

基于双向链表实现，使用 Node 存储链表节点信息。

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

每个链表存储了 first 和 last 指针：

1 2	transient Node<E> first; transient Node<E> last;

LinkedList的源码也就是普通的链表操作，没有什么难点

//构造函数
//空参构造
public LinkedList() {
}
//传入其他Collection转换成LinkedList
public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

public boolean addAll(Collection<? extends E> c) {
    return addAll(size, c);
}
//转换方式就是先变成数组类型，再将数组中的元素依次创建结点放在List中
public boolean addAll(int index, Collection<? extends E> c) {
    checkPositionIndex(index);

    Object[] a = c.toArray();
    int numNew = a.length;
    if (numNew == 0)
        return false;

    Node<E> pred, succ;
    if (index == size) {
        succ = null;
        pred = last;
    } else {
        succ = node(index);
        pred = succ.prev;
    }

    for (Object o : a) {
        @SuppressWarnings("unchecked") E e = (E) o;
        Node<E> newNode = new Node<>(pred, e, null);
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        pred = newNode;
    }

    if (succ == null) {
        last = pred;
    } else {
        pred.next = succ;
        succ.prev = pred;
    }

    size += numNew;
    modCount++;
    return true;
}
//链表存储了first last指针，所以对头尾结点增删查非常好实现

与 ArrayList 的比较

ArrayList 基于动态数组实现，LinkedList 基于双向链表实现；
ArrayList 支持随机访问，LinkedList 不支持；
LinkedList 在任意位置添加删除元素更快

遍历方法及效率

Linkedlist不支持随机访问，所以使用访问next的方式便利更高效。ArrayList使用for随机访问更高效。foreach本质上是使用iterator实现的。

Linkedlist : foreach > iterator >for
ArrayList ：for >foreach >iterator

参考：https://www.cnblogs.com/aoguren/p/4771589.html

ArrayList

常用方法

//创建
ArrayList<String> list = new ArrayList<String>();
//指定容量大小
ArrayList<Integer> list = new ArrayList<Integer>(7);

//add
boolean add(Element e)//增加指定元素到链表尾部.
void add(int index, Element e)//增加指定元素到链表指定位置

//remove
E remove(int index)
E remove(Object o)

//get
E get(int index)获取链表中指定位置处的元素

//set
E set(int index, E element)//将链表中指定位置上的元素替换成新元素。

Object[] toArray() //即将链表转换为一个数组

int indexOf(Object o)//返回元素在链表中第一次出现的位置，没有返回-1
int lastIndexOf(Object o)//返回元素在链表中最后一次出现的位置，没有返回-1

boolean contains(Object o)//如果链表包含指定元素，返回true.
boolean isEmpty()
int size()
void clear()

参考：实例讲解ArrayList用法

源码分析

ArrayList 继承了AbstractList，实现了List。它是一个数组队列，提供了相关的添加、删除、修改、遍历等功能。
实现了Cloneable 接口，即覆盖了函数 clone()，能被克隆。
实现java.io.Serializable 接口，这意味着ArrayList支持序列化，能通过序列化去传输。

实现了 RandomAccess 接口，因此支持随机访问。

1 2	public class ArrayList<E> extends AbstractList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable{}

构造方法(3种)

private static final int DEFAULT_CAPACITY = 10;
//空参构造,实际上初始化赋值一个空数组，当真正对数组添加元素时，才真正分配大小=10
public ArrayList() {
    //private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};
    this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
}

//创建ArrayList时传入初始容量
public ArrayList(int initialCapacity) {
    //创建指定大小的数组
    if (initialCapacity > 0) {
        this.elementData = new Object[initialCapacity];
    } else if (initialCapacity == 0) {
        this.elementData = EMPTY_ELEMENTDATA;
    } else {
        throw new IllegalArgumentException("Illegal Capacity: "+
                                            initialCapacity);
    }
}

//支持传入一个集合，将集合转换成ArrayList类型
public ArrayList(Collection<? extends E> c) {
    elementData = c.toArray();
    if ((size = elementData.length) != 0) {
        // defend against c.toArray (incorrectly) not returning Object[]
        // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
        if (elementData.getClass() != Object[].class)
            elementData = Arrays.copyOf(elementData, size, Object[].class);
    } else {
        // replace with empty array.
        this.elementData = EMPTY_ELEMENTDATA;
    }
}

插入数据

private void add(E e, Object[] elementData, int s) {
    //数组没有空间了就进行扩容
    if (s == elementData.length)
        //扩容后的大小是之前大小的1.5倍
        elementData = grow();
    elementData[s] = e;
    size = s + 1;
}
//在数组末尾插入数据
public boolean add(E e) {
    modCount++;
    add(e, elementData, size);
    return true;
}
//指定位置插入数据
public void add(int index, E element) {
    //检测下标是否越界
    rangeCheckForAdd(index);
    modCount++;
    final int s;
    Object[] elementData;
    if ((s = size) == (elementData = this.elementData).length)
        elementData = grow();
    //把index之后的所有元素向后移一位
    //elementData 源数组 index:源数组中起始位置
    //elementData 目标数组 index:目标数组中起始位置
    //s - index:要复制的数组元素的数量
    System.arraycopy(elementData, index,
                        elementData, index + 1,
                        s - index);
    elementData[index] = element;
    size = s + 1;
}

扩容(重点)

插入数据时没有空间了就进行扩容。

使用 grow() 方法进行扩容，新容量的大小为 oldCapacity + (oldCapacity >> 1) ，也就是旧容量的 1.5 倍。

扩容操作需要调用 Arrays.copyOf() 把原数组整个复制到新数组中，这个操作代价很高，因此最好在创建ArrayList 对象时就指定大概的容量大小，减少扩容操作的次数。

private Object[] grow(int minCapacity) {
    //elementData:要复制的数组，newCapacity(minCapacity)：复制的长度
    return elementData = Arrays.copyOf(elementData,
                                        newCapacity(minCapacity));
}

private Object[] grow() {
    return grow(size + 1);
}

private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        int newCapacity = oldCapacity + (oldCapacity >> 1);
        if (newCapacity - minCapacity <= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity < 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        return (newCapacity - MAX_ARRAY_SIZE <= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }

删除数据

需要调用 System.arraycopy() 将 index+1 后面的元素都复制到 index 位置上，该操作的时间复杂度为 O(N)，可以看出ArrayList 删除元素的代价是非常高的。

ArrayList源码大量使用了System.arrayCopy()和Arrays.copyOf()方法

copyOf()内部实际上调用了System.arrayCopy()方法

//固定位置删除，返回要删除的元素
public E remove(int index) {
    Objects.checkIndex(index, size);

    modCount++;
    E oldValue = elementData(index);

    int numMoved = size - index - 1;
    //向前移动一位
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
    //最后一位置空，size减小1
    elementData[--size] = null; // clear to let GC do its work

    return oldValue;
}
//删除指定元素
public boolean remove(Object o) {
    if (o == null) {
        for (int index = 0; index < size; index++)
            if (elementData[index] == null) {
                fastRemove(index);
                return true;
            }
    } else {
        for (int index = 0; index < size; index++)
            if (o.equals(elementData[index])) {
                fastRemove(index);
                return true;
            }
    }
    return false;
}

private void fastRemove(int index) {
    modCount++;
    int numMoved = size - index - 1;
    if (numMoved > 0)
        System.arraycopy(elementData, index+1, elementData, index,
                            numMoved);
    elementData[--size] = null; // clear to let GC do its work
}

遍历时删除元素

对集合进行遍历的时候，将集合的大小改变了就会报错

//会报错 java.util.ConcurrentModificationException
ArrayList <Integer> list=new ArrayList();
list.add(10);
list.add(11);
list.add(12);
list.add(13);
list.add(14);
list.add(15);
list.add(16);
list.add(17);
for(Integer i: list){
    if(i==13){
        list.remove(i);
    }
}
//同样报错
Iterator<Integer>it=list.iterator();
while(it.hasNext()){
    Integer num=it.next();
    if(num==13){
        list.remove(num);
    }
}
//用迭代器删除可以解决
Iterator<Integer>it=list.iterator();
while(it.hasNext()){
    Integer num=it.next();
    if(num==13){
        //区别点
        it.remove(num);
    }
}

ensureCapacity方法

大量添加元素之前最好先使用ensureCapacity()方法。可以减少扩容次数，提高效率

public void ensureCapacity(int minCapacity) {
        if (minCapacity > elementData.length
            && !(elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA
                 && minCapacity <= DEFAULT_CAPACITY)) {
            modCount++;
            grow(minCapacity);
        }
    }

参考：https://github.com/Snailclimb/JavaGuide/blob/master/docs/java/collection/ArrayList-Grow.md

与Vector区别

Vector 每次扩容请求其大小的 2 倍空间，而 ArrayList 是 1.5 倍。
Vector是线程安全的

Vector(弃用)

实现与 ArrayList 类似，但是使用了 synchronized 进行同步,因此开销就比 ArrayList 要大，访问速度更慢。最好使用 ArrayList 而不是 Vector，因为同步操作完全可以由程序员自己来控制；

替代方案1

使用Collections.synchronizedList(); 得到一个线程安全的 ArrayList。

1 2	List<String> list = new ArrayList<>(); List<String> synList = Collections.synchronizedList(list);

替代方案2

可以使用 java.util.concurrent 并发包下的 CopyOnWriteArrayList 类

1	List<String> list = new CopyOnWriteArrayList<>();

CopyOnWriteArrayList

读写分离

写操作在一个复制的数组上进行，读操作还是在原始数组中进行，读写分离，互不影响。
写操作需要加锁，防止并发写入时导致写入数据丢失。

写操作结束之后需要把原始数组指向新的复制数组。

public boolean add(E e) {
final ReentrantLock lock = this.lock;
lock.lock();
try {
Object[] elements = getArray();
int len = elements.length;
Object[] newElements = Arrays.copyOf(elements, len + 1);
newElements[len] = e;
setArray(newElements);
return true;
} finally {
lock.unlock();
}
}
final void setArray(Object[] a) {
array = a;
}

@SuppressWarnings("unchecked")
private E get(Object[] a, int index) {
  return (E) a[index];
}

适用场景

CopyOnWriteArrayList 在写操作的同时允许读操作，大大提高了读操作的性能，因此很适合读多写少的应用场景。
但是 CopyOnWriteArrayList 有其缺陷：

内存占用：在写操作时需要复制一个新的数组，使得内存占用为原来的两倍左右；
数据不一致：读操作不能读取实时性的数据，因为部分写操作的数据还未同步到读数组中。

所以 CopyOnWriteArrayList 不适合内存敏感以及对实时性要求很高的场景。

为什么JUC包里没有并发的ArrayList实现

主要原因：很难去开发一个通用并且没有并发瓶颈的线程安全的List。

像ConcurrentHashMap这样的类的真正价值并不是它们保证了线程安全。而在于它们在保证线程安全的同时不存在并发瓶颈。举个例子，ConcurrentHashMap采用了锁分段技术和弱一致性的Map迭代器去规避并发瓶颈。

像ArrayList这样的数据结构，你不知道如何去规避并发的瓶颈。拿contains() 这样一个操作来说，当你进行搜索的时候如何避免锁住整个list？

另一方面，Queue和Deque(基于LinkedList)有并发的实现是因为他们的接口相比List的接口有更多的限制，这些限制使得实现并发成为可能。

CopyOnWriteArrayList是一个有趣的例子，它规避了只读操作（如get/contains）并发的瓶颈，但是它为了做到这点，在修改操作中做了很多工作和修改可见性规则。此外，修改操作还会锁住整个List，因此这也是一个并发瓶颈。所以从理论上来说，CopyOnWriteArrayList并不算是一个通用的并发List。

Lichord

Java_容器_List

LinkedList

常用方法

源码分析

与 ArrayList 的比较

遍历方法及效率

ArrayList

常用方法

源码分析

构造方法(3种)

插入数据

扩容(重点)

删除数据

遍历时删除元素

ensureCapacity方法

与Vector区别

Vector(弃用)

替代方案1

替代方案2

CopyOnWriteArrayList

读写分离

适用场景

为什么JUC包里没有并发的ArrayList实现