11. LinkedStack

• The Stack was defined with an interface

• An array based implementation of the stack was created — ArrayStack

• Now, being aware of linked structures, a linked based stack may be implemented — LinkedStack

11.1. Stack ADT

• The Stack interface was already written

• Remember, based on the interface, a stack must implement the following methods

  • push

  • pop

  • peek

  • isEmpty

  • size

• Also remember that the interface strictly defines the what and says nothing about the how

11.2. Implementing a Stack with a Linked Structure

• The top of the stack will be managed by a field called top that is a reference to the head of a linked structure

• All pushing and popping will happen at the head end of the linked structure

• An additional field will be needed to keep track of the size of the stack

An example LinkedStack containing four elements. Note the value stored in top is a reference to a Node object that contains the element on the top of the stack.

The state of the LinkedStack after an element was pushed. Note that top changed to reference a new Node containing the newly pushed element.

The state of the LinkedStack after an element was popped. Note that top changed to reference the Node that was after the Node that contained the element on the top of the stack (the Node that was removed).

The state of the LinkedStack after another element was popped. Note that, again, top changed to reference the Node that was after the Node that contained the element on the top of the stack.

11.3. Implementation

/**
 * Implementation of a stack with a linked structure as the container. The class contains a static inner class defining
 * a node for the linked structure.
 *
 * @param <T> Type of elements that are to be in the stack
 */
public class LinkedStack<T> implements Stack<T> {

    private Node<T> top;
    private int size;

    /**
     * Create an empty LinkedStack.
     */
    public LinkedStack() {
        top = null;
        size = 0;
    }

• Like the ArrayStack, the LinkedStack will implement the Stack interface

• The constructor creates an empty stack with nothing in it

11.3.1. Push

    @Override
    public boolean push(T element) {
        Node<T> toPush = new Node<T>(element);
        toPush.setNext(top);
        top = toPush;
        size++;
        return true;
    }

• In push, notice how this is just adding to the front of a linked structure

11.3.2. Pop & Peek

    @Override
    public T pop() {
        if (isEmpty()) {
            throw new NoSuchElementException("Empty stack");
        }
        T returnElement = top.getData();
        top = top.getNext();
        size--;
        return returnElement;
    }

    @Override
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException("Empty stack");
        }
        return top.getData();
    }

• Like the ArrayStack, popping or peeking from an empty stack throws an exception

• Notice how pop does a remove/delete from the front of a linked structure

11.3.3. size and isEmpty

    @Override
    public boolean isEmpty() {
        return size() == 0;
    }

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

• The LinkedStack is empty if its size() == 0

  • How else could this condition be checked?

11.3.4. toString

    @Override
    public String toString() {
        StringBuilder builder = new StringBuilder();
        Node<T> currentNode = top;
        while (currentNode != null) {
            builder.append(currentNode.getData());
            builder.append(", ");
            currentNode = currentNode.getNext();
        }
        return builder.toString();
    }

• This is matching the output format that the ArrayStack's toString had

11.3.5. equals & hashCode

    @Override
    public boolean equals(Object o) {
        if (this == o) {
            return true;
        }
        if (o == null || getClass() != o.getClass()) {
            return false;
        }
        LinkedStack<?> that = (LinkedStack<?>) o;
        if (this.size() != that.size()) {
            return false;
        }
        Node<?> thisCurrent = this.top;
        Node<?> thatCurrent = that.top;
        while (thisCurrent != null && thatCurrent != null) {
            if (!Objects.equals(thisCurrent.getData(), thatCurrent.getData())) {
                return false;
            }
            thisCurrent = thisCurrent.getNext();
            thatCurrent = thatCurrent.getNext();
        }
        return true;
    }

    @Override
    public int hashCode() {
        int result = Objects.hashCode(size);
        Node<?> current = top;
        while (current != null) {
            result = result * 97 + Objects.hashCode(current.getData());
            current = current.getNext();
        }
        return result;
    }

