集合篇-LinkedList

LinkedList

LinkedList是List家族中的一员，实现了List接口，底层是一个双向链表来实现，在删除的时候效率高。
因为LinkedList底层是个双向链表，所以他支持头结点插入和尾节点插入，同时也可以当做一个双端队列来使用

字段解析

//链表节点个数
transient int size = 0;
//头结点
transient Node<E> first;
//尾结点
transient Node<E> last;

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

尾结点插入

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

头结点插入

private void linkFirst(E e) {
    //记录头结点
    final Node<E> f = first;
    //新建一个下一节点的指针指向当前头结点的节点
    final Node<E> newNode = new Node<>(null, e, f);
    //头结点职位新建的节点
    first = newNode;
    //如果原有的头结点为空 说明整个链表是为空的 此时尾结点也职位新建的节点
    if (f == null)
        last = newNode;
    //否则 原有的头结点的上节点指针指向新节点
    else
        f.prev = newNode;
    
    //链表长度+1
    size++;
    //链表结构变更次数加一
    modCount++;
}

头结点删除

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;  断言 此时的f是头结点 并且不为null
    final E element = f.item;
    //头结点的下一节点
    final Node<E> next = f.next;
    
    //下面两个语句都是为空方便垃圾收集器回收掉
    f.item = null;
    f.next = null; // help GC
    
    //头结点职位f的下一节点
    first = next;
    
    //如果next为空 代表当前链表没有了元素 此时尾结点也要置位null
    if (next == null)
        last = null;
    else
        //否则头结点的上一节点指针置位null
        next.prev = null;
    //链表元素减一
    size--;
    //链表变更次数减一
    modCount++;
    return element;
}

尾节点删除

private E unlinkLast(Node<E> l) {
    // assert l == last && l != null; 断言此时的f是尾结点 并且不为null
    //记录f的持有的元素值
    final E element = l.item;
    //记录f的上一节点 可以理解为尾结点的上一节点
    final Node<E> prev = l.prev;
    //f的持有的元素值和上一节点置位null 方法GC
    l.item = null;
    l.prev = null; // help GC
    
    //尾结点置位当前节点(尾结点)的上一节点
    last = prev;
    //如果上一节点为null 说明已经没有元素了 头结点也置位null
    if (prev == null)
        first = null;
    else
        //否则 尾结点的下一节点的指针指向null
        prev.next = null;
    //链表上次减一
    size--;
    //链表变更洗漱+1
    modCount++;
    //返回移除的元素
    return element;
}

实现了List集合的add方法


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

可以看出默认是往尾部进行元素的插入，想往头部插入的时候可以调用linkFirst()或者addFirst()后者里面也是直接调用了前者

删除元素

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 {
        //遍历找到元素为指定元素的节点 调用unlink()方法删除 与上面不同的是 当为空元素的时候  调用equals方法会抛出NPE
        for (Node<E> x = first; x != null; x = x.next) {
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}


E unlink(Node<E> x) {
    
    //记录当前节点
    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;
        //当前节点的上一节点置位null  方便GC
        x.prev = null;
    }

    //下一节点为空的时候 说明当前节点是尾结点 删除之后就要把当前节点的上一节点置位尾结点
    if (next == null) {
        last = prev;
    } else {
       //否则就是下节点的上节点指针指向当前节点的上一节点
        next.prev = prev;
        //当前节点的下一节点置位null  方便GC
        x.next = null;
    }
    
     //当前节点的值置位null 方便GC
    x.item = null;
    //链表长度减一
    size--;
    //链表结构变更次数+1
    modCount++;
    返回删除的节点
    return element;
}

总结：LinkedList是一个实现了List和Deque的类，不仅可以当做集合来用，还可以当做队列来用。
主要围绕linkFirst(), linkLast(), unlinkFirst, unlinkLast()等几个主要的方法
进行对LinkedList的增删改