集合系列 Queue(十):LinkedList

我们之前在说到 List 集合的时候已经说过 LinkedList 了。但 LinkedList 不仅仅是一个 List 集合实现,其还是一个双向队列实现。

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

LinkedList 不仅实现了 List 接口,还实现了 Deque 接口。所以这一节我们来聊聊 LinkedList 的双向队列特性。

原理

为了深入理解 LinkedList 的原理,我们将从类成员变量、构造方法、核心方法两个方面逐一介绍。

类成员变量

// 链表大小
transient int size = 0;
// 首节点
transient Node first;
// 尾节点
transient Node last;
// Node节点
private static class Node {
    E item;
    Node next;
    Node prev;

    Node(Node prev, E element, Node next) {
        this.item = element;
        this.next = next;
        this.prev = prev;
    }
}

可以看到 LinkedList 采用了链表节点的方式实现,并且每个节点都有前驱和后继节点。

构造方法

LinkedList 总共有 2 个构造方法:

public LinkedList() {
}
public LinkedList(Collection c) {
    this();
    addAll(c);
}

构造方法比较简单,这里不深入介绍。

核心方法

LinkedList 中与双向队列相关的几个方法为:offerFirst、offerLast、pollFirst、pollLast。

offerFirst

public boolean offerFirst(E e) {
    addFirst(e);
    return true;
}
    
    public void addFirst(E e) {
    linkFirst(e);
}

// 将e节点作为头结点插入
private void linkFirst(E e) {
    final Node f = first;
    final Node newNode = new Node<>(null, e, f);
    first = newNode;
    if (f == null)
        last = newNode;
    else
        f.prev = newNode;
    size++;
    modCount++;
}

offerLast

public boolean offerLast(E e) {
    addLast(e);
    return true;
}
    
public void addLast(E e) {
    linkLast(e);
}
// 将e节点作为末尾节点插入
void linkLast(E e) {
    final Node l = last;
    final Node newNode = new Node<>(l, e, null);
    last = newNode;
    if (l == null)
        first = newNode;
    else
        l.next = newNode;
    size++;
    modCount++;
}

pollFirst

public E pollFirst() {
    final Node f = first;
    return (f == null) ? null : unlinkFirst(f);
}
// 删除头结点
private E unlinkFirst(Node f) {
    // assert f == first && f != null;
    final E element = f.item;
    final Node 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;
}

pollLast

public E pollLast() {
    final Node l = last;
    return (l == null) ? null : unlinkLast(l);
}
// 删除尾节点
private E unlinkLast(Node l) {
    // assert l == last && l != null;
    final E element = l.item;
    final Node 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;
}

可以看出无论是插入还是删除,poll 和 offer 操作都相对简单,重点在于引用的修改和维护。

总结

LinkedList 不仅是一个简单的 List 实现,其也是一个双向队列实现。

如若转载,请注明出处:https://www.javaidea.cn/article/7967.html

(0)
上一篇 2022年2月7日 上午10:03
下一篇 2022年2月7日 上午10:03

相关推荐

发表评论

您的电子邮箱地址不会被公开。