ADT Stack with LinkedList

Question

I am currently preparing for my exam and I am trying to implement some abstract data types with linked lists as preparation for the exam. I found an older exam from my prof. and he wants us to implement an ADT stack with an inner class ListElement.

He has given us the interface, so it doesn't need to be implemented. He wants us to use his given methods, so we are not allowed to change them. This is what I did and I am not sure whether it is right or wrong.

public class Stack<T> implements ADTStack<T> {
    private ListElement<T> firstElement;
    int size = 0;

    public Stack() {
        firstElement = null;
    }

    public static void main(String[] args) {
        // TODO Auto-generated method stub
    }

    @Override
    public void push(T element) {
        if (empty()) {
            firstElement = new ListElement(element);
            size++;
        }
        else {
            firstElement.nextElement = firstElement;
            firstElement = new ListElement(element);
            size++;
        }
    }

    @Override
    public void pop() {
        if (empty()) {
            throw new RuntimeException("stack is empty");
        }
        else {
            T element = top();
            firstElement = firstElement.nextElement;
            size--;
        }
    }

    @Override
    public T top() {
        if (empty()) {
            return null;
        }
        else {
            return firstElement.element;
        }
    }

    @Override
    public boolean empty() {
        return (firstElement == null);
    }

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

    public class ListElement<T> {
        private T element = null;
        private ListElement<T> nextElement = null;

        public ListElement(T element) {
            this.element = element;
        }

        public T getElement() {
            return element;
        }

        public ListElement<T> getNextElement() {
            return nextElement;
        }

        public void setNextElement(ListElement<T> element) {
            this.nextElement = nextElement;
        }
    }
}

Answer 1

Don't use bare types

It seems you forgot to specify the type parameter here:

firstElement = new ListElement(element);

It should have been (as of Java 7):

firstElement = new ListElement<>(element);

Avoid duplicated logic

Notice the duplicated logic here:

if (empty()) {
    firstElement = new ListElement<>(element);
    size++;
} else {
    firstElement.nextElement = firstElement;
    firstElement = new ListElement<>(element);
    size++;
}

size++ appears at the end of both branches: it could be done after the conditional.

The assignment firstElement = new ListElement<>(element); is right before size++ at the end of both branches, so that too can be done after the conditional.

Without these duplications, the code becomes simpler:

if (!empty()) {
    firstElement.nextElement = firstElement;
}
firstElement = new ListElement<>(element);
size++;

Unnecessary statements

In pop, this statement is unnecessary, you can delete it:

T element = top();

And since the if branch throws an exception, you can eliminate the else branch, like this:

public void pop() {
    if (empty()) {
        throw new RuntimeException("stack is empty");
    }
    firstElement = firstElement.nextElement;
    size--;
}

Follow good examples in the JDK

Take a look at the pop and peek methods of the Javadoc of Stack: when the stack is empty, they both throw EmptyStackException. I advise you do likewise.

Working with inner classes

The inner class ListElement holds a reference to the enclosing class (as all non-static inner classes do). In your example, this is unnecessary. Make this inner class static, so that it becomes independent from the enclosing class. This improves performance, and also solves another problem that the type parameter T in ListElement<T> shadows the type parameter T of the enclosing Stack<T>.

Keep your toolbox clean

A Stack is a utility class, potentially a useful element in your programming toolbox. This method doesn't belong in it:

public static void main(String[] args) {
    // TODO Auto-generated method stub
}

The method does nothing, so it's pointless. It has a default TODO comment, which you should always delete when you're done working, for example before asking for a code review. If later you want to demonstrate the functionality of the stack by creating a runnable class with a main method, do it in another class (say, StackDemo), not in this one.

Answer 2

I have embedded the comments directly in the code whenever I have something to say:

import java.util.NoSuchElementException;

public class Stack<T> { 
    private ListElement<T> firstElement;

    // In Java, the default value for integer fields is zero (0). You don't need
    // the following assignment.
    // int size = 0;
    int size;

    // The default value for a reference field IS null.
    // public Stack() {
    //    firstElement = null;
    //}

    // Try to put this main somewhere else (for instance, StackDemo.java).
    public static void main(String[] args) {
        Stack<Integer> stack = new Stack<>();

        for (int i = 0; i < 5; ++i) {
            stack.push(i);
        }

        while (!stack.empty()) {
            System.out.println(stack.top());
            stack.pop();
        }
    }

    // You had a nasty bug in your push.
//    @Override
    public void push(T element) {
        ListElement<T> newElement = new ListElement<>(element);
        // Why don't you use your element setters/getters if you defined them?
        // newElement.nextElement = firstElement;
        newElement.setNextElement(firstElement);
        firstElement = newElement;
        ++size;
    }

//    @Override
    public void pop() {
        if (empty()) {
            // JDK Stack throws NoSuchElementException on popping from empty 
            // stack. 
            throw new NoSuchElementException("Stack is empty.");
        }

        // Unnecessary 'else' and 'top()'.
        firstElement = firstElement.getNextElement();
        size--;
    }

//    @Override
    public T top() {
        // Much shorter:
        return empty() ? null : firstElement.element;
//        if (empty()) {
//            return null;
//        }
//        else {
//            return firstElement.element;
//        }
    }

//    @Override
    public boolean empty() {
        // You don't have to use parenthesis here. Spare them for more complex
        // expressions.
        return firstElement == null;
    }

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

    //
    // The keyword 'static' removes the reference to an owner 'Stack' from each
    // 'ListElement'. Because: (1) you don't need them here. 
    //                         (2) you save some memory.
    // Also, add 'private' in order to hide the implementation.
    private static class ListElement<T> {
        // Once again, in Java each reference in an object is by default 
        // initialized with 'null'.
        private T element;
        private ListElement<T> nextElement;
//        private T element = null;
//        private ListElement<T> nextElement = null;

        public ListElement(T element) {
            this.element = element;
        }

        public T getElement() {
            return element;
        }

        public ListElement<T> getNextElement() {
            return nextElement;
        }

        public void setNextElement(ListElement<T> element) {
            // Here, you assign this.nextElement to itself!
            // this.nextElement = nextElement;
            this.nextElement = element;
        }
    }
}