什么是鏈表

在閱讀本章之前，需要您知道什么是鏈表？

說到鏈表，那么就需要聊一聊計算機中的存儲方式。計算機中的存儲方式主要分為兩種，一種是順序存儲，一種是非順序存儲?？梢园且话?a target="_blank">這篇文章看一看。

鏈表是一種非順序存儲結(jié)構(gòu)，它允許保存的數(shù)據(jù)在內(nèi)存中可以不連續(xù)。

鏈表有以下4種

• 單向鏈表：每個節(jié)點有一個指針（next）指向下一個節(jié)點，最后一個節(jié)點指向null
• 雙向鏈表：每個節(jié)點有一個指針（next）指向下一個節(jié)點和一個指針(prev)指向上一個節(jié)點。第一個節(jié)點的prev為null，最后一個節(jié)點的next為null。
• 單向循環(huán)鏈表：最后一個節(jié)點的next指針指向第一個節(jié)點，如果只有一個節(jié)點，這個節(jié)點的next指向自己。
• 雙向循環(huán)鏈表：第一個節(jié)點的prev指向最后一個節(jié)點，最后一個節(jié)點的next指向第一個節(jié)點，如果只有一個節(jié)點prev和next都指向自己。

這里只簡單介紹鏈表，后面會寫文章詳細(xì)介紹鏈表及鏈表的實現(xiàn)。本文中我們用單向鏈表實現(xiàn)。

實現(xiàn)原理

定義兩個指針front和rear。front指向第一個元素，rear指向最后一個元素。

消費一個元素后，front指向這個元素的next。即下一個元素，當(dāng)消費完最后一個元素后(next == null)，front和rear都指向null。
添加元素后，rear所指向的元素的next指針指向新元素，同時rear也指向新元素。
需要在添加或者取出元素時維護(hù)隊列長度。

使用鏈表來實現(xiàn)隊列是比較簡單的，而且可以實現(xiàn)沒有長度限制的隊列。

實現(xiàn)代碼

package com.codestd.study.queue;

import java.util.NoSuchElementException;

/**
 * 鏈表方式實現(xiàn)隊列
 *
 * @author jaune
 * @since 1.0.0
 */
public class LinkedQueue<T> implements Queue<T> {
    private Node<T> front = null;
    private Node<T> rear = null;
    private int size = 0;
    private final Integer maxSize;

    /**
     * 不設(shè)置最大長度，則隊列的長度可以無限增加
     */
    public LinkedQueue() {
        this.maxSize = null;
    }

    /**
     * 設(shè)置隊列的最大長度，達(dá)到最大長度后不能再添加元素。
     * @param maxSize 最大長度
     */
    public LinkedQueue(Integer maxSize) {
        this.maxSize = maxSize;
    }

    @Override
    public T peek() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("隊列為空");
        }
        return this.front.item;
    }

    @Override
    public void push(T t) {
        if (this.isFull()) {
            throw new RuntimeException("隊列已滿，無法添加新的元素。");
        }
        if (this.size == 0) {
            this.front = new Node<>(t);
            this.rear = this.front;
        } else {
            Node<T> node = new Node<>(t);
            this.rear.next = node;
            this.rear = node;
        }
        this.size++;
    }

    @Override
    public T pop() {
        if (this.isEmpty()) {
            throw new NoSuchElementException("隊列為空");
        }
        Node<T> node = this.front;
        if (node.next == null) {
            this.front = null;
            this.rear = null;
            this.size = 0;
        } else {
            this.front = node.next;
            this.size--;
        }
        return node.item;
    }
    
    @Override
    public void clear() {
        // 這里清空所有引用，目的是為了便于垃圾回收。
        Node<T> node = this.front;
        while (node != null) {
            Node<T> next = node.next;
            node.item = null;
            node.next = null;
            node = next;
        }
        this.front = this.rear = null;
        this.size = 0;
    }

    @Override
    public int size() {
        return this.size;
    }

    @Override
    public boolean isEmpty() {
        return this.size == 0;
    }

    /**
     * 鏈表隊列不會有長度限制。
     */
    @Override
    public boolean isFull() {
        if (this.maxSize == null) {
            return false;
        } else {
            return size == maxSize;
        }
    }

    private static class Node<T> {
        T item;
        Node<T> next;

        public Node(T item) {
            this.item = item;
        }
    }
}

注意clear方法，clear方法中是將所有引用都清空了。這樣便于垃圾回收。java.util.LinkedList中的clear采用了另一種方法，下面將代碼貼出來供大家參考。

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