阅读java.util.LinkedList源码Note

原创
2020/04/20 21:56
阅读数 99

Queue 队列

这些操作都是在头部进行操作,但队列内的排序则不尽然相同,可以FIFO,也可以LIFO, 队列、栈!

操作 抛出异常 返回特定值
Insert add(容量限制) offer
Remove remove(queue为空) poll
Examine element(queue为空) peek

Deque 双端队列

方法比较

Summary of Deque methods
  First Element (Head) Last Element (Tail)
  Throws exception Special value Throws exception Special value
Insert {@link Deque#addFirst addFirst(e)} {@link Deque#offerFirst offerFirst(e)} {@link Deque#addLast addLast(e)} {@link Deque#offerLast offerLast(e)}
Remove {@link Deque#removeFirst removeFirst()} {@link Deque#pollFirst pollFirst()} {@link Deque#removeLast removeLast()} {@link Deque#pollLast pollLast()}
Examine {@link Deque#getFirst getFirst()} {@link Deque#peekFirst peekFirst()} {@link Deque#getLast getLast()} {@link Deque#peekLast peekLast()}

作为队列, FIFO

Comparison of Queue and Deque methods
{@code Queue} Method Equivalent {@code Deque} Method
{@link java.util.Queue#add add(e)} {@link #addLast addLast(e)}
{@link java.util.Queue#offer offer(e)} {@link #offerLast offerLast(e)}
{@link java.util.Queue#remove remove()} {@link #removeFirst removeFirst()}
{@link java.util.Queue#poll poll()} {@link #pollFirst pollFirst()}
{@link java.util.Queue#element element()} {@link #getFirst getFirst()}
{@link java.util.Queue#peek peek()} {@link #peek peekFirst()}

作为栈 Stack

Comparison of Stack and Deque methods
Stack Method Equivalent {@code Deque} Method
{@link #push push(e)} {@link #addFirst addFirst(e)}
{@link #pop pop()} {@link #removeFirst removeFirst()}
{@link #peek peek()} {@link #peekFirst peekFirst()}

双向链表: 链表记录头节点和尾节点,每个节点会持有前驱节点和后驱节点的引用。

public class LinkedList {
    Node first;
    Node last

    class Node {
        Node pre;
        Object item;
        Node next;
    }
}

fail-fast机制:在创建Iterator后,只能通过iterator的remove后者add方法修改集合,其他方式都会引起遍历失败。

    /**
     * Pointer to first node.
     * 集合为空时,first和last必定为空
     * 集合不为空时,first的前驱为空,first的item不为空
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     * Pointer to last node.
     * 集合为空时,first和last必定为空
     * 集合不为空时,last的后驱为空,last的item不为空
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

内部获取指定位置的元素,判断index在前半部分还是后半部分

if( index < size >> 1) {
    //从first开始向后遍历
}else {
    //从last开始向前遍历
}

修改集合结构时,需操作前后节点的prev和next,同时需考虑是否需要设置头尾节点

记录几个关键方法,其余方法底层均是使用此部分方法实现


/**
     * Links e as first element.
     * 链接一个元素为头部节点,注意:此并非为替换元素
     */
    private void linkFirst(E e) {
        final Node<E> f = first;
        final Node<E> newNode = new Node<>(null, e, f);
        //集合的头节点引用至新节点
        first = newNode;
        if (f == null)
            //代表空集合,空集合的头节点、尾节点相同,节点的prev\next均为null
            last = newNode;
        else
            //否则将原先头节点的prev指向新的头节点
            f.prev = newNode;
        size++;
        modCount++;
    }

    /**
     * Links e as last element.
     */
    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
            //设置原尾结点的next
            l.next = newNode;
        size++;
        modCount++;
    }

    /**
     * Inserts element e before non-null Node succ.
     * 将元素插入特定节点之前
     * 需要做四个链接更新
     * 1. 设置新节点的prev和next
     * 2. 设置succ的prev为新节点
     * 3. 设置succ的原prev节点的next节点为新节点
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        //记录后继者的prev引用
        final Node<E> pred = succ.prev;
        //构造节点,指定prev为succ的prev,next为succ,
        final Node<E> newNode = new Node<>(pred, e, succ);
        // 设置succ的prev引用,更新链接关系
        succ.prev = newNode;
        if (pred == null)
            //succ为原来的头节点,相当于此动作为设置新的头节点
            //更新first的引用
            first = newNode;
        else
            //更新succ的原prev节点的next链接
            pred.next = newNode;
        size++;
        modCount++;
    }

    /**
     * Unlinks non-null first node f.
     * 去掉头节点
     */
    private E unlinkFirst(Node<E> f) {
        // assert f == first && f != null;
        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
            last = null;
        else
            //将next的prev置为null,取消引用关系
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

    /**
     * Unlinks non-null last node 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)
            //若集合为空,首尾节点相同,需将头节点设置为null
            first = null;
        else
            //集合尾结点的next为null,更新新的尾部节点的next链接关系
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

    /**
     * Unlinks non-null node x.
     * 去掉某个节点
     * 1. 设置x的item prev next为null, help GC
     * 2. 设置x的prev节点的next为x的next节点
     * 3. 设置x的next节点的prev为x的prev节点
     */
    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;
        //[prev item next] [prev item next] [prev item next]
        if (prev == null) {
            //节点的prev引用为空,则可认为是头节点,此时需更新集合的first引用
            first = next;
        } else {
            //设置x的prev节点的next为x的next节点
            prev.next = next;
            x.prev = null;
        }

        if (next == null) {
            //节点的next引用为空,则可认为是尾节点,此时需更新集合的next引用
            last = prev;
        } else {
            //设置x的next节点的prev为x的prev节点
            next.prev = prev;
            x.next = null;
        }
        //help gc
        x.item = null;
        size--;
        modCount++;
        return element;
    }

展开阅读全文
打赏
0
0 收藏
分享
加载中
更多评论
打赏
0 评论
0 收藏
0
分享
返回顶部
顶部