1.浅谈LinkedList

（1）LinkedList底层实现为双向循环链表。链表的特点就是插入、删除数据速度快，而查询数据慢(需要从头开始查找元素)。

（2）采用链表结构，每次添加元素，都会创建新的Node节点并分配空间，所以不存在扩容机制。

（3）LinkedList直接继承AbstractSequentialList，同时实现了List接口，也实现了Deque接口。

2.成员属性

//实际元素个数
transient int size = 0;
//头节点
transient Node<E> first;
/尾节点
transient Node<E> last;

3.LinkedList的构造方法

（1）无参构造方法

public LinkedList() {
    }

（2）有参构造方法

调用无参构造函数，并且把集合中所有的元素添加到LinkedList中。

public LinkedList(Collection<? extends E> c) {
//调用无参构造函数
        this();
//添加集合中所有的元素
        addAll(c);
    }

4.LinkedList的数据存储格式

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;
        }
    }

5.LinkedList的方法

5.1获取元素的方法

getFirst()    获取第一个元素

getLast()    获取最后一个元素

get(int index)   遍历链表，查找指定位置的元素

indexOf(Object o)   查找某一个元素的索引位置

 5.1.1 getFirst()    获取第一个元素 

 public E getFirst() {
// 保存第一个元素为f，注意是final
        final Node<E> f = first;
        if (f == null)
 // 如果没有第一个元素，那么就会抛出异常
            throw new NoSuchElementException();
// 返回第一个元素的item
        return f.item;
    }

 5.1.2 getLast()    获取最后一个元素

public E getLast() {
        // 保存最后一个元素的引用为l
        final Node<E> l = last;
        // 如果为空，抛出错误
        if (l == null)
            throw new NoSuchElementException();
        // 返回item
        return l.item;
    }

5.1.3 get(int index)   

get(int index)通过索引来获取元素,里面是调用了另外一个方法先获取节点，再获取该节点的item,在此之前，做了index安全性校验。 

 public E get(int index) {
        checkElementIndex(index);
        return node(index).item;
    }

在上面的代码中调用了通过索引位置查找节点位置的函数，下面我们来分析一下这个函数,由于底层是链表实现的，所以遍历起来不是很方便，就考虑到位运算，如果索引位置在后面一半，就从后往前遍历查找，否则从前往后遍历。

Node<E> node(int index) {
        // assert isElementIndex(index);
    // size>>1 表示除以2，相当于index小于size的一半
        if (index < (size >> 1)) {
           // 从前面开始遍历，取出first节点，因为中间过程引用会变化，所以不可直接操作first
            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;
        }
    }

5.1.4  indexOf(Object o)

查找某一个元素的索引位置,分为两种情况讨论，如果要查找的元素为空，那么就使用==，否则使用equals()，这也从侧面印证了LinedList实际上是可以存储null元素的。使用计数查找：

