源码阅读-LinkedList

Tips：

1. 如果要在集合中使用自定义类，建议重写equals函数
2. 如果集合内元素较多，使用结束后建议清空（GC）
3. LinkedList所提供的原生函数无批处理，所以会有线程安全的假象，但是它并非线程安全，并且因为不想ArrayList提供批处理函数（函数内针对线程安全做了一定的处理），所以在使用LinkedList时需要格外注意
4. 链表核心在于指针（即引用），可以先行了解这部分
5. 本次未像ArrayList提供基础代码调用实现

继承实现关系图

蓝色实线为继承，色虚线为实现,红色为内部类

链表简单结构示意图

此为LinkedList的节点结构与队列模拟展示，属于数据结构中的双向链表

参数解释

参数	释义
size	链表节点数目
first	链表头节点指针
last	链表尾节点指针

数据结构

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

创建实例

// 创建空链表
public LinkedList() {
   }

//根据集合创建链表
//实际是先创建空链表，再遍历集合加入链表
   public LinkedList(Collection<? extends E> c) {
       this();
       addAll(c);
   }

增加节点

头部增加节点

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

   //@since 1.6
   //个人认为就是为了修改方法名而存在的方法
   //push和pop应该算是链表的标准操作
   public void push(E e) {
       addFirst(e);
   }

   private void linkFirst(E e) {
   	// 创建指针指向头指针指向地址
       final Node<E> f = first;
       //创建节点，该节点next指针使用刚刚创建的指针f
       //即将新节点的后节点指向头结点
       final Node<E> newNode = new Node<>(null, e, f);
       //first指针指向刚创建的节点
       first = newNode;

       if (f == null)
       	//如果当前链表为空，则f将会指向null
       	//则新节点不仅是头结点也是尾节点
           last = newNode;
       else
       	//因为f指向的是之前的头节点，目前的第二节点
       	//因此需要将节点的prev指针指向现在的头结点，完成结构搭建
           f.prev = newNode;
       //节点数目+1
       size++;
       //修改次数+1
       modCount++;
   }

尾部增加节点

public void addLast(E e) {
       linkLast(e);
   }

   void linkLast(E e) {
   	//创建指针指向尾指针指向地址
       final Node<E> l = last;
       //创建新节点，新节点的前指针指向尾指针(l)指向地址
       //后指针指向null
       final Node<E> newNode = new Node<>(l, e, null);
       //链表尾指针指向新节点
       last = newNode;

       if (l == null)
       	//如果原链表为空，则新节点同时也是头结点
           first = newNode;
       else
       	//l原本指向尾节点，现在是倒数第二
       	//因此l指向的节点的后指针应指向新节点完成结构搭建
           l.next = newNode;
       //节点数目+1
       size++;
       //修改次数+1
       modCount++;
   }

增加一个节点

public boolean add(E e) {
	//使用尾部添加方式
       linkLast(e);
       return true;
   }

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

指定位置添加一个节点

public void add(int index, E element) {
    //索引位置校验
    checkPositionIndex(index);

    if (index == size)
        //尾部追加方式
        linkLast(element);
    else
        //指定index插入方式
        linkBefore(element, node(index));
}

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;
    //节点数目+1
    size++;
    //修改次数+1
    modCount++;
}

指定位置通过集合添加节点

public boolean addAll(int index, Collection<? extends E> c) {
	//检查索引位置是否合法[0,size]
       checkPositionIndex(index);
	
	//利用collection函数，将集合元素抽取为数组
       Object[] a = c.toArray();

       int numNew = a.length;
       if (numNew == 0)
       	//如果集合为空，则直接返回
           return false;

	//声明前指针，后指针
       Node<E> pred, succ;
       if (index == size) {
       	//如果插入位置与数量size相等
       	//则是尾部追加
           succ = null;
           pred = last;
       } else {
       	//将后指针指向指定位置节点
           succ = node(index);
		//将前指针指向指定位置节点的前一个节点
           pred = succ.prev;
       }

       for (Object o : a) {
       	//使用pred作为前指针，创建只有前指针的节点
           @SuppressWarnings("unchecked") E e = (E) o;
           Node<E> newNode = new Node<>(pred, e, null);
           if (pred == null)
               //前指针为空意味着链表为空，当前创建节点为链表头结点
               //需要将首指针指向该节点
               first = newNode;
           else
               //链表不为空，则需要将前面的节点的后指针指向创建节点
               pred.next = newNode;
           //pred指针后移
           pred = newNode;
       }
       
       //succ指向原本位置在index的节点
       if (succ == null) {
           //succ为空，则至少说明是尾部追加
           //需要将尾指针指向该节点
           last = pred;
       } else {
           //将创建的最后一个节点的后指针指向原本位于index的节点
           //将原节点的前指针指向创建的最后一个节点
           //完成最后的连接构建
           pred.next = succ;
           succ.prev = pred;
       }
       
       //刷新链表大小
       size += numNew;
       //修改次数+1
       modCount++;
       return true;
   }

