java - Java中链表的栈操作

Question

我必须编写一个应该使用链表实现堆栈的类。但是，它应该从列表的尾部而不是头部执行推送和弹出操作。此外，它不应该维护对列表尾节点的引用。

在不保留对最后一个节点的引用的情况下，我究竟如何实现这一目标？

Answer 1

你可以这样做，但效率很低，因为每次你想做某事时都必须遍历整个列表。当所有操作都在尾部执行时，您确实没有任何理由要保留对头部的引用。

但无论如何我都会这样做：

class Entry<E> {
    E object;
    Entry<E> next;
    public Entry(E obj) {
        object = obj;
    }
}

class StackList<E> {
    Entry<E> head;
    public void push(E element) {
        if (head == null) {
            // first
            head = new Entry<E>(element);
            return;
        }
        Entry<E> node = head;
        while (node != null && node.next != null) {
            node = node.next;
        }
        // node is now the tail
        Entry<E> newEntry = new Entry<E>(element);
        node.next = newEntry;
    }
    public E pop() {
        if (head == null) {
            // empty
            return null;
        }
        Entry<E> node = head, previousNode = null;
        while (node.next != null) {
            previousNode = node;
            node = node.next;
        }
        // node is now the tail
        // previousNode is the next-to-last
        if (previousNode != null) {
            previousNode.next = null;
        } else {
            // there was only one thing
            head = null;
        }
        return node.object;
    }
}