1
\$\begingroup\$

I've written an implementation of a Stack data structure using a linked list.

Stack.java

import java.util.EmptyStackException;

public class Stack<T> {

    private class Node {

        private T data;
        private Node prev, next;

        public Node() {
        }

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

    private Node top;

    public Stack() {
        top = null;
    }

    public boolean empty() {
        return top == null;
    }

    public T peek() {
        if (top == null) {
            throw new EmptyStackException();
        }
        return top.data;
    }

    public T pop() {
        if (top == null) {
            throw new EmptyStackException();
        }
        T value = top.data;
        top = top.prev;
        return value;
    }

    public T push(T data) {
        Node temp = new Node(data);
        if (top == null) {
            top = temp;
        } else {
            top.next = temp;
            temp.prev = top;
            top = temp;
        }
        return temp.data;
    }
}
\$\endgroup\$
  • \$\begingroup\$ You are aware that the JDK contains a stack implementation using generics? docs.oracle.com/javase/7/docs/api/java/util/Deque.html \$\endgroup\$ – wumpz Mar 16 '16 at 12:39
  • 2
    \$\begingroup\$ Yes I am, but I'm going through the process of implementing my own data structures from scratch as practice. \$\endgroup\$ – j.castillo Mar 16 '16 at 16:24
5
\$\begingroup\$
public T push(T data) {
    Node temp = new Node(data);
    if (top == null) {
        top = temp;
    } else {
        top.next = temp;
        temp.prev = top;
        top = temp;
    }
    return temp.data;
}

This can be simplified; since both cases have top = temp at the end, you can move it out of the if statement:

public T push(T data) {
    Node temp = new Node(data);
    if (top == null) {
    } else {
        top.next = temp;
        temp.prev = top;    
    }
    top = temp;
    return temp.data;
}

And as a result of that, there's only 1 case you're interested in:

public T push(T data) {
    Node temp = new Node(data);
    if (top != null) {
        top.next = temp;
        temp.prev = top;    
    }
    top = temp;
    return temp.data;
}

public T peek() {
    if (top == null) {
        throw new EmptyStackException();
    }
    return top.data;
}

public T pop() {
    if (top == null) {
        throw new EmptyStackException();
    }
    T value = top.data;
    top = top.prev;
    return value;
}

I'd extract the throwing to a separate function, like so:

public void throwIfEmpty(){
    if(empty()){
        throw new EmptyStackException();
    }
}

and use like this:

public T pop() {
    throwIfEmpty();

    T value = top.data;
    top = top.prev;
    return value;
}

Keep the blank line in there, it's for showing the difference between your guard clauses and the code that does the work.


        top.next = temp;

This is the only part in your code where you set the next attribute. Since it's not read, it can go; you have no need for a doubly-linked list and can just use a singly linked list. It makes sense, because all you need to access is the top node; the other nodes aren't important.

We can further improve things:

public T push(T data) {
    Node temp = new Node(data);
    if (top != null) {
        top.next = temp;
        temp.prev = top;    
    }
    top = temp;
    return temp.data;
}

Now that we decided to remove the next setting,

public T push(T data) {
    Node temp = new Node(data);
    if (top != null) {
        temp.prev = top;    
    }
    top = temp;
    return temp.data;
}

we really don't need that null check anymore. Either it is null, in which case you're going to skip setting temp.prev to the null it already is, or it is not null, in which case you want to set the value.

In both cases, simply setting the value gives the wanted outcome: the code does not crash and the top node's prev pointer points to the lower node if it exists, else to null.

So remove the if statement.

public T push(T data) {
    Node temp = new Node(data);
    temp.prev = top;
    top = temp;
    return temp.data;
}

Final result:

import java.util.EmptyStackException;

public class Stack<T> {

    private class Node {

        private T data;
        private Node prev;

        public Node() {
        }

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

    private Node top;

    public Stack() {
        top = null;
    }

    public void throwIfEmpty(){
        if(empty()){
            throw new EmptyStackException();
        }
    }

    public boolean empty() {
        return top == null;
    }

    public T peek() {
        throwIfEmpty();
        return top.data;
    }

    public T pop() {
        throwIfEmpty();

        T value = top.data;
        top = top.prev;
        return value;
    }

    public T push(T data) {
        Node temp = new Node(data);
        temp.prev = top;
        top = temp;
        return temp.data;
    }
}
\$\endgroup\$
  • \$\begingroup\$ Excellent review. Good to see things I overlooked where improvements could be made to tidy things up. \$\endgroup\$ – j.castillo Mar 16 '16 at 16:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.