Java的LinkedList源码（一）

NullPointer

只贴出了一部分源码，并不是所有方法的源码，后续更新get和addAll，大部分代码现在已贴出，如有不对的地方还请指正。
package collection;

import java.util.AbstractSequentialList;
import java.util.Collection;
import java.util.ConcurrentModificationException;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import java.util.ListIterator;
import java.util.NoSuchElementException;
import java.util.Queue;

public class LinkedList<E>
    extends AbstractSequentialList<E>
    implements List<E>, Deque<E>, Cloneable, java.io.Serializable
{
    /**
     * LinkedList的长度
     * transient：只能用来修饰字段，在对象序列化的过程中，带有此修饰符修饰的字段是不会被序列化的
     * 例如：User类有userName和transient password，那么序列化User类的时候password是不会被序列化的，
     * 所以反序列化拿出password也是null
     */
    transient int size = 0;

    /**
     * 指针头部
     */
    transient Node<E> first;

    /**
     * 指针尾部
     */
    transient Node<E> last;

    /**
     * 空构造器
     */
    public LinkedList() {
    }

    /**
     * 在链表头部插入元素
     */
    private void linkFirst(E e) {
            //先保存当前头节点
        final Node<E> f = first;
        //创建一个新节点，此新节点的上一个节点为null，下一个节点为当前头节点
        final Node<E> newNode = new Node<>(null, e, f);
        //让first指向新节点（更新头节点，这样可以保证对链表进行更改操作时first永远是第一个节点）
        first = newNode;
        //如果链表为null，则将last指向这唯一的新节点
        if (f == null)
            last = newNode;
        else //如果链表不为null，则将链表原来头节点的上一个元素指向新节点
            f.prev = newNode;
        size++;
        modCount++;
    }

    /**
     * 在链表尾部添加元素
     */
    void linkLast(E e) {
            //先保存当前尾节点
        final Node<E> l = last;
        //创建新节点，新节点的前驱(上一个节点)为当前尾节点，后驱为null
        final Node<E> newNode = new Node<>(l, e, null);
        //将链表尾节点指向新节点（更新尾节点，这样可以保证对链表进行更改操作时last永远是最后一个节点）
        last = newNode;
        //如果链表尾节点（指向新节点之前）为null，则将链表头节点指向新节点
        if (l == null)
            first = newNode;
        else //否则将链表尾节点（指向新节点之前）的上下一个节点指向新节点
            l.next = newNode;
        size++;
        modCount++;
    }

    /**
     * 向链表中间插入元素
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        final Node<E> pred = succ.prev;
        final Node<E> newNode = new Node<>(pred, e, succ);
        succ.prev = newNode;
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        size++;
        modCount++;
    }

    /**
     * 移除链表头元素, f:链表头元素，从其他方法调用传参而来
     * f不可为null，调用此方法的地方都已判断
     */
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
            //将element指向链表头节点的元素值
        final E element = f.item;
        //将next指向链表头节点的下一个节点
        final Node<E> next = f.next;
        //将链表头节点赋值为null
        f.item = null;
        //将链表头节点的下一个节点指向为null，有助于GC回收
        f.next = null; // help GC
        //将链表头节点first指向为next（目的是为了数据的正确性，删除此元素，要保证first指向下一个元素，不能指向当前删除的这个）
        first = next;
        //如果链表只有1个元素，则将last指向null，变成空链表
        if (next == null)
            last = null;
        else //否则将链表的上一个元素指向null
            next.prev = null;
        //长度减1
        size--;
        modCount++;
        //返回被移除的元素
        return element;
    }

    /**
     * 移除链表尾元素, l:链表尾元素，从其他方法调用传参而来
     * l不可为null，调用此方法的地方都已判断
     */
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
            //将链表尾节点的元素值赋给element
        final E element = l.item;
        //找到链表尾节点的上一个节点
        final Node<E> prev = l.prev;
        l.item = null;
        l.prev = null; // help GC
        //last指向前一个元素
        last = prev;
        //若前一个元素为null，则证明链表只有l这一个元素，则将first设置为null，变成空链表
        if (prev == null)
            first = null;
        else //否则删除此元素
            prev.next = null;
        size--;
        modCount++;
        //返回删除的这个元素
        return element;
    }

    /**
     * 从链表中间删除节点
     */
    E unlink(Node<E> x) {
        // assert x != null;
            //找到当前节点本身，上一个节点和下一个节点
        final E element = x.item;
        final Node<E> next = x.next;
        final Node<E> prev = x.prev;

        //前驱为空，说明删除的是头节点，first要指向下一个节点
        if (prev == null) {
            first = next;
        } else { //否则前驱节点的后继节点变为当前删除节点的下一个节点
            prev.next = next;
            x.prev = null;
        }
        //后驱为空，说明删除的是尾节点，last要指向前一个节点
        if (next == null) {
            last = prev;
        } else { //否则后驱节点的上一个节点变为当前删除的上一个节点
            next.prev = prev;
            x.next = null;
        }
        //将此元素设置为null
        x.item = null;
        size--;
        modCount++;
        //返回删除的元素
        return element;
    }

    /**
     * 获取链表第一个节点
     */
    public E getFirst() {
            //将节点f指向链表头节点
        final Node<E> f = first;
        //如果链表头节点为null，则抛出没有此元素的异常，否则返回此元素
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    /**
     * 获取链表最后一个节点
     */
    public E getLast() {
            //将节点l指向链表尾节点
        final Node<E> l = last;
        //如果链表尾节点为null，则抛出没有此元素的异常，否则返回此元素
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

    /**
     * 移除链表头节点
     */
    public E removeFirst() {
            //将节点f指向链表头节点
        final Node<E> f = first;
        //如果链表头节点为null，则抛出没有此元素的异常，否则移除此元素，并返回移除的元素
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    /**
     * 移除链表尾节点
     */
    public E removeLast() {
            //将节点f指向链表尾节点
        final Node<E> l = last;
        //如果链表尾节点为null，则抛出没有此元素的异常，否则移除此元素，并返回移除的元素
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

    /**
     * 向链表头部插入节点
     */
    public void addFirst(E e) {
        linkFirst(e);
    }

    /**
     * 向链表尾部插入节点
     */
    public void addLast(E e) {
        linkLast(e);
    }

    /**
     * 判断元素是否在链表中。true：在。false：不在
     */
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

    /**
     * 返回链表长度
     */
    public int size() {
        return size;
    }

    /**
     * 向链表尾部插入元素，成功则返回true
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    /**
     * 移除链表中的某元素，true：成功，false：失败
     */
    public boolean remove(Object o) {
        if (o == null) {
            for (Node<E> x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }


    /**
     * 返回元素在链表中第一次出现的位置下标，若不存在，则返回-1
     */
    public int indexOf(Object o) {
        int index = 0;
        if (o == null) {//当元素为null时，防止空指针，null用等于判断，非null的字符串用equals
                //遍历
            for (Node<E> x = first; x != null; x = x.next) {
                //链表节点元素中存在null，则返回位置
                if (x.item == null)
                    return index;
                index++;
            }
        } else { //当元素不为null时
            for (Node<E> x = first; x != null; x = x.next) {
                if (o.equals(x.item))
                    return index;
                index++;
            }
        }
        return -1;
    }

    /**
     * 返回元素在链表中最后一次出现的位置下标，若不存在，则返回-1
     */
    public int lastIndexOf(Object o) {
        int index = size;
        if (o == null) {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (x.item == null)
                    return index;
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                index--;
                if (o.equals(x.item))
                    return index;
            }
        }
        return -1;
    }

    /*
     * 链表上的每个节点
     */
    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;
        }
    }

}

小阿小叮当

膜拜大神

江南5753

这个厉害，还有二？

xj1124

bushi hendong

Vvvvvoid

Eclipse
Ctrl + 左键啊

While_Shark

好的，多谢楼主

NullPointer

江南5753 发表于 2016-12-2 11:56
这个厉害，还有二？

这个不全，只是写了常用的，可以看出来LinkedList移动元素很方便，效率很高，但是我并没有写get的，get的效率很低下了，打算在后续文章中写出，并与之前写的ArrayList的做对比。