public int indexOf(Object o) {
        int index = 0;
       // 如果需要查找null元素
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null)
                    return index;
                index++;
            }
        } else {
           // 查找元素不为空
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

5.2 add方法

boolean add(E e)    添加新元素至链表尾部
void addFirst(E e)    添加新元素至链表头部
void addLast(E e)    添加新元素至链表尾部

void add(int index,E element)将元素插入在指定位置

boolean addAll(Collection<? extends E> c)   批量添加元素至链表尾部

boolean addAll(int index, Collection<? extends E> c)  批量插入元素至指定位置

5.2.1  boolean add(E e)    添加新元素至链表尾部

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

5.2.2  void addFirst(E e)    添加新元素至链表头部

将元素e，添加到第一个节点，公有方法是addFirst()，但是其实内部调用是linkFirst()，这是private方法。

public void addFirst(E e) {
        linkFirst(e);
    }
    private void linkFirst(E e) {
        // 先保存第一个节点
        final Node<E> f = first;
        // 初始化一个新节点，prev是null，next是f（之前的首节点）
        final Node<E> newNode = new Node<>(null, e, f);
        // 更新first为新节点
        first = newNode;
        // 如果之前的第一个节点是空的，那么就说明里面是空的，没有元素
        if (f == null)
            // 最后一个元素也是新加入的元素
            last = newNode;
        else
            // f的prev前置节点的引用更新为新的节点
            f.prev = newNode;
        // 个数增加
        size++;
        // 修改次数增加
        modCount++;
    }

5.2.3  void addLast(E e)    添加新元素至链表尾部

 public void addLast(E e) {
        linkLast(e);
    }
    void linkLast(E e) {
        // 保存最后一个节点的引用
        final Node<E> l = last;
        // 初始化一个节点，前置节点指针引用指向之前的最后一个节点，后续节点的引用是null
        final Node<E> newNode = new Node<>(l, e, null);
        // 将最后一个节点更新
        last = newNode;
        // 如果之前的最后一个节点是null，说明链表是空的
        if (l == null)
            // 新节点同时是第一个节点
            first = newNode;
        else
            // 否则之前的最后一个节点的后续节点引用更新为新的节点
            l.next = newNode;
        // 大小+1
        size++;
        // 修改次数+1
        modCount++;
    }

5.2.4 void add(int index,E element)将元素插入在指定位置 

将元素插入在指定位置,先判断索引位置，如果索引位置是最后一个，那么直接调用在最后添加元素函数即可，否则需要调用另外一个函数，在某个元素前面插入：

public void add(int index, E element) {
       // index校验
        checkPositionIndex(index);
       
       // 索引等于链表大小
        if (index == size)
           // 直接在最后插入元素
            linkLast(element);
        else
           // 在某个节点前插入元素
            linkBefore(element, node(index));
    }

5.2.5 boolean addAll(Collection<? extends E> c)   批量添加元素至链表尾部

往链表里面批量添加元素,里面默认是在最后面批量添加，内部调用的是addAll(int index, Collection<? extends E> c),添加之前会判断索引位置是不是合法的。 然后查找需要插入的位置的前后节点，循环插入。

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

    public boolean addAll(int index, Collection<? extends E> c) {
        // 检查添加位置
        checkPositionIndex(index);

        // 将需要添加的集合转换成为数组
        Object[] a = c.toArray();
        // 获取数组的大小
        int numNew = a.length;
        // 如果数组长度为0，说明没有需要添加的元素，返回false
        if (numNew == 0)
            return false;

        // 插入位置的前节点和后续节点
        Node<E> pred, succ;
        // 如果插入位置索引大小等于链表大小，那么就是在最后插入元素
        if (index == size) {
            // 最后插入元素没有后续节点
            succ = null;
            // 前一个节点就是之前的最后一个节点
            pred = last;
        } else {
            // 查找到索引为index 的节点
            succ = node(index);
            // 获取前一个节点
            pred = succ.prev;
        }
        
        // 循环插入节点
        for (Object o : a) {
            @SuppressWarnings("unchecked") E e = (E) o;
            // 初始化新节点，上一个节点是pred
            Node<E> newNode = new Node<>(pred, e, null);
            // 如果前一个节点是null，那么第一个节点就是新的节点
            if (pred == null)
                first = newNode;
            else
                // 否则pred的next置为新节点
                pred.next = newNode;
            pred = newNode;
        }

        // 如果插入位置没有后续节点，也就是succ为null
        if (succ == null) {
            // 最后一个节点也就是pred，刚刚插入的新节点
            last = pred;
        } else {
            // 加入所有元素之后的最后一个节点的下一个节点指向succ（后续元素）
            pred.next = succ;
            // 插入位置的后续元素的上一个节点引用指向pred
            succ.prev = pred;
        }
       // 大小改变
        size += numNew;
       // 修改次数增加
        modCount++;
        return true;
    }

5.2.6 boolean addAll(int index, Collection<? extends E> c)  批量插入元素至指定位置 

public boolean addAll(int index, Collection<? extends E> c) {
       // 检查索引合法性
        checkPositionIndex(index);
       // 将需要插入的集合转换成为数组
        Object[] a = c.toArray();
       // 数组的长度
        int numNew = a.length;
       // 为0则不需要插入
        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;
           // 初始化节点，前置节点是插入位置的前节点，后续节点为null
            Node<E> newNode = new Node<>(pred, e, null);
           // 如果插入位置前一个节点是null，说明插入位置是链表首
            if (pred == null)
               // 首节点就是新插入的节点
                first = newNode;
            else
               // 前节点的next指向新节点
                pred.next = newNode;
           // 更新插入位置的前一个节点
            pred = newNode;
        }
       // 如果插入位置的后一个节点为空，说明插入位置是链表尾部
        if (succ == null) {
           // 最后一个元素就是插入的元素
            last = pred;
        } else {
           // 将插入的最后一个元素next指向succ
            pred.next = succ;
           // succ的上一个元素指向prev
            succ.prev = pred;
        }
       // 大小更新
        size += numNew;
       // 修改次数改变
        modCount++;
       // 返回成功
        return true;
    }

