老规矩我们先看下LinkedList的继承关系图:


①.从图中我可以看出LinkedList实现了Deque接口，可以将LinkedList当做队列使用;实现了cloneable表示能被克隆，实现了Serializable接口表示支持序列化.
②.LinkedList基于双向链表，实现了所有List操作并允许所有元素包括null值，它可以被当作双端队列.
③.LinkedList顺序访问非常高效，而随机访问效率很低.
④.LinkedList线程不安全，可以用Collections.synchronizedList使其线程安全.

源码分析LinkedList字段    /**     * 序列号     */    private static final long serialVersionUID = 876323262645176354L;         /**     * LinkedList长度，不可序列化     */    transient int size = 0;        /**     * 首结点     */    transient Node first;        /**     * 尾结点     */    transient Node last;复制代码结点类:
    /**     * 结点类     */    private static class Node {        // 当前结点所包含的值        E item;        // 后继结点        Node next;        // 前驱结点        Node prev;        //结点构造方法        Node(Node prev, E element, Node next) {            this.item = element;            this.next = next;            this.prev = prev;        }    } 复制代码>构造方法    /**     * 无参构造     */    public LinkedList() {    }         /**     * 参数Collection的构造方法     */    public LinkedList(Collection c) {        // 调用无参构造函数        this();        // 添加集合中所有的元素        addAll(c);    } 复制代码CRUDCreateLinkedList新增(public)有如下几个方法:
public boolean add(E e);
public boolean offer(E e);
public void addLast(E e);
public boolean offerLast(E e);

    /**     * 末尾插入元素     */    public boolean add(E e) {        linkLast(e);        return true;    }        public boolean offer(E e) {        // 尾插元素        return add(e);    }        /**     * 尾插元素     */    public void addLast(E e) {        linkLast(e);    }        /**     * 尾插元素     */     public boolean offerLast(E e) {        addLast(e);        return true;    }        /**     * 尾插元素     */    void linkLast(E e) {        //获取当前尾结点        final Node l = last;        //定义新结点，其前驱结点为尾结点，值为e，后继结点为null        final Node newNode = new Node<>(l, e, null);        //将刚定义的新节点设为尾结点        last = newNode;        //若原尾结点为null，即原链表为null，则链表首结点也为newNode        if (l == null)            first = newNode;        //若不是原尾结点的后继设为newNode        else              l.next = newNode;        长度+1            size++;        改变次数+1        modCount++;    }复制代码public void add(int index, E element);
public boolean addAll(Collection<? extends E> c);
public boolean addAll(int index, Collection<? extends E> c);

    /**     * 指定位置插入元素     */    public void add(int index, E element) {        // 判断索引是否越界        checkPositionIndex(index);        // 若指定位置在尾部，则尾插元素;若不在调通用方法指定位置插入        if (index == size)            linkLast(element);        else            linkBefore(element, node(index));    }    /**     * 尾插集合所有元素     */    public boolean addAll(Collection c) {        return addAll(size, c);    }    /**     * 指定位置插入集合所有元素     */    public boolean addAll(int index, Collection c) {        //判断索引是否越界        checkPositionIndex(index);        //将集合转为数组        Object[] a = c.toArray();        //获取数组长度        int numNew = a.length;        //若数组长度为0，即没有要插入的元素返回false        if (numNew == 0)            return false;        //succ为原index位置上结点，pred为succ前驱结点            Node pred, succ;        //若是尾部，succ为null，pred为尾结点        if (index == size) {            succ = null;            pred = last;        //若不是succ为index位置结点，pred为其前驱结点            } else {            succ = node(index);            pred = succ.prev;        }        //for循环遍历集合        for (Object o : a) {            @SuppressWarnings("unchecked") E e = (E) o;           //定义一个新结点，其前驱结点为pred，结点值为e，后继结点为null            Node newNode = new Node<>(pred, e, null);           //若前驱结点为null，则将newNode设为首结点            if (pred == null)                first = newNode;            else            //若存在前驱结点，将其后继赋为newNode                pred.next = newNode;            类似于迭代器的next，将newNode指向下一个需插入结点位置的前驱                pred = newNode;        }        //若是尾插，则最后添加元素为尾结点        if (succ == null) {            last = pred;        } else {         //若不是，最后添加的结点后继指向原index位置上的succ            pred.next = succ;        //succ的前驱指向最后添加的结点                succ.prev = pred;        }        //长度+numNew        size += numNew;        modCount++;        return true;    }        private void checkPositionIndex(int index) {        //若index不在[0，size]区间内则抛越界异常        if (!isPositionIndex(index))            throw new IndexOutOfBoundsException(outOfBoundsMsg(index));    }    private boolean isPositionIndex(int index) {        return index >= 0 && index <= size;    }    /**     * 获取指定位置结点     */    Node node(int index) {        // 若指定索引小于LinkedList长度一半，则从首结点开始遍历;若不是从尾结点开始遍历        if (index < (size >> 1)) {            Node x = first;            for (int i = 0; i < index; i++)                x = x.next;            return x;        } else {            Node x = last;            for (int i = size - 1; i > index; i--)                x = x.prev;            return x;        }    }    /**     * 中间插入     */    void linkBefore(E e, Node succ) {        // 获取原索引上元素前驱结点pred         final Node pred = succ.prev;        // 定义新结点，其前驱结点为pred，结点值为e，后继为succ        final Node newNode = new Node<>(pred, e, succ);        // 将succ的前驱结点设为newNode        succ.prev = newNode;        // pred为空，即succ为原首结点，那么将新定义的newNode设为新首结点        if (pred == null)            first = newNode;        else        //否则pred后继结点设为newNode            pred.next = newNode;        //长度+1            size++;        //修改次数+1        modCount++;    }复制代码public boolean offerFirst(E e);
public void addFirst(E e);
public void push(E e);

    /**     * 头插指定元素     */    public void addFirst(E e) {        linkFirst(e);    }    public void push(E e) {        addFirst(e);    }    /**     * 头插指定元素     */    public boolean offerFirst(E e) {        addFirst(e);        return true;    }    /**     * 头插     */    private void linkFirst(E e) {        //获取当前首结点        final Node f = first;        //定义新结点，前驱为null，结点值为e，后驱为f        final Node newNode = new Node<>(null, e, f);        //将newNode设为首结点        first = newNode;        //若首结点为null，尾结点设为newNode，若不是原首结点前驱设为newNode        if (f == null)            last = newNode;        else            f.prev = newNode;        长度+1            size++;        modCount++;    }复制代码RetrieveLinkedList查询(public)有如下几个方法:
public boolean contains(Object o);
public int size();
public E element();
public E get(int index);
public E getFirst();
public E getLast();
public int indexOf(Object o);
public int lastIndexOf(Object o);
public int size();
public E peek();
public E peekFirst();
public E peekLast();

    /**     * 查询是否包含此元素     */    public boolean contains(Object o) {        return indexOf(o) != -1;    }        /**     * 循环从头遍历找出指定元素索引，-1表示不存在该元素     */    public int indexOf(Object o) {        int index = 0;        if (o == null) {            for (Node x = first; x != null; x = x.next) {                if (x.item == null)                    return index;                index++;            }        } else {            for (Node x = first; x != null; x = x.next) {                if (o.equals(x.item))                    return index;                index++;            }        }        return -1;    }        /**     * 查询LinkedList长度     */    public int size() {        return size;    }        /**     * 获取首结点值，若链表为空会抛异常     */    public E element() {        return getFirst();    }        /**     * 获取首结点值，若链表为空会抛异常     */    public E getFirst() {        final Node f = first;        if (f == null)            throw new NoSuchElementException();        return f.item;    }        /**     * 获取首结点值，若无首结点返回null     */    public E peek() {        final Node f = first;        return (f == null) ? null : f.item;    }        /**     * 获取首结点值，若无首结点返回null     */    public E peekFirst() {        final Node f = first;        return (f == null) ? null : f.item;     }             /**     * 获取指定索引元素     */    public E get(int index) {        //校验是否越界        checkElementIndex(index);        return node(index).item;    }        /**     * 获取尾结点，，若链表为空会抛异常     */    public E getLast() {        final Node l = last;        if (l == null)            throw new NoSuchElementException();        return l.item;    }        /**     * 获取尾结点值，若链表为空返回null     */     public E peekLast() {        final Node l = last;        return (l == null) ? null : l.item;    }        /**     * 循环从尾遍历找出指定元素索引，-1表示不存在该元素     */    public int lastIndexOf(Object o) {        int index = size;        if (o == null) {            for (Node x = last; x != null; x = x.prev) {                index--;                if (x.item == null)                    return index;            }        } else {            for (Node x = last; x != null; x = x.prev) {                index--;                if (o.equals(x.item))                    return index;            }        }        return -1;    }复制代码Updatepublic E set(int index, E element);

    /**     * 修改指定位置结点值，返回被替换结点值     */    public E set(int index, E element) {        //校验index是否越界        checkElementIndex(index);        //获取当前index位置上结点        Node x = node(index);        //获取此结点值        E oldVal = x.item;        //修改结点值        x.item = element;        //返回被替换结点值        return oldVal;    } 复制代码Deletepublic E remove();
public E remove(int index);
public boolean remove(Object o);
public E removeFirst();
public boolean removeFirstOccurrence(Object o);
public E removeLast();
public boolean removeLastOccurrence(Object o);
public void clear();
public E poll();
public E pollFirst();
public E pop();

    /**     * 获取并删除首结点值，若链表为空则抛出异常     */    public E remove() {        return removeFirst();    }         public E pop() {        return removeFirst();    }        public E removeFirst() {        final Node f = first;        if (f == null)            throw new NoSuchElementException();        return unlinkFirst(f);    }        /**     * 获取并删除首结点，若链表为空返回null     */    public E poll() {        final Node f = first;        return (f == null) ? null : unlinkFirst(f);    }        public E pollFirst() {        final Node f = first;        return (f == null) ? null : unlinkFirst(f);    }        private E unlinkFirst(Node f) {        //获取首结点值        final E element = f.item;        //获取首结点后继        final Node next = f.next;        //删除首结点        f.item = null;        f.next = null; // help GC        //原后继结点设为首结点        first = next;        //若后继结点为null，尾结点设为null;若不是后继结点的前驱结点设为null        if (next == null)            last = null;        else            next.prev = null;        //长度-1            size--;        modCount++;        return element;    }        /**     * 删除指定位置结点     */    public E remove(int index) {        //校验index是否越界        checkElementIndex(index);        return unlink(node(index));    }        /**     * 删除指定结点     */    E unlink(Node x) {        // 获取指定结点值        final E element = x.item;        // 获取指定结点后继        final Node next = x.next;        // 获取指点结点前驱        final Node prev = x.prev;        // 若前驱为null，则后继结点设为首结点        if (prev == null) {            first = next;        } else {        //若不是，指定结点后继结点设为指定结点前驱结点后继，指定结点的前驱设为null            prev.next = next;            x.prev = null;        }        //若后继结点为空，则前驱结点设为尾结点        if (next == null) {            last = prev;        } else {        //若不是，指定结点前驱结点设为指定结点后继结点前驱，指定结点的后继设为null            next.prev = prev;            x.next = null;        }        //指定结点值设为null        x.item = null;        //长度-1        size--;        modCount++;        //返回被删除的结点值        return element;    }        /**     * for循环从头遍历，删除第一次出现的指定元素     */    public boolean remove(Object o) {        if (o == null) {            for (Node x = first; x != null; x = x.next) {                if (x.item == null) {                    unlink(x);                    return true;                }            }        } else {            for (Node x = first; x != null; x = x.next) {                if (o.equals(x.item)) {                    unlink(x);                    return true;                }            }        }        return false;    }        /**     * 删除从头开始第一出现的指定结点     */    public boolean removeFirstOccurrence(Object o) {        return remove(o);    }        /**     * 删除尾结点，若链表为空抛异常     */    public E removeLast() {        final Node l = last;        if (l == null)            throw new NoSuchElementException();        return unlinkLast(l);    }        /**     * 删除尾结点，若链表为空返回null     */    public E pollLast() {        final Node l = last;        return (l == null) ? null : unlinkLast(l);    }        /**     * 删除尾结点     */    private E unlinkLast(Node l) {        // 获取尾结点值        final E element = l.item;        // 获取尾结点前驱        final Node prev = l.prev;        // 删除尾结点        l.item = null;        l.prev = null; // help GC        // 将原尾结点前驱设为尾结点        last = prev;        // 若原尾结点的前驱结点为空，则首结点设为null        if (prev == null)            first = null;        else        //若不为null，原原尾结点的前驱结点的后继结点设为null            prev.next = null;        //长度-1            size--;        modCount++;        return element;    }        /**     * 删除最后出现的结点     */    public boolean removeLastOccurrence(Object o) {        if (o == null) {            for (Node x = last; x != null; x = x.prev) {                if (x.item == null) {                    unlink(x);                    return true;                }            }        } else {            for (Node x = last; x != null; x = x.prev) {                if (o.equals(x.item)) {                    unlink(x);                    return true;                }            }        }        return false;    }        /**     * 清空LinkedList     */    public void clear() {        //循环遍历LinkedList，删除所有结点        for (Node x = first; x != null; ) {            Node next = x.next;            x.item = null;            x.next = null;            x.prev = null;            x = next;        }        //首尾结点置空        first = last = null;        //长度设为0        size = 0;        modCount++;    }复制代码转换数组    public Object[] toArray() {        // 声明一个LinkedList长度的数组        Object[] result = new Object[size];        int i = 0;        //for遍历一一添加        for (Node x = first; x != null; x = x.next)            result[i++] = x.item;        return result;    } 复制代码手撕简单实现public class LinkedList {    private int size;    private Node first;    private Node last;    public LinkedList() {    }    public void add(Object obj) {        final Node lastNode = last;        Node newNode = new Node(lastNode, obj, null);        if (lastNode == null) {            first = newNode;        } else {            lastNode.next = newNode;        }        last = newNode;        size++;    }        public void add(int index, Object obj) {        final Node node = getNode(index);        final Node preNode = node.pre;        if (index == size) {            add(obj);            return;        }        Node newNode = new Node(preNode, obj, node);        node.pre = newNode;        if (preNode == null) {            first = newNode;        } else {            preNode.next = newNode;        }        size++;    }    public Object get(int index) {        return getNode(index).item;    }    private Node getNode(int index) {        if (index < 0 || index >= size) {            throw new IndexOutOfBoundsException("越界");        }        if (index < size << 1) {            Node node = first;            for (int i = 0; i < index; i++) {                node = node.next;            }            return node;        } else {            Node node = last;            for (int i = size - 1; i > index; i--) {                node = node.pre;            }            return node;        }    }    public void set(int index, Object obj) {        Node node = getNode(index);        node.item = obj;    }    public void remove(int index) {        final Node node = getNode(index);        final Node preNode = node.pre;        final Node nextNode = node.next;        if (preNode == null) {            first = nextNode;        } else {            preNode.next = nextNode;            node.pre = null;        }        if(nextNode == null){            last = preNode;            } else {            nextNode.pre = preNode;            node.next = null;        }        node.item = null;        size--;    }    private static class Node {        private Object item;        private Node pre;        private Node next;        public Node(Node pre, Object item, Node next) {            this.item = item;            this.pre = pre;            this.next = next;        }    }} 复制代码结语
①.ArrayList相当于动态数组，LinkedList相当于双向链表可以被当作堆栈、队列、双端队列
②.ArrayList支持随机访问，而LinkedList需要一步步移动找到索引位置
③.ArrayList新增可能需要扩容预留内存，LinkedList不需要
④.ArrayList插入删除操作(非尾部)需要数组拷贝，LinkedList只需要修改结点的前驱后继


【转载】仅作分享，侵删
作者：午夜12点
链接：https://juejin.im/post/5abb3ad46fb9a028cd452389