10
\$\begingroup\$

To understand the concept, I implemented the stack operations using a linked list. Please review the code and tell me your suggestions.

Node.java

public class Node {

public int data;
public Node next;

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

public void displayNode() {
    System.out.print(data);
    System.out.print("  ");

 }
}

LinkList.java

public class LinkList {

private Node first = null;

public void insertFirst(int data) {
    Node n = new Node(data);
    n.next = first;
    first = n;
}

public Node deleteFirst() {
    Node temp = first;
    first = first.next;
    return temp;
}

public void displayList() {
    Node current = first;
    while (current != null) {
        current.displayNode();
        current = current.next;
    }
}

public boolean isEmpty() {
    return (first == null);
  }
}

LinkListStack.java

public class LinkListStack {

LinkList li = new LinkList();

public void push(int data) {
    li.insertFirst(data);
}

public void pop() {
    while(!li.isEmpty()){
    li.deleteFirst();
    }
}

public void displayStack() {
    System.out.println("  ");
    li.displayList();
  }
}

LinkListStackDemo.java

public class LinkListStackDemo {

public static void main(String[] args) {
    LinkListStack st = new LinkListStack();

    st.push(50);
    st.push(70);
    st.push(190);
    st.displayStack();
    st.pop();
    st.displayStack();

  }
 }
\$\endgroup\$
18
\$\begingroup\$

Time complexity

The time complexity of push and pop operations should be \$O(1)\$, and so it is in your case too. It doesn't matter how many elements you have, these operations should take constant time. (UPDATE: you've edited your original post, and made pop wipe out the entire stack. That's not normal! Normally, the pop operation on a stack should return the most recently added value. That's \$O(1)\$ time.)

Avoid printing to stdout

Instead of the display* methods that print to stdout, it would be better to override toString. That way your implementation would be more testable.

Generalize

Why limit the stack, linked list, node elements to int type? It would be trivially easy to rewrite to make it work with any type T.

The question is tagged "beginner", so I understand you might not be familiar with generics just yet. In that case, see this official tutorial. Or perhaps you can also learn from my example implementation further down.

Add an isEmpty method for the stack

Your linked list has an isEmpty method but the stack doesn't. It would be good to have such method for the stack too.

Reinventing the wheel

When reinventing the wheel (here, linked list), it's good to mimic what exists. For example, java.util.LinkedList uses the method names addFirst and removeFirst, instead of insertFirst and deleteFirst. It's good to follow the example.

Access modifiers and encapsulation

As @rolfl pointed out, Node should not be exposed to the outside. Users of the stack should not have to know its inner workings.

Also, the members of Node should be private, and the data and next fields can be final. Similarly in the stack, the linked list member should be private.

Naming

You use poor names in many places.

  • Instead of n for the new node when replacing the first item of a linked list, newFirst would be more intuitive
  • Instead of temp for the old first item removed from a linked list, oldFirst would be more intuitive
  • Instead of li for the linked list in the stack, linkedList would be more intuitive

Suggested implementation

class LinkList<T> {

    private static class Node<T> {

        private final T data;
        private final Node<T> next;

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

        @Override
        public String toString() {
            return data.toString();
        }
    }

    private Node<T> first = null;

    public void addFirst(T data) {
        Node<T> newFirst = new Node<T>(data);
        newFirst.next = first;
        first = newFirst;
    }

    public T removeFirst() {
        Node<T> oldFirst = first;
        first = first.next;
        return oldFirst.data;
    }

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node current = first;
        while (current != null) {
            builder.append(current).append(" ");
            current = current.next;
        }
        return builder.toString();
    }

    public boolean isEmpty() {
        return first == null;
    }

}

class LinkListStack<T> {

    private final LinkList<T> linkedList = new LinkList<>();

    public void push(T data) {
        linkedList.addFirst(data);
    }

    public T pop() {
        return linkedList.removeFirst();
    }

    public boolean isEmpty() {
        return linkedList.isEmpty();
    }

    @Override
    public String toString() {
        return linkedList.toString();
    }
}

Unit tests

@Test
public void testPushAndPop() {
    LinkListStack<Integer> st = new LinkListStack<>();
    st.push(50);
    st.push(70);
    st.push(190);
    assertEquals("190 70 50", st.toString());
    assertEquals(190, (int) st.pop());
    assertEquals("70 50", st.toString());
}

