In this section we develop list implementations using references (links). We follow the same basic pattern of development here that we did when we developed list implementations using arrays.
Our reference-based implementations fulfill the interfaces that we used with arrays.
We first combine all the methods whose reference-based implementations are common across our different list types into a single class, the RefList class, and then we extend that class with classes that complete the implementations.
As we did for our reference-based stacks and queues, we use the LLObjectNode class from the support package to provide our nodes.
We maintain a variable, list, that references the first node on the list.
We'll implement both unsorted and sorted lists using the linked approach.
We do not implement indexed lists. There is no simple way to efficiently implement the add, set, get, and remove operations involving index arguments.
Includes all the list methods that do not depend on whether the list is sorted. The implementations of size, contains, get, toString, reset, and getNext are straightforward.
The RefList class (RefList.java code)
The Unsorted Ref List class (RefUnsortedList.java)
The Sorted Ref List class (RefSortedList.java)
The find method sets an extra variable "previous" for use by the remove method.
The remove method: To remove an element, we first find it using the find method, which sets the location variable to indicate the target element and sets the previous variable to a reference in the previous node.
We can now change the link of the previous node to reference the node following the one being removed.
Removing the first node must be treated as a special case because the main reference to the list (list) must be changed.
Implements the SortedListInterface and extends the RefList with an add method
Adding an element to a reference-based sorted list requires three steps:
1. Finding the location where the new element belongs
To link the new node into the identified location, we also need a reference to the previous node.
While traversing the list during the search stage, each time we update the location variable, we first save its value in a prevLoc variable:
prevLoc = location;
location = location.getLink();
2. Create a node for the new element
instantiate a new LLObjectNode object called newNode, passing its constructor the new element for use as the information attribute of the node
LLObjectNode newNode = new LLObjectNode(element);
3. Correctly link the new node into the identified location
We change the link in the newNode to reference the node indicated by location and change the link in our prevLoc node to reference the newNode:
newNode.setLink(location);
prevLoc.setLink(newNode);
