Java Data Structures and Algorithms. Stacks, implementing a Singly Linked List Stack

Introduction

• This series is going to be dedicated to learning and understanding data structures and algorithms in Java. All the information I am using is coming from the book, Data Structures and Algorithms in Java by Michael T. Goodrich and Roberto Tamassia and the California State Polytechnic University course, which is free and can be found HERE, shout out professor Tang. Please do not buy the book it is expensive and can be found online for MUCH cheaper.

YouTube version:

• YouTube version of this blog post can be found HERE

GitHub code

• GitHub for the code can be found HERE

Singly linked list implementation

• If you are unfamiliar with how to create a Singly linked list, you can check out my YouTube video HERE

Singly Linked List Stack

• Unlike the array based implementation from the previous post, the singly linked list implementation has memory usage that is always proportional to the number of actual elements currently in the stack. Also, unlike arrays this implementation has no fixed capacity.
• Our first order of business, is to decide which end of the linked list is going to be the top of the stack and which end is going to be the bottom. The answer to this problem lies in algorithm analysis, specifically that we want operations on data structures to be in O(1) constant or O(logN) logarithmic time. So with this in mind I want you to look at the singly linked list and decide which end can we remove and add items to in O(1) or O(logN) time..... The answer is the front of the singly linked list, because only in the front of the linked list we can remove and add items in O(1) time. For more details checkout the YouTube version of this post.

Adapter pattern

• In order to make the Stack and Singly Linked List work together we are going to implement the adapter pattern. Which is a pattern where we modify an existing class so that its methods match those of a related but different class or interface. The main way to apply this pattern is to define a new class in such a way that it contains an instance of the existing class as a hidden field, and then to implement each method of the new class using methods of this hidden instance variable.

Implementing the adapter pattern

• 1) The first thing that we need to do is to create a new class and have it implement the Stack interface that we created in the last blog post.

public class LinkedStack <E> implements Stack<E>{}

• 2) Next we implement the adapter pattern and create a private instance variable that all the methods will use.

public class LinkedStack <E> implements Stack<E>{
   private SinglyLinkedList<E> list = new SinglyLinkedList<>();

}

• 3) Lastly we will implement all the methods and have them make calls to our singly linked list instance variable, list.

public class LinkedStack <E> implements Stack<E>{
   private SinglyLinkedList<E> list = new SinglyLinkedList<>();
   @Override
    public int size() {
        return list.size();
    }

    @Override
    public boolean isEmpty() {
        return list.isEmpty();
    }

    @Override
    public E top() {
        return list.first();
    }

    @Override
    public void push(E e) {
        list.addFirst(e);

    }

    @Override
    public E pop() {
        return list.removeFirst();
    }

• Now we both have a Singly Linked List Stack implementation that operates in O(1) time, very cool!!

Conclusion

• Thank you for taking the time out of your day to read this blog post of mine. If you have any questions or concerns please comment below or reach out to me on Twitter.