Linked List - Clean Design

Definition

When each item contained within itself the address of the next item, such explicit ordering gives rise to a data structure which is known as a linear linked list. Each item in the list is called a node and contains two fields, an information field and a next address field.

Clean Design of Linked List

As per the linked list definition, there is a separation between the structured data and its allocation or deallocation. By this separation more controlled is gained on the object creation or destruction. Hence the design for this should also follow the same separation of structured data and instantiations. 

To do that we first define contract and implementations for the structured data

package clean.project.ds.linkedlist.model.contract;

public interface Node<T> {
    public T getInfo();
    public void setInfo(final T info);
}

package clean.project.ds.linkedlist.model.contract;

public interface LinkedNode<T> extends Node<T> {
    public LinkedNode<T> getNext();
    public void setNext(final LinkedNode<T> next);
}

package clean.project.ds.linkedlist.model.contract;

public interface DoublyLinkedNode<T> extends LinkedNode<T> {
    public DoublyLinkedNode<T> getPrevious();
    public void setPrevious(final DoublyLinkedNode<T> previous);
}

The implementations of the structured data will look like this as plug-ins.

Next we will define the creation & removal operations for nodes. These we choose to define as separate interfaces as we want to give flexibility to have either or both of the operations implemented for some type of linked list implementation without making anything mandatory.

package clean.project.ds.linkedlist.operations.contract;

import clean.project.ds.linkedlist.model.contract.DoublyLinkedNode;
import clean.project.ds.linkedlist.model.contract.LinkedNode;

public interface Creation<T> {
    public LinkedNode<T> getLinkedNode(final T info);
    public DoublyLinkedNode<T> getDoublyLinkedNode(final T info);
}

package clean.project.ds.linkedlist.operations.contract;

import clean.project.ds.linkedlist.model.contract.DoublyLinkedNode;
import clean.project.ds.linkedlist.model.contract.LinkedNode;

public interface Removal<T> {
    public void freeLinkedNode(final LinkedNode<T> linkedNode);
    public void freeDoublyLinkedNode(final DoublyLinkedNode<T> doublyLinkedNode);
}

And we implement these operations, either to have a simple operation which continuously creates and discards the nodes after use or a pooled implementation which keeps nodes for reuse.

To manage the creation of linked nodes, we implement the factory for them as indicated in the below UML diagram

Application of Linked List

Stack as Linked List

Here we will implement stack using linked list and use this version of stack implementation to write the algorithm for parentheses syntax checker

We extend the PrimitiveStack interface (refer the stack blog here) for the linked list version of stack, which is going to be an unlimited stack as with the linked list, it can grow dynamically until the memory is available.

package clean.project.ds.stack.contract;

public interface UnlimitedStack<T> extends PrimitiveStack<T> {
    public boolean isEmpty();
}

 And our implementation of this version of stack with linked list looks like this.

package clean.project.ds.stack.impl;

import clean.project.ds.linkedlist.model.contract.LinkedNode;
import clean.project.ds.linkedlist.operations.impl.PooledOperations;
import clean.project.ds.stack.contract.UnlimitedStack;

public class UnlimitedStackLinkedListImpl<T> implements UnlimitedStack<T> {
    private PooledOperations<T> pooledOperations = new PooledOperations<T>();
    private LinkedNode<T> topNode;

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

    public void push(T item) throws Exception {
        if (isEmpty()) {
            topNode = pooledOperations.getLinkedNode(item);
        } else {
            LinkedNode<T> tempNode = pooledOperations.getLinkedNode(item);
            tempNode.setNext(topNode);
            topNode = tempNode;
        }
    }

    public T pop() throws Exception {
        if (null == topNode) {
            throw new Exception("Stack is empty");
        } else {
            LinkedNode<T> tempNode = topNode;
            topNode = tempNode.getNext();
            T item = tempNode.getInfo();
            pooledOperations.freeLinkedNode(tempNode);
            return item;
        }
    }
}

The new implementation looks like this for stacks.

Stack factory now looks like this

And finally the parentheses syntax checker with the linked list version of stack.

package clean.project.ds.linkedlist.application;

import clean.project.ds.stack.contract.UnlimitedStack;
import clean.project.ds.stack.factory.StackFactoryBuilder;

public class ParenthesesCheckerLinkedListStack {
    private static StackFactoryBuilder<Character> characterStackFactoryBuilder = new StackFactoryBuilder<Character>();

    private boolean checkParenthesisSyntax(final String input) throws Exception {
        final UnlimitedStack<Character> characterUnlimitedStack = characterStackFactoryBuilder.buildUnlimitedStackLinkedListFactory().getStack(-1);
        char [] inputAsCharArray = input.toCharArray();
        boolean isValid = true;
        for (char currentChar : inputAsCharArray) {
            if (currentChar == '(' || currentChar == '[' || currentChar == '{') {
                characterUnlimitedStack.push(currentChar);
            }

            if (currentChar == ')' || currentChar == ']' || currentChar == '}') {
                if (characterUnlimitedStack.isEmpty()) {
                    isValid = false;
                } else {
                    Character stackTop = characterUnlimitedStack.pop();
                    if (getMatchingOpener(currentChar) != stackTop) {
                        isValid = false;
                    }
                }
            }
        }
        if (!characterUnlimitedStack.isEmpty()) {
            isValid = false;
        }
        return isValid;
    }

    private char getMatchingOpener(final char closer) {
        if (closer == ')') {
            return '(';
        } else if (closer == ']') {
            return '[';
        } else if (closer == '}') {
            return '{';
        }
        return ' ';
    }

    public static void main(String[] args) {
        final String firstExample = "[(A + B])";
        final String secondExample = "(A + B) - {C + D} - [F + G]";
        final String thirdExample = "((H) * {([J + K])})";
        final String [] examples = {firstExample, secondExample, thirdExample};
        final ParenthesesCheckerLinkedListStack parenthesesSyntaxChecker = new ParenthesesCheckerLinkedListStack();
        for (String example: examples) {
            try {
                System.out.println(String.format("The syntax for example \"%s\" is valid? : %s", example, parenthesesSyntaxChecker.checkParenthesisSyntax(example)));
            } catch (Exception e) {
                e.printStackTrace();
            }
        }
    }
}

You can find the full code at https://github.com/priyeshkpandey/clean-data-structures