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://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)

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

Question R-3.6) Give algorithm for finding second to last node in singly linked list in which last node indicated by null reference.

Question R-3.8) Describe a method for finding the middle node of a doubly linked list with header and trailer sentinels by "link hopping," and without relying on explicit knowledge of the size of the list. In the case of an even numer ofnodes, report hte node slightly left of center as middle. WHat is the runtime of this 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.

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.

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.

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.

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