11.4. Nested Node Class

• Consider the doubly linked structure

• Since this structure need a reference to both the next and previous nodes, the existing Node class will not work

• Also consider that the Node class would only be used for a linked implementation of something

  • As far as the user of a LinkedStack is concerned, they don’t care about the Node class, they just care that the LinkedStack works

    • I don’t know, I don’t want to know

  • Similar idea to the private method expandCapacity in the ArrayStack

• Does it make sense to have the Node class accessible from everywhere?

11.4.1. Nested Classes

• Thinking about the doubly linked structure, what should the node class be called, Node?

  • This would be a problem if there already exists a Node class

• Instead, the Node class can be put inside the LinkedStack class

  • If this is done, the Node class can still be accessed by the LinkedStack class

  • But, it’s only accessible from within that class, so it keeps the Node class out of the way of all other classes

• Going back to the doubly linked structure, a Node class can exist within the class using the doubly linked structure

  • It will not introduce any ambiguity since the singly linked and doubly linked structure’s Node classes are nested within their respective classes

• Perhaps this is not that big of a problem, and there are other ways around it

• But since the two classes are inextricably connected, nesting Node makes sense

11.4.2. Nesting in LinkedStack

• Below is an example of the nested Node class at the end of the LinkedStack class

  • Notice that it is both private and static

    /**
     * A node class for a singly linked structure. Each node contains a nullable reference to data of type T, and a
     * reference to the next/subsequent/successor singly linked node, which may be a null reference.
     *
     * @param <T> Type of the data being stored in the node
     */
    private static class Node<T> {

        private T data;
        private Node<T> next;

        public Node() {
            this(null);
        }

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

        public T getData() {
            return data;
        }

        public void setData(T data) {
            this.data = data;
        }

        public Node<T> getNext() {
            return next;
        }

        public void setNext(Node<T> next) {
            this.next = next;
        }
    }

11.5. For Next Time

• Read Chapter 4 Section 6

  • 13 pages

11.5.1. Playing Code

• Download and play with

  • LinkedStack

  • LinkedStackTest

  • LinkedStack playing code

• One could use the same code from PlayingArrayStack to play with the LinkedStack

• Only need to make one change

  • ArrayStack -> LinkedStack

• If everything was done correctly, the following code from PlayingLinkedStack should work

import java.util.NoSuchElementException;

public class PlayingLinkedStack {
    public static void main(String[] args) {
        // Create a LinkedStack
        Stack<Integer> myStack = new LinkedStack<>();

        // Check stack is empty
        System.out.println(myStack.size());
        System.out.println(myStack.isEmpty());
        System.out.println(myStack);

        // Test push
        myStack.push(0);
        myStack.push(1);
        myStack.push(2);
        myStack.push(3);
        myStack.push(4);
        System.out.println(myStack.size());
        System.out.println(myStack.isEmpty());
        System.out.println(myStack);

        // No test for expandCapacity since LinkedStack
        // doesn't need it, but test more pushes anyways
        // as the functionality does not change either way
        myStack.push(10);
        myStack.push(11);
        myStack.push(12);
        myStack.push(13);
        myStack.push(14);
        System.out.println(myStack.size());
        System.out.println(myStack.isEmpty());
        System.out.println(myStack);

        // Test peek
        System.out.println(myStack.peek());
        System.out.println(myStack.size());
        System.out.println(myStack.isEmpty());
        System.out.println(myStack);

        // Test Pop
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.pop());
        System.out.println(myStack.size());
        System.out.println(myStack.isEmpty());
        System.out.println(myStack);

        // Test peek and pop throwing exception
        try {
            myStack.peek();
        } catch (NoSuchElementException e) {
            e.printStackTrace();
        }
        try {
            myStack.pop();
        } catch (NoSuchElementException e) {
            e.printStackTrace();
        }
    }
}