Where is the need for the positional list ADT?

If your program often needs to add new elements to or delete elements from your data collection a list is likely to be a better choice than an array.

Deleting the element at position N of an array require a copy operation on all elements after element N. In principle:

Arr[N] = Arr[N+1]
Arr[N+1] = Arr[N+2]
...

A similar copy is needed when inserting an new element, i.e. to make room for the new element.

If your program frequently adds/deletes element, the many copy operations may hurt performance.

As a part of these operations the position of existing elements changes, i.e. an element at position 1000 will be at either position 999 or 1001 after an element is deleted/added at position 50.

This can be a problem if some part of your program has searched for a specific element and saved its position (e.g. position 1000). After an element delete/add operation, the saved position is no longer valid.

A (doubly-linked) list "solves" the 3 problems described. With a list you can add/delete elements without copying existing elements to new positions. Consequently, the position of a specific element (e.g. a pointer to an element) will still be valid after an add/delete operation.

To summarize: If your program (frequently) adds or deletes random located elements and if your program requires that position information isn't affected by add/delete operations, a list may be a better choice than an array.

Positional Lists

• So when working with arrays indexes are great in locating positions for insertion and deletion. However, indexes are not great for linked structures (like a linked list), mainly because even if we have the index. We still have to traverse all previous nodes in the liked structure. That means an index based deletion or insertion in a linked list would run O(N) time(no bueno). It is a general rule of thumb that for data structure operations we want them to run either O(1) or O(log n). Also, indexes are not good at describing there positions relative to other nodes.

What do Positions allow us to do?

• Positions allow us to achieve constant time insertions and deletions at arbitrary locations within our liked structure (kind cool, right??).
• They also allow us to describe the element relative to other elements.
• Essentially, a Position gives us a reference to a memory address which we can then use for constant time insertions and deletions. Your textbook image doesn't show a validate method, However, I would assume that the implementation does. So just be aware that you will need a utility method validate to verify that the position is in the linked structure.

What does a Position look like?

• in reality a Position is a ADT (abstract data type) and in Java we formalize ADTs with interfaces, like so:

public interface Position <E>{

    E getElement()throws IllegalStateException;
}

• A Position is just an abstraction that gets implemented on a Node within a linked structure. Why do this? Well, it gives our code greater flexibility and better abstraction.
• So to implement a Position for a linked list node, it would look something like this:

private static class Node<E> implements Position<E> {
// ALL THE OTHER METHODS WOULD BE HERE
}

• The Node class is private and static because it is assumed to be nested inside the linked list class. Then ultimately we use this Position as a data type when dealing with all the other methods inside your Positional Linked list.

Real world example

• Well you could use this method to create a parse tree for a parser. You could have a binary tree that implements and uses the Position interface for all of its methods and then use the tree for parsing