jdk源码——集合(LinkedList)

上一篇分析了ArrayList的源码jdk源码——集合(ArrayList)，这一次分析LinkedList的源码。

先看一下LinkedList的类定义：

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

由上面的代码，可以得出LinkedList继承了AbstractSwquentialList，接下来我们先看一下AbstractSwquentialList类。

/*
abstract AbstractSequentialList继承了AbstractList，所有的方法内部都是调用一个抽象的方法listIterator(int index)，
 */
public abstract class AbstractSequentialList<E> extends AbstractList<E> {

    protected AbstractSequentialList() {
    }


    //获取，根据内部的迭代器，获取值
    public E get(int index) {
        try {
            return listIterator(index).next();
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

    //设置新值
    public E set(int index, E element) {
        try {
            ListIterator<E> e = listIterator(index);
            E oldVal = e.next();
            e.set(element);
            return oldVal;
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

    //指定位置添加
    public void add(int index, E element) {
        try {
            listIterator(index).add(element);
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

    //删除指定位置的值
    public E remove(int index) {
        try {
            ListIterator<E> e = listIterator(index);
            E outCast = e.next();
            e.remove();
            return outCast;
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }


    //在指定的位置添加一个集合
    public boolean addAll(int index, Collection<? extends E> c) {
        try {
            boolean modified = false;
            ListIterator<E> e1 = listIterator(index);
            Iterator<? extends E> e2 = c.iterator();
            while (e2.hasNext()) {
                e1.add(e2.next());
                modified = true;
            }
            return modified;
        } catch (NoSuchElementException exc) {
            throw new IndexOutOfBoundsException("Index: "+index);
        }
    }

   //返回一个迭代器
    public Iterator<E> iterator() {
        return listIterator();
    }

    //抽象方法，需要子类实现
    public abstract ListIterator<E> listIterator(int index);
}

    有父类可以知道，LinkedList必须实现listIterator方法，方法内部必须要实现一个迭代器，并将之返回。

   ArrayList的底层是一个数组，LinkedList的底层是一个链表。如果你知道链表结构的操作，看LinkedList将会非常简单。

   不知道大家对链表有没有认识，这里就不讲解链表了，如果有同学不会的话，可以网上搜一下。链表是由一个一个的节点组成的。我们可以看一下java中对链表的定义。

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

    

     ——LinkedList的成员变量

    /*
    first和list都会在链表被修改时候(首或尾改变)或添加的时，就会被赋予值，
     */
    transient int size = 0;//LinkedList的长度
    
    transient Node<E> first;//首节点
    
    transient Node<E> last;//末节点

    这些成员变量，都被transient关键字所修饰，这个关键字的作用就是不被序列化

  

   ——LinkedList的构造方法(2个)

   public LinkedList() {
    }
    
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);调用了addALL()方法，下面会介绍
    }

  ——LinkedList的普通方法

       ——添加

     /**
    在首位添加，
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        first = newNode;//first变为新添加的节点
        if (f == null)
            //如果f为null，则该链表为null
            last = newNode;//尾节点，首节点都是newNode
        else
            f.prev = newNode;//前面插入
        size++;
        modCount++;
    }

    /*
     在最后添加元素
    */
    void linkLast(E e) {
        //transient Node<E> last;
        final Node<E> l = last;
        final Node<E> newNode = new Node<>(l, e, null);
        last = newNode;
        if (l == null)
            //如果l为null，则该链表为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++;
    }
//----------------------------------几乎后面的添加操作，都是调用的上面的三个方法

    /*
    在first位置插入元素
     */
    public void addFirst(E e) {
        linkFirst(e);
    }
    
    /*
    addLast和add方法一样，都是调用linkLast方法
     */
    public void addLast(E e) {
        linkLast(e);
    }

    /*
    在末尾添加节点
     */
    public boolean add(E e) {
        linkLast(e);
        return true;
    }

    /*
    添加一个集合
     */
    public boolean addAll(Collection<? extends E> c) {
        return addAll(size, c);
    }

    /*
    添加集合的实际操作方法，有参数构造器，也调用了此方法，
     */
    public boolean addAll(int index, Collection<? extends E> c) {
        //index就是在指定位置添加一个集合，其实链表并没有和数组一样的下标，只是LinkedList有一个size属性，添加操作时会+1，类似于下标
        checkPositionIndex(index);//判断参数合法化，index >= 0 && index <= size;，如果不符合，则会抛出异常

        Object[] a = c.toArray();//将传入的集合转化为数组
        int numNew = a.length;
        if (numNew == 0)
            //如果传入的集合长度为0，直接返回false
            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;//将Object类型强制转化
            Node<E> newNode = new Node<>(pred, e, null);
            if (pred == null)
                //如果前一个节点为null，证明是在第一个节点添加
                first = newNode;//重新设置first
            else
                //前一个节点不为null，只需要维护维护节点的next，将前一个节点的next指向这个新节点即添加成功
                pred.next = newNode;
            pred = newNode;//然后把该节点当做当前节点，继续循环遍历
        }

        if (succ == null) {
            last = pred;//因为实在末尾进行添加操作，首节点未改变，末节点已经改变，还需要重新设置
        } else {
            //因为不是在末尾添加，所以首尾节点不改变或者已经在for循环中进行了维护，

            pred.next = succ;//将已经添加成功后的节点的next指向添加之前index位置的节点(在中间添加一个集合的情况)
            succ.prev = pred;
        }

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

    /*
    固定位置添加值
     */
    public void add(int index, E element) {
        checkPositionIndex(index);///判断参数合法化

        if (index == size)
            linkLast(element);//如果传入的参数等于长度，直接在最后添加元素
        else
            //如果不等于链表长度，调用linkBefore(),在摸个元素之前添加节点
            linkBefore(element, node(index));
    }

    /*
       在链表尾添加元素
     */
    public boolean offer(E e) {
        return add(e);
    }

    /*
       在链表头部添加元素
     */
    public boolean offerFirst(E e) {
        addFirst(e);
        return true;
    }
    
    /*
      在链表尾添加元素,
    */
    public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

    /*
   在链表首添加第一个元素
    */
    public void push(E e) {
        addFirst(e);
    }

    大家可以看到添加的方法有很多，但是有很多方法都重复了，底层都是调用了同一个方法。其实根本没有区别。

  

     ——删除

    /*
    删除第一个元素并返回
     */
    private E unlinkFirst(Node<E> f) {
        /*
         其实根本不是真正以上的删除，只是将第一个节点后面的那个节点的prev设置为null，第一个节点next设置为null，
         first保存第一个节点后的那个节点，如此而已
          */
        final E element = f.item;
        final Node<E> next = f.next;
        f.item = null;
        f.next = null; // 将第一个节点都设置为null，会让垃圾收集器进行清除
        first = next;
        if (next == null)
            //如果next为null，证明是该链表只有一个节点
            last = null;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }
    
    /*
    删除并返回最后一个元素，维护最后一个和倒数第二个节点即可
     */
    private E unlinkLast(Node<E> l) {
        // assert l == last && l != null;
        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
            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;//前一个节点

        //将后一个节点和前一个节点互相指向，即可
        if (prev == null) {
            first = next;
        } else {
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            last = prev;
        } else {
            next.prev = prev;
            x.next = null;
        }
        x.item = null;
        size--;
        modCount++;
        return element;
    }
//----------------------------------下面的删除方法都是调用的上面的三个删除方法

    /*
    删除第一个元素
     */
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }
    
    /*
    删除最后一个元素
     */
    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

   /*
      删除指定的值删除节点
    */
    public boolean remove(Object o) {
        if (o == null) {
            //就是循环遍历，得到包含这个值得节点，然后调用unlink()删除这个节点
            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;
    }

    /*
     只要指定固定位置的，都需要调用node()方法，来获得该位置的元素
    */
    public E remove(int index) {
        checkElementIndex(index);
        return unlink(node(index));//调用了node(int index),获得节点
    }

    /*
    删除第一个元素，如果为空时返回null
     */
    public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    
    /*
   删除第一个元素，如果为空时报错
    */
    public E remove() {
        return removeFirst();
    }

    /*
    unlinkFirst()删除，获取并移除第一个元素
    */
    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }
    
    /*
    unlinkFirst()删除，获取并移除最后一个元素
    */
    public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

    /*
    删除第一个元素，如果为空，会报错
     */
    public E pop() {
        return removeFirst();
    }

    /*
    从此列表中移除第一次出现的指定元素（从头部到尾部遍历列表时）。
    */
    public boolean removeFirstOccurrence(Object o) {
        return remove(o);
    }

    /*
    删除最后一次出现的指定元素，
    */
    public boolean removeLastOccurrence(Object o) {
        if (o == null) {
            //也是循环遍历，只不过方向是从后往前
            for (Node<E> x = last; x != null; x = x.prev) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node<E> x = last; x != null; x = x.prev) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

删除的方法也是，都有了大量的重复，但是有少许的不同，就是为null，是返回null，还是报错。底层还是调用的相同的方法。

     ——获取

     /*
    获得指定位置的元素
     */
    Node<E> node(int index) {
        if (index < (size >> 1)) {
            Node<E> x = first;
            for (int i = 0; i < index; i++)
                x = x.next;
            //这个设计，我没有想到，我想的是遍历链表，设置length值，遍历一次length+1，知道length=index，而这个设计是根据index，进行next操作
            return x;
        } else {
            Node<E> x = last;
            for (int i = size - 1; i > index; i--)
                x = x.prev;
            return x;
        }
    }

    /*
    获得第一个元素
    */
    public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            //为null抛异常
            throw new NoSuchElementException();
        return f.item;
    }

    /*
    获得最后一个元素
    */
    public E getLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return l.item;
    }

    /*
    根据指定位置，获得值
    */
    public E get(int index) {
        checkElementIndex(index);//判断传入的指定位置，是否合法
        return node(index).item;
    }

    /*
    获得该元素在链表中的下标
    */
    public int indexOf(Object o) {
        int index = 0;
        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;
    }
    
    /*
    获得该元素在最末尾的下标
     */
    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;
    }

    /*
    获得首元素，如果为null，返回null，不为空，则返回该元素的值
    */
    public E peek() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
    }
    
