Code Review Stack Exchange is a question and answer site for peer programmer code reviews. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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;
    }
}
share|improve this question
    
You are aware that the JDK contains a stack implementation using generics? docs.oracle.com/javase/7/docs/api/java/util/Deque.html – wumpz Mar 16 at 12:39
1  
Yes I am, but I'm going through the process of implementing my own data structures from scratch as practice. – j.castillo Mar 16 at 16:24
up vote 5 down vote accepted
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;
    }
}
share|improve this answer
    
Excellent review. Good to see things I overlooked where improvements could be made to tidy things up. – j.castillo Mar 16 at 16:27

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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