5.3删除元素的方法

boolean remove(Object o)   删除指定内容的元素
E remove(int index)    删除指定位置的元素
E removeFirst()   删除链表中的头元素
E removeLast()    删除链表中的尾元素

void clear()  清空链表

5.3.1 boolean remove(Object o)   删除指定内容的元素

删除某个元素分为两种情况，元素为null和非null,直接遍历判断，里面真正删除的方法其实是unLink(E e)，成功移除则返回true，注意这里只会移除掉第一个，后续要是还有该节点，不会移除。

 public boolean remove(Object o) {
       // 元素为null
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
           // 元素不为null
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                   // 移除节点
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

 unLink(E e) 的方法  :

E unlink(Node<E> x) {
        // assert x != null;
       // 保存被移除节点的item
        final E element = x.item;
       // 下一个节点
        final Node<E> next = x.next;
       // 上一个节点
        final Node<E> prev = x.prev;
       // 如果前置节点为空，那么首节点就是当前节点了
        if (prev == null) {
            first = next;
        } else {
           // 前一个节点的next置为下一个节点
            prev.next = next;
           // 之前的节点的前一个节点置null
            x.prev = null;
        }
       // 如果next是空的，那么上一个节点就是现在最后一个节点
        if (next == null) {
            last = prev;
        } else {
           // next的上一个节点引用指向prev
            next.prev = prev;
           // 被删除的元素的next置空
            x.next = null;
        }
       // item置空
        x.item = null;
       // 大小改变
        size--;
       // 修改次数增加
        modCount++;
       // 返回被删除的节点里面的item
        return element;
    }

5.3.2 E remove(int index)    删除指定位置的元素

移除指定索引的元素。先通过索引找到节点，再移除指定的节点

 public E remove(int index) {
       // 检查合法性
        checkElementIndex(index);
       // 先找到节点，再移除指定节点
        return unlink(node(index));
    }

5.3.3 E removeFirst()   删除链表中的头元素

删除第一个节点，先获取首节点，判断第一个节点是不是为空，如果为空则证明没有该节点，抛出异常，内部调用的其实是unlinkFirst()。返回值是被移除的节点里面的数值。

public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
  // 移除首节点
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
       // 获取里面的元素
        final E element = f.item;
       // 保存下一个节点
        final Node<E> next = f.next;
       // 将之前的首节点前后节点引用置空，有利于GC
        f.item = null;
        f.next = null; // help GC
       // 首节点更新
        first = next;
       // 如果首节点是空的，那么链表没有元素了，最后一个节点自然也是null
        if (next == null)
            last = null;
        else
           // 否则当前的第一个节点的前置节点置null
            next.prev = null;
       // 链表大小-1
        size--;
       // 修改次数增加
        modCount++;
        return element;
    }

5.3.4  E removeLast()    删除链表中的尾元素

删除最后一个节点，和上面的删除首节点差不多，先取出最后一个节点，判断是否为空，如果为空则抛出异常，否则会调用另一个解除连接的函数unLinkLast()。

public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
       // 保存被移除的节点的item
        final E element = l.item;
       // 获取上一个节点
        final Node<E> prev = l.prev;
       // 前后引用置空，有利于垃圾回收
        l.item = null;
        l.prev = null; // help GC
       // 更新最后一个节点
        last = prev;
       // 如果前置节点为空，那么链表已经没有元素了
        if (prev == null)
            first = null;
        else
           // 否则将上一个节点的next置null
            prev.next = null;
       // 大小该表
        size--;
       // 修改次数增加
        modCount++;
       // 返回被移除的节点的item值
        return element;
    }

5.3.5 void clear() 清空链表