    /*
    获得第一个元素，为空时会报错
     */
    public E element() {
        return getFirst();
    }  

     /*
    获取第一个值，如果为空，返回null
     */
    public E peekFirst() {
        final Node<E> f = first;
        return (f == null) ? null : f.item;
     }
     
    /*
    获取最后一个值，如果为空，返回null
    */
    public E peekLast() {
        final Node<E> l = last;
        return (l == null) ? null : l.item;
    }       

          —— 获取并删除

    /*
    unlinkFirst()删除，获取并移除第一个元素
    */
    public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    /*
    unlinkFirst()删除，获取并移除最后一个元素
    */
    public E pollLast() {
        final Node<E> l = last;
        return (l == null) ? null : unlinkLast(l);
    }

      

       —— 设置

    /*
     固定位置设置元素并返回原来的值
     */
    public E set(int index, E element) {
        checkElementIndex(index);//判断传入的指定位置，是否合法
        Node<E> x = node(index);//获得指定位置的元素
        E oldVal = x.item;//仅仅需要改变节点中的值即可，因为上一个节点的地址和下一个节点的地址都没有改变.
        x.item = element;
        return oldVal;
    }

      —— 其他方法

    /*
      size会在链表改变时改变size
     */
    public int size() {
        return size;
    }

    /*
    是否包含该元素，也是查询该链表，如果有则返回length值，length并不是下标值，只是模拟的下标志
     */
    public boolean contains(Object o) {
        return indexOf(o) != -1;
    }

