Positional List

---

Note: A positional list not a standard name.

Singly Linked List

Traversable in one single direction. Each node contains a pointer to the next node.

Double Linked List

DLLs can be traversed in both direction.

• Advantage: insert/remove before a given node
• Disadvantage: requires more memory to store the extra pointers and you must update the extra pointer as we perform various operations.

Minimal scaffolding of a DLL data structure:

public class DoublyLinkedList<T> {
	private Node<T> head;
	// optional tail pointer
	
	private static class Node<E> {
		E data;
		Node<E> prev;
		Node<E> prev;
	}
}

To add a new node to the front:

public void addFrist(T data) {
	Node<T> node = new Node<>(data);
	node.next = head;
	node.prev = node; 
	head = node;
}

To append a new node to the end:

public void addLast(T data) { 
	Node<T> node = new Node<>(data);
	node.prev = tail;
	tail.next = node; 
	tail = node; 
}

To get the data stored in the kth node (at index k-1), you must start from the head or tail and follow the pointers to get there (following implementation fails to account for an edge case):

public T get(int index) { 
	Node<T> target = tail;
	for (int i = numElements - 1; i > index; i--)
	{ 
		target = target.prev; 
	} 
	return target.data; 
}

To delete the node pointed to by the reference variable target (following implementation fails to account for an edge case):

public void delete(Node<T> target) {
	Node<T> prevNode = target.prev;
	Node<T> nextNode = target.next;
	
	prevNode.next = nextNode;
	nextNode.prev = prevNode;
}

Insert a node after the one pointed to by the reference variable target (following implementation fails to account for an edge case):

public void insertAfter(Node<T> target, T data) {
	Node<T> nodeToInsert = new Node<>(data);
	Node<T> nextNode = target, next;
	target.next = nodeToInsert; 
	nodeToInsert.prev = target;
	
	nodeToInsert.next = nextNode;
	nextNode.prev = nodeToInsert;
}

To insert a node before the one pointed to by the reference variable target (following implementation fails to account for an edge case):

public void insertBefore(Node<T> target, T data) {
	Node<T> nodeToInsert = newNode<>(data);
	Node<T> prevNode = target.prev;
	
	target.prev = nodeToInsert;
	nodeToInsert.next = target;
	
	nodeToInsert.prev = prevNode;
	prevNode.next = nodeToInsert; 
}

Position Interface

Since we are using Node as a type in the signature of these public operations, like delete, we must make Node available by making it public. However, this can be risky because a client can change the value and pointers stored in the node.

Solution: since the Node class represents a position in a linked list, we can further abstract the idea of a position. We can create an interface for position that node will implement.

public interface Position<T> {
	/**
	 * read element from thsi position
	 *
	 * @return element at this position
	 **/
	T get();
}

• This way, the client recieves the type of Position and will only have one operation at their disposal: get.

Example implementation:

public Position<T> addFirst(T data) {
	Node<T> node = new Node<>(data);
	node.next = head;
	head.prev = node;
	head= node;
	return node; 
}

// downcast the target to access reference variables
public void delete(Position<T> target) {
	Node<T> targetNode = (Node<T>)target;
	// ...
}

insertFront will

public Position<T> insertFront(T data) {
	if (head == null) {
		head = new Node<T>(data, this);
		tail = head; 
		numElements += 1;
		return head;
	}	
	
	Node<T> newFront = new Node<T>(data, this);
	
	newFront.next = currFront;
	currFront.prev = newFront;
	head = newFront;
	
	numElement += 1;
	return newFront; 
}

List

The generic positional list builds on top of the doubly linked list.

• You can insert/remove from either end
• You can insert/remove in between a given "position".
• There are a "getter" methods to access the front, back, or next or previous positions given a "position".

Position Exception

Structures that work with Position throw PositionException when

• a given position is null
• a given position refers to a different, unrelated instance (e.g., position in a different list)
• a given position refers to a different data structure.

// throw when the position provided is null or invalid
public class PositionException extends RuntimeException {
	// constructs a new PositionException
	public PositionException() { }

	// constructs with specific message
	public PositionException(String message) {
	super(message);
	}
}

Node is-a Position

private static class Node<E> implements Position<E> {
	Node<E> next;
	Node<E> prev;
	E data;
	List<E> owner;
	
	Node(E data, List<E> owner) {
		this.data = data;
		this.owner = owner;
	}
	
	@Override
	public E get() {
		return data;
	}
}

• We track the owner of the data structure so that we can later check if a given position belongs to the current data structure.

A convert method may be necessary for turning a Position into a Node. It guards against null positions, positions from other data structures, and positions that belong to other LinkedList objects.

Sentinel Nodes

Sentinel nodes are dummy nodes that you add to both ends of your linked list. The head and tail pointer always points to sentinel nodes, that are constructed by the constructor. These nodes do not count as elements of the data structure. Do not iterate through these either. Overall, it allows for a more elegant implementation because it removes some edge cases.

public LinkedList() {
	head = new Node<>(null, this);
	head = new Node<>(null, this);
	head.next = tail;
	tail.prev = head;
	numElements = 0;
}

When implementing insertFront you no longer need to treat the case when head = null.