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://charlesreid1.com:3000/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://charlesreid1.com:3000/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://charlesreid1.com:3000/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://charlesreid1.com:3000/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://charlesreid1.com:3000/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.