     /*
    清除链表
     */
    public void clear() {
        for (Node<E> x = first; x != null; ) {
            //循环遍历，将node节点全部设置为null
            Node<E> next = x.next;
            x.item = null;
            x.next = null;
            x.prev = null;
            x = next;
        }
        first = last = null;
        size = 0;
        modCount++;
    }

   /*
   链表的复制，实际上就是创建一个新的空的链表然后将目的链表添加
    */
    public Object clone() {
        LinkedList<E> clone = superClone();

        // Put clone into "virgin" state
        clone.first = clone.last = null;
        clone.size = 0;
        clone.modCount = 0;

        // Initialize clone with our elements
        for (Node<E> x = first; x != null; x = x.next)
            clone.add(x.item);

        return clone;
    }
    
    /*
    将链表变为数组，创建一个数组，遍历，将链表中每个节点的值放在新创建的数组中
     */
    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;
    }
    
    @SuppressWarnings("unchecked")
    /*
    将链表变为数组，就是遍历，将链表中每个节点的值放在指定的数组中
     */
    public <T> T[] toArray(T[] a) {
        if (a.length < size)
            a = (T[])java.lang.reflect.Array.newInstance(
                                a.getClass().getComponentType(), size);
        int i = 0;
        Object[] result = a;
        for (Node<E> x = first; x != null; x = x.next)
            result[i++] = x.item;
        if (a.length > size)
            a[size] = null;

        return a;
    }

      好了，LinkedList集合就分析到这了。差不多就是这样了吧，看集合的底层最好是有一些数据结构的基础，这样看源代码，会起到事半功倍的效果。

    嗯，文章中有错误的，记得评论哦！下一篇简单将一下红黑树，因为set集合的底层是Map集合，而Map集合的底层是红黑树。所以，知道红黑树的结构和操作，很重要！！！