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

文章目录

1. LinkedList类图总览
2. 源码分析
- 2.1. 数据节点
- 2.2. LinkedList拥有的属性
- 2.3. LinkedList构造函数
- 2.4. LinkedList相关操作
- - 2.4.1. 添加元素
  - - 2.4.1.1. 头插
    - 2.4.1.2. 尾插
    - 2.4.1.3. 中间插入
  - 2.4.2. 删除元素
  - - 2.4.2.1. 删除头节点
    - 2.4.2.2. 删除尾节点
    - 2.4.2.3. 根据元素删除
    - 2.4.2.4. 根据索引删除
3. LinkedList作为队列
- 3.1. 入队操作
- - 3.1.1. add
  - 3.1.2. addLast
  - 3.1.3. offerLast
  - 3.1.4. offer
- 3.2. 出队操作
- - 3.2.1. remove
  - 3.2.2. removeFirst
  - 3.2.3. poll
  - 3.2.4. pollFirst
- 3.3. 获取队首元素
- - 3.3.1. element
  - 3.3.2. peek
4. LinkedList作为栈
- 4.1. 进栈操作
- - 4.1.1. push
- 4.2. 出栈操作
- 4.3. 获取顶部元素

1. LinkedList类图总览

从类图中可以看到LinkedList继承了AbstractSequentialList，同时实现了List、Deque、Cloneable、java.io.Serializable。

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

Deque：双向队列

public interface Deque extends Queue

Queue：队列

2. 源码分析 2.1. 数据节点

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

2.2. LinkedList拥有的属性

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

    
    transient Node first;

    
    transient Node last;

2.3. LinkedList构造函数

    
    public LinkedList() {
    }

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

2.4. LinkedList相关操作 2.4.1. 添加元素 2.4.1.1. 头插

    
    private void linkFirst(E e) {
        //头节点
        final Node f = first;
        //定义一个新的节点，元素为e，next指向头节点
        final Node 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++;
    }
    
    
    public void addFirst(E e) {
        linkFirst(e);
    }

2.4.1.2. 尾插

    
    void linkLast(E e) {
        //尾节点
        final Node l = last;
        //定义一个新的节点，元素为e，prev指向尾节点
        final Node 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++;
    }

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

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

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

    
    void linkBefore(E e, Node succ) {
        // assert succ != null;
        //定义succ的前驱节点为pred
        final Node pred = succ.prev;
        //新节点的前驱为pred，后继为succ
        final Node 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++;
    }

2.4.2. 删除元素 2.4.2.1. 删除头节点

    public E removeFirst() {
        final Node f = first;
        if (f == null)
            throw new NoSuchElementException();
        return 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;
    }

2.4.2.2. 删除尾节点

 
    public E removeLast() {
        final Node l = last;
        if (l == null)
            throw new NoSuchElementException();
        return 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;
    }

2.4.2.3. 根据元素删除

public boolean remove(Object o) {
        if (o == null) {
            for (Node x = first; x != null; x = x.next) {
                if (x.item == null) {
                    unlink(x);
                    return true;
                }
            }
        } else {
            for (Node x = first; x != null; x = x.next) {
                if (o.equals(x.item)) {
                    unlink(x);
                    return true;
                }
            }
        }
        return false;
    }

    
    E unlink(Node x) {
        // assert x != null;
        final E element = x.item;
        final Node next = x.next;
        final Node 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;
    }

2.4.2.4. 根据索引删除

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

    
    E unlink(Node x) {
        // assert x != null;
        final E element = x.item;
        final Node next = x.next;
        final Node 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;
    }

3. LinkedList作为队列

队列：先进先出

ListLinked queue = new LinkedList<>();

3.1. 入队操作

在链表的尾部添加节点

3.1.1. add

public boolean add(E e)

示例：

queue.add("1");

源码：

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

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

3.1.2. addLast

public void addLast(E e)

示例：

queue.addLast("2");

源码：

    public void addLast(E e) {
        linkLast(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++;
    }

3.1.3. offerLast

public boolean offerLast(E e)

示例：

queue.offerLast("3");

源码：

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

    public void addLast(E e) {
        linkLast(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++;
    }

3.1.4. offer

public boolean offer(E e)

示例：

queue.offer("4");

源码：

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

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

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

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

3.2. 出队操作

从链表的头部删除节点

3.2.1. remove

public E remove()

示例：

queue.remove();

源码：

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

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

3.2.2. removeFirst

public E removeFirst()

示例：

queue.removeFirst();

源码：

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

3.2.3. poll

public E poll()

示例：

queue.poll();

源码：

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

3.2.4. pollFirst

public E pollFirst()

示例：

queue.pollFirst();

源码:

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

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

3.3. 获取队首元素 3.3.1. element

public E element()

示例：

queue.element();

源码：

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

    public E getFirst() {
        final Node f = first;
        if (f == null)
            throw new NoSuchElementException();
        return f.item;
    }

3.3.2. peek

public E peek()

示例：

queue.peek();

源码：

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

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

4. LinkedList作为栈

栈：后进先出

ListLinked stack = new LinkedList<>();

4.1. 进栈操作

从链表的头部添加节点

4.1.1. push

 public void push(E e)

示例：

stack.push();

源码：

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

    public void addFirst(E e) {
        linkFirst(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++;
    }

4.2. 出栈操作

从链表的头部删除节点

同：队列的出队操作

4.3. 获取顶部元素

同：队列获取队首元素

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

Java相关栏目本月热门文章