@Test
public void testPopUntilEmpty() {
    List<Integer> values = Arrays.asList(50, 70, 190, 20);
    LinkListStack<Integer> st = new LinkListStack<>();
    assertTrue(st.isEmpty());
    for (Integer value : values) {
        st.push(value);
    }
    assertFalse(st.isEmpty());
    for (int i = values.size(); i > 0; --i) {
        assertEquals(values.get(i - 1), st.pop());
    }
    assertTrue(st.isEmpty());
}
\$\endgroup\$
8
\$\begingroup\$

Well, there are a few things to go through here.

Node

Starting with the Node class. This should not be public. There is no reason for you to expose the logic to anything other than the LinkedList class. It is common to include the Node class as a static inner class of the data structure. Something like:

public class LinkList {

    private static class Node {

        int data;
        Node next;

        Node(int data) {
            this.data = data;
        }

        void displayNode() {
            System.out.print(data);
            System.out.print("  ");

        }

    }

    private Node first = null;

    ...

Complexity

You assert that the complexities for the push and pop are \$O(n)\$, but this is not true. Both of these operations affect only the head of the list, e.g.:

public void insertFirst(int data) {
    Node n = new Node(data);
    n.next = first;
    first = n;
}

As a consequence, they are \$O(1)\$ operations, and that is what I would expect for a linked list insert-at-the-head.

LinkedList

The deleteFirst method should not return a Node value. It should be the 'mirror image' of the insert method. The insert method inserts an int, and the delete method should return an int as well.

LinkedListStack

pop() methods should return the popped value. Yours returns nothing, it's void. It is not normal.

Note: it has been pointed out that your pop method removes all values from the list because of the while (!isEmpty()) loop. This loop was added after I wrote this part of the answer (but before I pressed 'submit'). The sentence I have above is accurate for a classic 'pop' method, which removes the first value from the stack (and in Java, and many other languages, returns that value too).

What you have now is worse, you have a method called 'pop' which does nothing of the sort, it is a 'clear' method, it empties the stack. As a result, you do not have a stack at all, you have a class called a Stack that is not a Stack. Additionally, it is in many cases WOM (Write Only Memory), you can write values to the Stack, but never read them.

Summary

Your indentation is off. I presume this is because you are not familiar with Code Review's markdown system. You should paste your code in to the edit box, then select it all, and then press ctrl-k.

\$\endgroup\$
  • \$\begingroup\$ pop() returning nothing is not normal in Java particularly, you mean? In C++, it is normal. \$\endgroup\$ – Jamal Sep 12 '14 at 5:10
  • 2
    \$\begingroup\$ @Jamal Maybe because C++ tries to save every fraction of nanosecond which returning an unused value could cost. Actually, it could be costly if a big object was to be copied and the compiler isn't guaranteed to see it can omit it. This can't happen in Java. That said, it's sad that Java Collection aren't more STL inspired. \$\endgroup\$ – maaartinus Sep 12 '14 at 5:31
  • \$\begingroup\$ Note that pop() is a while loop; not only does it not return anything, but it destroys the entire stack. \$\endgroup\$ – raptortech97 Sep 12 '14 at 11:11
  • 1
    \$\begingroup\$ @maaartinus - the reason that pop does not return an object in C++ is that returning an object copies it, and copying can throw an exception. If that happens, the object has been lost. \$\endgroup\$ – Pete Becker Sep 12 '14 at 13:43
  • 1
    \$\begingroup\$ @maaartinus - yes, call top to get the object. top won't throw an exception: it returns a reference. If you copy that object and the copy throws an exception the stack is still intact, so you haven't lost anything. Worst case you call pop to get rid of the troublemaker. \$\endgroup\$ – Pete Becker Sep 12 '14 at 14:53
2
\$\begingroup\$

Why do you write

public void pop() {
    while(!li.isEmpty()){
    li.deleteFirst();
    }
}

instead of

public void pop() {
    if(!li.isEmpty()){
    li.deleteFirst();
    }
}

because the you wrote it, pop() would pop all of the elements off the stack, instead of one. Or am I mistaken?

\$\endgroup\$
  • \$\begingroup\$ This is not really an answer. In fact it has a question at the end. Please amend this to more closely follow the structure of an answer. \$\endgroup\$ – Boris the Spider Sep 12 '14 at 15:20

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.