文章

01-链表-LinkedList-基础

什么是链表

链表是真正的动态数据结构
最简单的动态数据结构
更深入的理解引用(或者指针)
更深入的理解递归
辅助组成其他数据结构

链表的特点

数据存储在"节点(Node)"中

Lil-K1/11/24大约 7 分钟

02-带有头尾指针的链表

代码实现

public class LinkedListQueue<E> implements Queue<E> {

    private class Node {
        public E e;
        public Node next;

        public Node () {}

        public Node (E e) {
            this(e,null);
        }

        public Node (E e,Node next) {
            this.e = e;
            this.next = next;
        }
    }

    private Node head, tail;

    private int size;

    public LinkedListQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    @Override
    public int getSize() {
        return size;
    }

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

    /**
     * 入队
     * @param e
     */
    @Override
    public void enqueue(E e) {
        if (tail == null) {
            tail = new Node(e);
            head = tail;
        }else {
            tail.next = new Node(e);
            tail = tail.next;
        }

        size++;
    }

    /**
     * 出队
     * @return
     */
    @Override
    public E dequeue() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }
        // 记录出队元素
        Node retNode = head;

        // 维护链表 head的位置
        head = head.next;

        // 将出队的位置变为null
        retNode.next = null;

        /**
         * 当队列只剩一个元素时,head.next == null
         * 所以要维护一下 tail
         */
        if (head == null) {
            tail = null;
        }
        size--;
        return (E)retNode.e;
    }

    /**
     * 获取队首元素
     * @return
     */
    @Override
    public E getFront() {
        if (isEmpty()) {
            throw new IllegalArgumentException("Cannot dequeue from an empty queue.");
        }

        return head.e;
    }

    @Override
    public String toString() {
        StringBuilder res = new StringBuilder();
        Node cur = head;
        while (cur != null) {
            res.append(cur + "->");
            cur = cur.next;
        }
        res.append("null tail");
        return res.toString();
    }
}