1、简介

LinkedList实现接口如图所示，支持高效删除和插入操作，由于实现了Deque接口，使得LinkedList类也具有队列的特性。LinkedList不是线程安全的，如果想保证线程安全，可以使用Collections类的synchronizedList方法：

List list = Collections.synchronizedList(new LinkedList(……));

2、源码分析

2.1 内部结构

内部私有类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;
        }
    }

2.2 构造方法

空构造方法

public LinkedList() {
}

用已有的集合创建链表的构造方法

public LinkedList(Collection<? extends E> c) {
    this();
    addAll(c);
}

2.3 add方法

add(E e)方法：将元素添加到链表尾部

public boolean add(E e) {
        linkLast(e);//这里就只调用了这一个方法
        return true;
    }

   /**
     * 链接使e作为最后一个元素。
     */
    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++;
    }

add(int index,E e):在指定位置添加元素

public void add(int index, E element) {
        checkPositionIndex(index); //检查索引是否处于[0-size]之间

        if (index == size)//添加在链表尾部
            linkLast(element);
        else//添加在链表中间
            //node(index)去寻找index对应的节点
            linkBefore(element, node(index));
    }

addAll(Collection c):将集合插入到链表尾部

public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

addAll(int index,Collection c):将集合从指定位置开始插入

public boolean addAll(int index, Collection<? extends E> c) {
        //1:检查index范围是否在size之内
        checkPositionIndex(index);

        //2:toArray()方法把集合的数据存到对象数组中
        Object[] a = c.toArray();
        int numNew = a.length;
        if (numNew == 0)
            return false;

        //3：得到插入位置的前驱节点和后继节点
        Node<E> pred, succ;
        //如果插入位置为尾部，前驱节点为last，后继节点为null
        if (index == size) {
            succ = null;
            pred = last;
        }
        //否则，调用node()方法得到后继节点，再得到前驱节点
        else {
            succ = node(index);
            pred = succ.prev;
        }

        // 4：遍历数据将数据插入
        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;
        }

        //如果插入位置在尾部，重置last节点
        if (succ == null) {
            last = pred;
        }
        //否则，将插入的链表与先前链表连接起来
        else {
            pred.next = succ;
            succ.prev = pred;
        }

        size += numNew;
        modCount++;
        return true;
    }    

addFirst(E e):将元素添加到链表头部

 public void addFirst(E e) {
        linkFirst(e);
    }

private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);//新建节点，以头节点为后继节点
        first = newNode;
        //如果链表为空，last节点也指向该节点
        if (f == null)
            last = newNode;
        //否则，将头节点的前驱指针指向新节点，也就是指向前一个元素
        else
            f.prev = newNode;
        size++;
        modCount++;
    }

2.4 其他操作

get(int index):根据指定索引返回数据

public E get(int index) {
        //检查index范围是否在size之内
        checkElementIndex(index);
        //调用Node(index)去找到index对应的node然后返回它的值
        return node(index).item;
    }

获取头节点(index=0)数据方法：

public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }
public E element() {
        return getFirst();
    }
public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }

public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }

区别：getFirst()、element()、peek()、peekFirst()这四个获取头节点方法的区别为对链表为空时的处理，是抛出异常还是返回null，其中getFirst()和element()方法将会在链表为空时，抛出异常。

element()方法内部是使用getFirst()实现的，链表为空时，抛出NoSuchElementException

getLast() 方法在链表为空时，会抛出NoSuchElementException，而peekLast() 则不会，只是会返回 null。

removeLast()在链表为空时将抛出NoSuchElementException，而pollLast()方法返回null。

---