public void clear() {
        for (Node<E> x = first; x != null; ) {
           // 保存下一个
            Node<E> next = x.next;
           // 当前元素置空
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
       // 首节点和尾节点全部置null
        first = last = null;
        size = 0;
        modCount++;
    }

5.4 更新元素

E set(int index,E element)  更新指定索引的位置的元素

5.4.1 E set(int index,E element)  更新指定索引的位置的元素

更新指定索引的位置的元素,首先通过索引查找到该元素，然后修改item值，返回旧的item值。

public E set(int index, E element) {
       // 检查索引是否合法
        checkElementIndex(index);
       // 通过索引查找到节点
        Node<E> x = node(index);
       // 保存旧的值
        E oldVal = x.item;
       // 修改
        x.item = element;
       // 返回旧的元素
        return oldVal;
    }

5.5 queue相关方法 

因为LinkedList也实现了queue接口，所以它肯定也实现了相关的方法。

5.5.1 peek()

获取队列第一个元素

 public E peek() {
       // 拿到第一个元素，final不可变
        final Node<E> f = first;
       // 返回item值
        return (f == null) ? null : f.item;
    }

5.5.2 element()

 也是获取队列第一个元素，里面调用的是getFirst()。

 public E element() {
        return getFirst();
    }

5.5.3 poll()

 移除队列第一个节点元素并返回，里面调用的其实是unlinkFirst()

public E poll() {
       // 获取到第一个元素
        final Node<E> f = first;
       // 移除并返回
        return (f == null) ? null : unlinkFirst(f);
    }

5.5.4 remove()

 移除队列第一个元素,里面调用的是removeFirst()

public E remove() {
        return removeFirst();
    }

5.5.5  offer(E e)

在队列后面添加元素

public boolean offer(E e) {
        return add(e);
    }

5.5.6 offerFirst( E e)

往队列的前面插入元素，其实调用的是addFirst()

public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }

 5.5.7 offerLast(E e)

往队列的后面添加元素,其实调用的是addList()

 public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

5.5.8 peekFirst()

获取第一个节点里面的元素

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

5.5.9 peekLast()

获取最后一个元素里面的元素

 public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }

5.5.10 pollFirst()

获取第一个元素，并且移除它,使用的是unlinkFirst(E e)

public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

5.5.11 pollLast()

获取队列最后一个元素，并且移除它,调用的其实是unlinkLast(E e)

public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

5.5.12 push(E e)

在前面添加元素

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

5.5.13 pop()

取出队首元素

public E pop() {
        return removeFirst();
    }

 5.5.14 removeFirstOccurrence(Object o)

移除元素,从前往后第一次出现的地方移除掉：

public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

5.5.15  removeLastOccurrence(Object o)

移除元素，最后一次出现的地方移除掉,和前面分析的一样，分为两种情况，null和非null。

public boolean removeLastOccurrence(Object o) {
       // 元素为null
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
           // 元素不是null
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

5.6 其他方法 

是否包含某个元素,其实调用的是indexOf()方法，如果返回的索引不为-1，则包含：

 public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

返回大小：

public int size() {
        return size;
    }

 是否为有效元素下标索引，从0到size-1

 private boolean isElementIndex(int index) {
        return index >= 0 && index < size;
    }

是否为有效位置索引，从0到size

private boolean isPositionIndex(int index) {
        return index >= 0 && index <= size;
    }

 获取指定索引位置的ListIterator

public ListIterator<E> listIterator(int index) {
       // 检查合法性
        checkPositionIndex(index);
        return new ListItr(index);
    }

转换成为数组，通过循环实现

public Object[] toArray() {
        Object[] result = new Object[size];
        int i = 0;
       // 循环实现
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;
        return result;
    }

6.总结

1.LinkedList底层是用链表实现的，而且是双向链表，并且实现了Queue接口，可以当成双向队列或者堆栈来使用。也正是因为是链表实现，所以删除元素比较快，但是查找的时候相对较慢。也没有什么扩容，除非就是内存不够了。
2.双向链表，可以从头往尾遍历，也可以从尾部往前遍历。
3.LinkedList继承了AbstractSequentialList，AbstractSequentialList实现了get,set,add,remove等方法。
4.线程不安全