Positional List is an Abstract Data Type that can used in a wide variety of use cases. In this post, we will see Positional List Implementation using Java as the programming language.
Think of the Positional List as a combo between Stacks and Queues. A queue is just a list. However, you can add items only at the end. On the other hand, a stack allows you to add elements at the top and pop them off the top. A Positional List allows you to do both.
A Positional List allows you to perform arbitrary insertion and deletion. You can think of it like a queue at the ticket window. A person in this line or queue can leave the line before reaching the front. Also, a person in the line can allow a friend to enter the line in front or behind him or her. Such cases are better handled using a Positional List rather than a simple array.
Defining the Interfaces
Let’s start our Positional List Implementation using Java in a step-by-step manner. We will first define the interfaces.
Defining the Position Interface
Positional List works on the notion of Position. Therefore, we define a Position interface. This is similar to the Position interface we used in our Tree Implementation using Java.
public interface Position<E> { /** * Returns the element stored at the position * @return the stored element * @throws IllegalStateException if it is invalid position */ E getElement() throws IllegalStateException; }
A position acts as a marker or token within the Positional List Implementation.
Defining the Positional List ADT
Next step is to define the Positional List interface.
public interface PositionalList<E> { /** * Returns the number of elements in the list * @return */ int size(); /** * Tests whether the list is empty or not * @return */ boolean isEmpty(); /** * Returns the first position in the list * @return */ Position<E> first(); /** * Returns the last position in the list * @return */ Position<E> last(); /** * Returns the position before Position p in the list * @param p * @return * @throws IllegalArgumentException */ Position<E> before(Position<E> p) throws IllegalArgumentException; /** * Returns the position after Position p in the list * @param p * @return * @throws IllegalArgumentException */ Position<E> after(Position<E> p) throws IllegalArgumentException; /** * Inserts an element e at the front of the list and returns its position * @param e * @return */ Position<E> addFirst(E e); /** * Inserts an element e at the end of the list and returns its position * @param e * @return */ Position<E> addLast(E e); /** * Inserts an element e just before position p and returns its position * @param p * @param e * @return * @throws IllegalArgumentException */ Position<E> addBefore(Position<E> p, E e) throws IllegalArgumentException; /** * Inserts an element e just after position p and returns its position * @param p * @param e * @return * @throws IllegalArgumentException */ Position<E> addAfter(Position<E>p , E e) throws IllegalArgumentException; /** * Replaces the element at Position p and returns the replaced element * @param p * @param e * @return * @throws IllegalArgumentException */ E set(Position<E> p, E e) throws IllegalArgumentException; /** * Removes the element at position p and returns the removed element * @param p * @return * @throws IllegalArgumentException */ E remove(Position<E> p) throws IllegalArgumentException; }
Some of the important methods in this interface are as follows:
- The size() method returns the number of elements in the list.
- The isEmpty() method tests whether the list is empty or not.
- first() method returns the first Position in the Positional List.
- last() method returns the last Position in the list.
- before(p) returns the Position just before the position p. Similarly, after(p) returns the Position just after the position p.
- addFirst(e) and addLast(e) inserts an element e at the front or the end of the list respectively.
- addBefore(p, e) and addAfter(p, e) inserts an element e before or after the position p respectively.
- set(p, e) replaces the element e stored at position p.
- Lastly, remove(p) removes a position p from the list.
Positional List Implementation
Now that the interfaces have been defined, we can implement the interfaces. For the purposes of implementation, we will use a Doubly Linked List approach.
A Linked List is another Abstract Data Type that fits our requirement for Positional List quite well.
Implementing the Position Interface
As a first step, we implement the Position interface. We declare a Node class that implements Position. We keep this Node class as nested class in our Positional List implementation to follow the principles of proper abstraction.
Below is the implementation.
private static class Node<E> implements Position<E>{ private E element; private Node<E> prev; private Node<E> next; public Node(E e, Node<E> p, Node<E> n){ this.element = e; this.prev = p; this.next = n; } @Override public E getElement() throws IllegalStateException { if (next == null) throw new IllegalArgumentException("Position no longer valid"); return element; } public void setElement(E element) { this.element = element; } public Node<E> getPrev() { return prev; } public void setPrev(Node<E> prev) { this.prev = prev; } public Node<E> getNext() { return next; } public void setNext(Node<E> next) { this.next = next; } }
As you can see, the implementation is quite self-explanatory.
Implementing the Positional List Interface
Now, we can implement the Positional List Interface itself. We call our implementation Linked Positional List since we are using Linked List approach.
Below is the implementation including the nested Node class.
public class LinkedPositionalList<E> implements PositionalList<E> { private static class Node<E> implements Position<E>{ private E element; private Node<E> prev; private Node<E> next; public Node(E e, Node<E> p, Node<E> n){ this.element = e; this.prev = p; this.next = n; } @Override public E getElement() throws IllegalStateException { if (next == null) throw new IllegalArgumentException("Position no longer valid"); return element; } public void setElement(E element) { this.element = element; } public Node<E> getPrev() { return prev; } public void setPrev(Node<E> prev) { this.prev = prev; } public Node<E> getNext() { return next; } public void setNext(Node<E> next) { this.next = next; } } private Node<E> header; private Node<E> trailer; private int size = 0; public LinkedPositionalList(){ header = new Node(null, null, null); trailer = new Node(null, header, null); header.setNext(trailer); } private Node<E> validate(Position<E> p) throws IllegalArgumentException{ if(!(p instanceof Node)) throw new IllegalArgumentException("Invalid p"); Node<E> node = (Node<E>) p; if(node.getNext() == null) throw new IllegalArgumentException("p is no longer in the list"); return node; } private Position<E> position(Node<E> node){ if (node == header || node == trailer) return null; return node; } @Override public int size() { return size; } @Override public boolean isEmpty() { return size == 0; } @Override public Position<E> first() { return position(header.getNext()); } @Override public Position<E> last() { return position(trailer.getPrev()); } @Override public Position<E> before(Position<E> p) throws IllegalArgumentException { Node<E> node = validate(p); return position(node.getPrev()); } @Override public Position<E> after(Position<E> p) throws IllegalArgumentException { Node<E> node = validate(p); return position(node.getNext()); } private Position<E> addBetween(E e, Node<E> pred, Node<E> succ){ Node<E> newest = new Node<>(e, pred, succ); pred.setNext(newest); succ.setPrev(newest); size++; return position(newest); } @Override public Position<E> addFirst(E e) { return addBetween(e, header, header.getNext()); } @Override public Position<E> addLast(E e) { return addBetween(e, trailer.getPrev(), trailer); } @Override public Position<E> addBefore(Position<E> p, E e) throws IllegalArgumentException { Node<E> node = validate(p); return addBetween(e, node.getPrev(), node); } @Override public Position<E> addAfter(Position<E> p, E e) throws IllegalArgumentException { Node<E> node = validate(p); return addBetween(e, node, node.getNext()); } @Override public E set(Position<E> p, E e) throws IllegalArgumentException { Node<E> node = validate(p); E answer = p.getElement(); node.setElement(e); return answer; } @Override public E remove(Position<E> p) throws IllegalArgumentException { Node<E> node = validate(p); Node<E> predecessor = node.getPrev(); Node<E> successor = node.getNext(); predecessor.setNext(successor); successor.setPrev(predecessor); size--; E answer = node.getElement(); node.setElement(null); node.setPrev(null); node.setNext(null); return answer; } }
On a high-level, in our Positional List Implementation using Java, we declare two nodes as Header and Trailer. These header and trailer nodes act as sentinel nodes. All new nodes or positions are inserted between these two sentinel nodes.
Also, we declare a variable size to keep track of the number of elements in the list.
To make things easier for us, we also declare few utility methods to check if a Position actually belongs to the Node class. We also reuse the logic for inserting a node by declaring an addBetween() method.
The beauty of our Positional List Implementation using Linked List is that all operations run in worst-case constant time. Below is the list of these operations and their performance:
| Method Name | Running Time |
| size() | O(1) |
| isEmpty() | O(1) |
| first(), last() | O(1) |
| before(p), after(p) | O(1) |
| addFirst(e), addLast(e) | O(1) |
| addBefore(p, e), addAfter(p, e) | O(1) |
| set(p, e) | O(1) |
| remove(p) | O(1) |
Conclusion
We have finished our Positional List Implementation using Java. To do so, we took a step-by-step approach by defining the interfaces followed by the concrete implementations for the same.
We also used Doubly Linked List as the base for our concrete implementation. This allows our positional list implementation to work in O(1) constant running time.
The code for this available on Github.
Please sound off your comments or queries in the comments section below.
0 Comments