Linked Lists/Java

List Interfaces in Java API

List ADT

The List interface - adding implements List<E> to a class - has quite a few methods that need to be defined. This makes a data collection capable of being treated as a Collections object.

The full list is here: List interface class abstract methods: https://docs.oracle.com/javase/8/docs/api/java/util/List.html

Link to implementations of various Linked Lists on on git.charlesreid1.com: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists

LinkedList ADT

The linked list abstract data type provides the following methods:

• size
• isEmpty
• first
• last
• addFirst
• addLast
• removeFirst

Furthermore, convenience methods can be added, like:

• add
• remove
• remove(i)
• removeFirst
• removeLast

See Java API for LinkedList class: https://docs.oracle.com/javase/8/docs/api/java/util/LinkedList.html

Code Implementation

Singly Linked List

A basic singly linked list that forces the data type to be an integer is defined in IntList.java: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/IntList.java

It takes quite a bit of work to get everything functioning correctly - particularly with remove operations. None of the difficulty is in the concept. It is all in the details.

Practice, review the details, document learning process/patterns/mistakes here: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists

Generic Type Linked List

The next phase of implementing a linked list is to make it type-generic, so that it can utilize the diamond notation of the Java Collections library and the type protection it requires.

Typed linked list TLinkedList<E> class: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/TLinkedList.java

Circular Linked List

A linked list organized in a circular fashion, that can be expanded but that is efficient in its re-use of space.

Circular linked list CLinkedList<E> class: https://git.charlesreid1.com/cs/java/src/master/lists/linked-lists/CLinkedList.java

Doubly Linked List

Implementation of a linked list that stores a reference to a header and trailer node, "bumper nodes" that make the implementation of various algorithms easier.

Questions

Goodrich et al Data Structures in Java Chapter 3 questions

Note that Goodrich spends the first few chapters of the Java book focusing on linked lists and link-based data structures, while in the Python book the emphasis is on array lists and array-based data structures.

Questions about Java arrays and lists:

Tail Pointer

Question R-3.5) SinglyLinkedList sets the tail field to null when deleting last node of a list. What if those lines were removed? Would class still work, and why or why not?

Class would no longer work properly - if tail pointer is not null, will not be able to use fact that tail pointer points at null for end of list. Tail pointer is never reset to null, so dangling node will always be a dangling node until tail is explicitly reset to something else. (Some functionality may not be affected - but it depends entirely on the order of operations.)

Second to last

Question R-3.6) Find second to last node in singly linked list, where last node is indicated by having a null reference.

To find second to last node, you're checking two nodes ahead:

if(size==0 || size==1) { 
    // no second to last node
}

Node runner = this.head;
while(runner.getNext().getNext() != null) { 
    runner = runner.getNext();
}
// Now runner points to the node that points to the null node
// (i.e., runner points to the second-to-last node.)

Midpoint

Finding the midpoint of a singly linked list:

• Naive solution: traverse the list once, counting along the way, then traverse the list a second time
• But, why not count twice if we can
• Two steps with the runner, one step with the head. etc..

Finding the midpoint of a doubly linked list:

• In the case of an odd number of nodes, iterating head forward and tail backward will eventually have head and tail equal - pointing to same node
• In the case of an even number of nodes, the head and tail are passing ships in the night - so we need to check if head.next == tail

Implementing the Size Method

Question R-3.9) Give an implementation of the size() method for the SingularlyLinkedList class, assuming that we did not maintain size as an instance variable.

if(isEmpty()) {
    throws new Empty();
}
int count = 1;
Node runner = head;
while(runner.getNext()!=null) { 
    count++;
    runner = runner.getNext();
}

Question R-3.10) Give an implementation of the size() method for the DoublyLinkedList class, assuming that we did not maintain size as an instance variable.

if(isEmpty()) {
    throws new Empty();
}
int count = 1;
Node hrunner = head;
Node trunner = tail;
while(hrunner!=trunner && hrunner.getNext()!=trunner) {
    count++; count++;
    hrunner = hrunner.getNext();
    trunner = trunner.getNext();
}
if(hrunner!=trunner) {
    // the pointers don't match - even number of elements
    count--;
}

// This handles the empty DLL, the one-element DLL, the two-element DLL, the three-element DLL

Question R-3.11) Give an implementation of the size() method for the CircularlyLinkedList class, assuming that we did not maintain size as an instance variable.

Rotate

Question R-3.12) Implement a rotate() method in the SinglyLinkedList class, which has semantics equal to addLast(removeFirst()) but which does not create any new node.