//根据索引找到节点
   Node<E> node(int index) {
       // assert isElementIndex(index);

       if (index < (size >> 1)) {
       	//如果索引在前半部，则使用头结点正向遍历查找
           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;
       }
   }

尾部添加集合

public boolean addAll(Collection<? extends E> c) {
       //直接传入size
       return addAll(size, c);
   }

删除节点

删除头节点

public E removeFirst() {
    final Node<E> f = first;
    if (f == null)
        //防止链表为空
        throw new NoSuchElementException();
    return unlinkFirst(f);
}

//该方法与上一个方法的区别就是健壮性
//当链表为空时，不会抛出异常，而是null
//@since 1.5
public E poll() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

//@since 1.6
//只改了 一个方法名称，之所以保留上一个方法
//应该是出于兼容问题考虑，防止有的用户升级了jdk版本
//但是没有完全的修改好已经使用的方法
//也怀疑是方便推广
public E pollFirst() {
    final Node<E> f = first;
    return (f == null) ? null : unlinkFirst(f);
}

//@since 1.6
//同考虑为只是修改方法名，或者说降低使用难度（针对英语为母语）
public E pop() {
    return removeFirst();
}

//个人认为该方法只是为了重载，无明显含义
public E remove() {
    return removeFirst();
}

private E unlinkFirst(Node<E> f) {
    // assert f == first && f != null;
    //保留下头结点内部value
    final E element = f.item;
    //新指针指向第二个节点
    final Node<E> next = f.next;
    //释放第一节点值域
    f.item = null;
    //断开头结点与第二节点连接
    f.next = null; // help GC
    //头指针指向第二节点
    first = next;
    if (next == null)
        //防止头结点被移除后，链表为空
        last = null;
    else
        //第二节点与原头结点连接断开
        next.prev = null;
    //链表节点数目-1
    size--;
    //修改次数+1
    modCount++;
    //返回原头结点保存的值
    return element;
}

删除尾节点

public E removeLast() {
    final Node<E> l = last;
    if (l == null)
        //防止链表为空
        throw new NoSuchElementException();
    return unlinkLast(l);
}

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

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;
    //刷新链表大小-1
    size--;
    //修改次数+1
    modCount++;
    //返回原尾结点保存的值
    return element;
}

根据内容删除节点

//@since 1.6
//来自语言的满满恶意
public boolean removeFirstOccurrence(Object o) {
    return remove(o);
}

public boolean remove(Object o) {
    if (o == null) {
        //区分null是因为空无法使用equals函数比较
        //从头结点开始，正向遍历查找
        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) {
            //因为使用的是传入对象的equals方法进行对比，因此
            //使用自定义对象的时候，建议重写equals方法
            if (o.equals(x.item)) {
                unlink(x);
                return true;
            }
        }
    }
    return false;
}

//@since 1.6
//来自语言的满满恶意
//此方法有些许不同，它是删除最后一个出现的，即反向查找
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;
}

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;
    //节点数目-1
    size--;
    //修改次数+1
    modCount++;
    返回被移除节点保存内容
    return element;
}

删除指定位置节点

public E remove(int index) {
    //校验index合法
    checkElementIndex(index);
    return unlink(node(index));
}

节点清空

public void clear() {
    // Clearing all of the links between nodes is "unnecessary", but:
    // - helps a generational GC if the discarded nodes inhabit
    //   more than one generation
    // - is sure to free memory even if there is a reachable Iterator
    //理论上不用清除每一个节点的指针连接，但是这能帮助减少GC压力，因为
    //丢弃的节点依然会存在内存中互相引用
    //正向遍历清空每一个节点
    for (Node<E> x = first; x != null; ) {
        Node<E> next = x.next;
        x.item = null;
        x.next = null;
        x.prev = null;
        x = next;
    }
    //刷新头指针与尾指针
    first = last = null;
    //刷新链表大小
    size = 0;
    //修改次数+1
    modCount++;
}

修改节点

修改指定索引节点

//该方法虽然修改了节点
//但是并没有修改modCount
public E set(int index, E element) {
    //校验index合法
    checkElementIndex(index);
    //找出指定位置节点
    Node<E> x = node(index);
    //保留一份值的副本
    E oldVal = x.item;
    //修改节点的值
    x.item = element;
    //返回旧值
    return oldVal;
}

查找节点

获取头结点

//返回的是节点的值
public E getFirst() {
    final Node<E> f = first;
    if (f == null)
        throw new NoSuchElementException();
    return f.item;
}

//@since 1.5
public E peek() {
    final Node<E> f = first;
    return (f == null) ? null : f.item;
}

//@since 1.5
public E element() {
    return getFirst();
}

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

获取尾节点

//返回节点值
public E getLast() {
    final Node<E> l = last;
    if (l == null)
        throw new NoSuchElementException();
    return l.item;
}

判断是否含有节点

//通过值判断
public boolean contains(Object o) {
    return indexOf(o) != -1;
}

查询节点索引位置

//正向，返回第一次出现的索引
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;
}

查询指定索引节点

//返回值
public E get(int index) {
    checkElementIndex(index);
    return node(index).item;
}