# Linked Lists/Java

### From charlesreid1

## 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.

# Flags

Data StructuresThis is the staging ground for computer science notes as part of the 2017 CS Study Plan.
Classes of data structures: Abstract Data Types Array-based and Link-based memory management: ArrayLists and Linked Lists Algorithmic Analysis of Data Structures: Algorithmic Analysis of Data Structures Advanced data structures: Advanced Data Structures
· Template:DataStructuresFlag · e |

ArraysSeries on Data Structures Python: Arrays/Python Java: Arrays/Java Categories: Category:Python Arrays
· Template:ArraysFlagBase · e |

Stacks and QueuesSeries on Data Structures
StacksQueues/Python StacksQueues/Python/LinkedStack
StacksQueues/Java StacksQueues/Java/LinkedStack
Postfix_Expressions#Stacks
· Template:StacksQueuesFlagBase · e |

Priority Queues and HeapsSeries on Data Structures
Priority Queues/Heap
· Template:PriorityQueuesFlagBase · e |

Linked ListSeries on Data Structures
· Template:LinkedListFlagBase · e |

TreesSeries on Data Structures Abstract data type: Trees/ADT Concrete implementations: Trees/LinkedTree
Preorder traversal: Trees/Preorder Postorder traversal: Trees/Postorder In-Order traversal: Binary Trees/Inorder Breadth-First Search: BFS Breadth-First Traversal: BFT Depth-First Search: DFS Depth-First Traversal: DFT OOP Principles for Traversal: Tree Traversal/OOP Tree operations: Trees/Operations Performance
Finding Minimum in Log N Time: Tree/LogN Min Search
Abstract data type: Binary Trees/ADT Concrete implementations: Binary Trees/LinkedBinTree Binary Trees/Cheat Sheet
· Template:TreesFlagBase · e |

Search TreesSeries on Data Structures
Binary Search Trees Trees/OOP
(Note that heaps are also value-sorting trees with minimums at the top. See Template:PriorityQueuesFlag and Priority Queues.)
· Template:SearchTreesFlagBase · e |

Maps and DictionariesSeries on Data Structures
Maps Map implementations: Maps/AbstractMap Dictionary implementations: Dictionaries/LinkedDict
Hash Maps/OOP Hash Maps/Dynamic Resizing Hash functions: Hash Functions Hash map implementations: Hash Maps/AbstractHashMap
Skip Lists Java implementations: SkipList
Sets
· Template:MapsFlagBase · e |