Linked Lists

What Are Linked Lists

Linked lists are a data structure whereby each element of a list is stored in a structure of linked wrapper objects that simply hold a data value and point to neighbor items. The list is an object that contains only one reference to the beginning of the list. Remaining elements must be obtained from the items in the list themselves.

The linked list structure can be implemented as a singly-linked list or a doubly-linked list. A singly linked list means each list node points only to the next node (or a null pointer if the end of the list). A doubly linked list means each list node points at the prior node as well as the next node.

The purpose of using linked lists is that certain operations become much faster (for example, adding elements to the front or back of a list) when using a linked object data structure than they would be using an array-based data structure, which would need to constantly shift or resize elements.

Why Linked Lists

Linked lists are a basic data structure, and the idea is a simple one, on the surface. These are excellent for testing understanding, however, because a Linked List takes practice and experience to implement correctly. This can separate the student who says "Let me try this concept out first..." and knows how to practice, from a student who says "Yes yes, I understand, it's very easy, now on to the next topic" and has not actually sat down to implement any of the basics, let alone the more advanced stuff.

Another nice feature of LinkedLists is that they are great for simple, applied recursion problems. "Do X. Okay, now do X recursively."

The Gist of Linked Lists

Questions about Linked Lists require handling a number of different assumptions, questions, and possible interfaces. Which one you implement depends on the problem and specifications. However, "Linked List" should immediately call to mind the methods in a List ADT (abstract data type) and by extension the methods in a LinkedList ADT.

They are mainly the same, but their level of detail depends on the features of the list.

List ADT

LinkedList ADT

Link to implementation on git.charlesreid1.com: https://charlesreid1.com:3000/cs/java/src/master/lists/linked-lists

The linked list abstract data type provides the following methods:

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

Other convenience methods:

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

Node type:

• Node class should be defined INSIDE list class
• private static class Node
• Node class fields: E data, Node next
• constructor with data, constructor with data plus next
• getData
• getNext
• setNext
• equals
• toString

Iterable

Java API LinkedList

Link: https://docs.oracle.com/javase/7/docs/api/java/util/LinkedList.html

Add methods:

• add(e) : add element
• add(i,e) : add index i element e
• addAll(c) : add all elements from collection c
• addFirst(e)
• addLast(e)

Utility operations:

• clear()
• clone()
• contains(o)

Iterators:

• descendingIterator()
• listiterator(i)

Find:

• indexOf(o) : returns -1 if not found

Get/Set:

• get(i)
• getFirst()
• getLast()
• element() : peek operation. "Retrieves, but does not remove, the head (first element) of this list."

Remove:

• remove() : removes head
• remove(i) : remove element at index i
• removeFirst()
• removeLast()

• remove(o) : remove obj, if present
• removeFirstOccurrence(o)
• removeLastOcurrence(o)