• LinkedList源码解析及队列和栈相关分析

    文章目录

    1. LinkedList类图总览

    在这里插入图片描述
    从类图中可以看到LinkedList继承了AbstractSequentialList，同时实现了List、Deque、Cloneable、java.io.Serializable。

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

    • 1
    • 2
    • 3

    Deque：双向队列

    public interface Deque<E> extends Queue<E> 

    • 1

    Queue：队列

    2. 源码分析

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14

    2.2. LinkedList拥有的属性

    在这里插入图片描述

    
    //元素个数
    transient int size = 0;

    /**
     *  头节点
     * Pointer to first node.
     * Invariant: (first == null && last == null) ||
     *            (first.prev == null && first.item != null)
     */
    transient Node<E> first;

    /**
     *  尾节点
     * Pointer to last node.
     * Invariant: (first == null && last == null) ||
     *            (last.next == null && last.item != null)
     */
    transient Node<E> last;

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19

    2.3. LinkedList构造函数

    在这里插入图片描述

        /**
     * Constructs an empty list.
     */
    public LinkedList() {
    }

    /**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection's
     * iterator.
     *
     * @param  c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public LinkedList(Collection<? extends E> c) {
        this();
        addAll(c);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    2.4. LinkedList相关操作

    2.4.1. 添加元素

    2.4.1.1. 头插

        /**
     * Links e as first element.
     */
    private void linkFirst(E e) {
        //头节点
        final Node<E> f = first;
        //定义一个新的节点，元素为e，next指向头节点
        final Node<E> newNode = new Node<>(null, e, f);
        //头节点重新赋值为新的节点newNode
        first = newNode;
        //如果头节点为空，则尾节点也指向新的节点newNode；否则，头结点的前驱指针执行新的节点newNode
        if (f == null)
            last = newNode;
        else
            f.prev = newNode;
        //元素个数+1
        size++;
        //修改次数 +1，用于 fail-fast 处理
        modCount++;
    }
    
    /**
     * Inserts the specified element at the beginning of this list.
     *
     * @param e the element to add
     */
    public void addFirst(E e) {
        linkFirst(e);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29

    2.4.1.2. 尾插

        /**
     * Links e as last element.
     */
    void linkLast(E e) {
        //尾节点
        final Node<E> l = last;
        //定义一个新的节点，元素为e，prev指向尾节点
        final Node<E> newNode = new Node<>(l, e, null);
        //尾节点重新赋值为新的节点newNode
        last = newNode;
        //如果尾节点尾null，头节点也指想新的节点newNode；否则，尾节点的后继指针指向新的节点newNode
        if (l == null)
            first = newNode;
        else
            l.next = newNode;
        //元素个数+1
        size++;
        //修改次数 +1，用于 fail-fast 处理
        modCount++;
    }

    /**
     * Appends the specified element to the end of this list.
     *
     * 
    This method is equivalent to {@link #add}.
     *
     * @param e the element to add
     */
    public void addLast(E e) {
        linkLast(e);
    }

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

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32
    • 33
    • 34
    • 35
    • 36

    addLastE e)和add(E e)的区别：

    • addLast(E e)：没有返回值

    • add(E e)：插入成功后会返回true

    2.4.1.3. 中间插入

        public void add(int index, E element) {
        //判断是否越界
        checkPositionIndex(index);

        //如果要插入的位置等于链表的大小，则在尾部插入；否则，找到索引位置的节点node(index)，在该节点之前插入
        if (index == size)
            linkLast(element);
        else
            linkBefore(element, node(index));
    }

    /**
     * Inserts element e before non-null Node succ.
     */
    void linkBefore(E e, Node<E> succ) {
        // assert succ != null;
        //定义succ的前驱节点为pred
        final Node<E> pred = succ.prev;
        //新节点的前驱为pred，后继为succ
        final Node<E> newNode = new Node<>(pred, e, succ);
        //succ的前驱为新节点newNode
        succ.prev = newNode;
        //如果前驱节点pred为null，则说明新插入的节点为头节点，更新first；否则，需要将前驱节点pred的后继指针指向新节点newNode
        if (pred == null)
            first = newNode;
        else
            pred.next = newNode;
        //元素个数+1
        size++;
        //修改次数 +1，用于 fail-fast 处理
        modCount++;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28
    • 29
    • 30
    • 31
    • 32

    2.4.2. 删除元素

    2.4.2.1. 删除头节点

    /**
     * Removes and returns the first element from this list.
     *
     * @return the first element from this list
     * @throws NoSuchElementException if this list is empty
     */
    public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    /**
     * 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;
        else
            next.prev = null;
        size--;
        modCount++;
        return element;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    2.4.2.2. 删除尾节点

     /**
     * Removes and returns the last element from this list.
     *
     * @return the last element from this list
     * @throws NoSuchElementException if this list is empty
     */
    public E removeLast() {
        final Node<E> l = last;
        if (l == null)
            throw new NoSuchElementException();
        return unlinkLast(l);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    /**
     * 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)
            first = null;
        else
            prev.next = null;
        size--;
        modCount++;
        return element;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18

    2.4.2.3. 根据元素删除

    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
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
        /**
     * Unlinks non-null node x.
     */
    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;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    2.4.2.4. 根据索引删除

        public E remove(int index) {
        //校验索引是否越界
        checkElementIndex(index);
        return unlink(node(index));
    }

    • 1
    • 2
    • 3
    • 4
    • 5
        /**
     * Unlinks non-null node x.
     */
    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;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11
    • 12
    • 13
    • 14
    • 15
    • 16
    • 17
    • 18
    • 19
    • 20
    • 21
    • 22
    • 23
    • 24
    • 25
    • 26
    • 27
    • 28

    3. LinkedList作为队列

    队列：先进先出

    ListLinked<String> queue = new LinkedList<>();

    • 1

    3.1. 入队操作

    在链表的尾部添加节点

    3.1.1. add

    public boolean add(E e)

    • 1

    示例：

    queue.add("1");

    • 1

    源码：

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

    • 1
    • 2
    • 3
    • 4
        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++;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    3.1.2. addLast

    public void addLast(E e)

    • 1

    示例：

    queue.addLast("2");

    • 1

    源码：

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

    • 1
    • 2
    • 3
        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++;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    3.1.3. offerLast

    public boolean offerLast(E e)

    • 1

    示例：

    queue.offerLast("3");

    • 1

    源码：

        public boolean offerLast(E e) {
        addLast(e);
        return true;
    }

    • 1
    • 2
    • 3
    • 4
        public void addLast(E e) {
        linkLast(e);
    }

    • 1
    • 2
    • 3
        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++;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    3.1.4. offer

    public boolean offer(E e)

    • 1

    示例：

    queue.offer("4");

    • 1

    源码：

        public boolean offer(E e) {
        return add(e);
    }

    • 1
    • 2
    • 3
        public boolean add(E e) {
        linkLast(e);
        return true;
    }

    • 1
    • 2
    • 3
    • 4
        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++;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    总结：
    offer->add->LinkLast
    offerLast->addLast->LinkLast

    3.2. 出队操作

    从链表的头部删除节点

    3.2.1. remove

    public E remove()

    • 1

    示例：

    queue.remove();

    • 1

    源码：

        public E remove() {
        return removeFirst();
    }

    • 1
    • 2
    • 3
        public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    3.2.2. removeFirst

    public E removeFirst()

    • 1

    示例：

    queue.removeFirst();

    • 1

    源码：

        public E removeFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return unlinkFirst(f);
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    3.2.3. poll

    public E poll()

    • 1

    示例：

    queue.poll();

    • 1

    源码：

        public E poll() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    • 1
    • 2
    • 3
    • 4

    3.2.4. pollFirst

    public E pollFirst()

    • 1

    示例：

    queue.pollFirst();

    • 1

    源码:

        public E pollFirst() {
        final Node<E> f = first;
        return (f == null) ? null : unlinkFirst(f);
    }

    • 1
    • 2
    • 3
    • 4

    总结：
    remove->removerFirst：失败抛异常
    poll==pollFirst：失败返回null

    3.3. 获取队首元素

    3.3.1. element

    public E element()

    • 1

    示例：

    queue.element();

    • 1

    源码：

        public E element() {
        return getFirst();
    }

    • 1
    • 2
    • 3
        public E getFirst() {
        final Node<E> f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6

    3.3.2. peek

    public E peek()

    • 1

    示例：

    queue.peek();

    • 1

    源码：

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

    • 1
    • 2
    • 3
    • 4

    总结：
    element：无数据抛异常
    peek：无数据返回null

    4. LinkedList作为栈

    栈：后进先出

    ListLinked<String> stack = new LinkedList<>();

    • 1

    4.1. 进栈操作

    从链表的头部添加节点

    4.1.1. push

     public void push(E e)

    • 1

    示例：

    stack.push();

    • 1

    源码：

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

    • 1
    • 2
    • 3
        public void addFirst(E e) {
        linkFirst(e);
    }

    • 1
    • 2
    • 3
        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;
        size++;
        modCount++;
    }

    • 1
    • 2
    • 3
    • 4
    • 5
    • 6
    • 7
    • 8
    • 9
    • 10
    • 11

    4.2. 出栈操作

    从链表的头部删除节点

    同：队列的出队操作

    4.3. 获取顶部元素

    同：队列获取队首元素

  • 相关阅读:
    灵性图书馆：好书推荐-《在荷欧波诺波诺中遇见真正的自己》
    BOM的常用操作和有关获取页面/窗口高度、宽度及滚动的兼容性写法
    【NLP】使用 BERT 和 PyTorch Lightning 进行多标签文本分类
    后续遍历非递归算法
    Kibana使用Timelion根据时间序列展示数据
    Android自定义View之条件筛选菜单
    探索ChatGPT的Fine-tuning和Embeddings
    Unity UGUI Image Maskable
    ROS2与turtlebot4仿真入门教程-turtlebot4异步建图
    猿创征文 第二季｜ #「笔耕不辍」--生命不息，写作不止#
  • 原文地址：https://blog.csdn.net/hdn_kb/article/details/126249355