Linked Lists

Notes

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. (See Abstract Data Types.) Linked lists are designed according to the same basic principles, but their implementation can vary.

The basic gist is this: a simple, link-based memory structure that is dynamic in size. This organization of data makes management and allocation of new memory for new data less troublesome than automatically resizing arrays. However, it makes random access impossible, sacrificing functionality for speed.

The main purpose of using linked lists is the O(1) access to add nodes to the front or back of the list.

List ADT

LinkedList ADT

Link to implementation on git.charlesreid1.com: https://git.charlesreid1.com/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)

Implementations

See Linked Lists/Java and Linked Lists/Python

Questions

See questions from Goodrich et al Data Structures in Java book at Linked Lists/Java#Questions

Skiena Algorithm Handbook Chapter 3 questions

Question 3-2) Write a program to reverse the direction of a singly linked list in O(n) time.

See Linked Lists/Java/Reverse