HiveBrain v1.2.0
Get Started
← Back to all entries
patternjavaModerate

Stack implementation using a linked list

Submitted by: @import:stackexchange-codereview··
0
Viewed 0 times
stackusingimplementationlistlinked

Problem

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();

  }
 }

Solution

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 {

    private static class Node {

        private final T data;
        private final Node next;

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

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

    private Node first = null;

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

    public T removeFirst() {
        Node 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 {

    private final LinkList 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 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 values = Arrays.asList(50, 70, 190, 20);
    LinkListStack 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());
}

Code Snippets

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();
    }
}
@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());
}

Context

StackExchange Code Review Q#62710, answer score: 18

Revisions (0)

No revisions yet.