Linked Lists

Every data structure we've encountered so far has shared one serious limitation: they have all needed to be defined with contiguous stretches of memory. This can be a major issue when dealing with variable sized data—remember back to one of the major cons of vectors. That then raises the question: "Can we create a data structure which can grow arbitrarily large, but does not require large swathes of connected strips of memory?" The answer: linked lists.

Linked lists were first formalized in a work published by Allen Newell, Cliff Shaw, and Herbert A. Simon in 1957 titled Programming the Logic Theory Machine. Newell, Shaw, and Simon had previously worked on establishing a heuristic search-based algorithm which would mimic human-like proof discovery with symbolic symbol sets. The biggest barrier they encountered when trying to practically implement the Logic Theory Machine was that, by definition, the search would take an amount of time and space not known a priori—human beings never know how long it might take to discover proofs, so the algorithmic representation was equally haunted by that reality. This meant that storing all of the different possible branches and twists the search algorithm went on was beyond the capabilities of known data structures and programming language constructs. Their solution was to craft a new programming language, IPL, which was focused around the maintenance of a revolutionary data structure they called a "list".

The IPL list had to satisfy the following constraints:

1. "There should be no restriction on the number of different lists of items of information to be stored. This number should not have to be decided in advance; that is, it should be possible to create new lists at will during the course of computation."
2. "There should be no restriction on the nature of the items in a list. These might range from a single symbol or number to an arbitrary list. Thus, it should be possible to make lists, lists of lists, lists of lists of lists, etc."
3. "It should be possible to add, delete, insert, and rearrange items of information in a list at any time and in any way. Thus, for example, one should be able to add to the front of a list as well as to the end."
4. "It should be possible for the same item to appear on any number of lists simultaneously."

And thus, what we call a "linked list" was born!

I've found that, for many students, linked lists mark a major point where data structures enter a level of what can feel like incomprehensible abstraction. The most important thing to keep in mind when dealing with linked lists is that they are really only constituted of two components: data and a pointer to the next element in the list. The "elements" that make up linked lists are called nodes. A node looks like the following:

+--------+--------+
|  data  |  next  |
+--------+--------+

The node stores two values: the key data associated with that node and the pointer that will be used to connect it to the next node in the chain.

Now that we know what a node looks like, we can visualize what a full linked list looks like:

+------+------+    +------+------+    +------+------+    +------+------+    +------+------+
|  17  |   *--+--->|   4  |   *--+--->|  91  |   *--+--->|  62  |   *--+--->|   1  | NULL |
+------+------+    +------+------+    +------+------+    +------+------+    +------+------+
 head

Here we see a linked list which is storing integer values. This list is comprised of five nodes all of which have up to a single connection to another node. We call this sort of linked list a singly-linked list for that very reason. The advantage of the linked list is that, since it is entirely pointer, or reference, based none of the nodes must be connected contiguously in memory. For example, Listing 1 could be represented in memory like this:

Address                                                    
0x008  +------+------+                                    
       |  17  |   *--+---+                                
       +------+------+   |                                
                         |                                
0x031  +------+------+<--+                               
       |   4  |   *--+---+                                
       +------+------+   |                                
                         |                                
0x057  +------+------+<--+                               
       |  91  |   *--+---+                                
       +------+------+   |                                
                         |                                
0x102  +------+------+<--+                               
       |  62  |   *--+---+                                
       +------+------+   |                                
                         |                                
0x210  +------+------+<--+                               
       |   1  | NULL |                                    
       +------+------+                                    

head → 0x008

Again, in a linked list nodes can be connected between disparate locations in the address space.

One thing that you will have noticed is the use of the phrase head. The head pointer refers to the start of the linked list. Without a head pointer there would be no way to "enter" into the linked list.

We can define a simple linked list API as follows:

• init
  • Initializes a linked list
• append
  • Adds an element to the end of the linked list
• insert
  • Inserts an element at the desired index of the linked list
• search
  • Retrieves the desired element from the linked list
• get
  • Retrieves the element at the desired index of the linked list
• remove
  • Removes the element at the desired index of the linked list
• isEmpty
  • Indicates whether the linked list is empty or not
• free
  • Frees the linked list

Linked list implementations often allow for two ways of adding elements: appending and inserting.

Searching a linked list follows the exact same algorithm as appending/inserting with the exception of checking equivalency at each data item.

Removing elements from a linked list follow a similar algorithm to insertion. The only difference being is you want to break the next node chain and free up the node that is marked for deletion.

 1: delete(index):
 2:   current_node ← head
 3:   prev_node ← null
 4:   c_i ← 0
 5:   while c_i not = index:
 6:     prev_node ← current_node
 7:     current_node ← current_node.next
 8:     c_i ← c_i + 1
 9:   prev_node.next = current_node.next
10:   free(current_node)

Again, the delete function is missing two distinct case checks. Can you figure out what they are?

The references to linked lists above were all to singly-linked lists as each node had only one next pointer. We can increase the complexity of our linked lists by adding a second pointer to each node which points to the previous node in the chain. The diagram below shows a doubly-linked list variant of the singly-linked list diagram used above:

+-------+------+------+    +------+------+-------+    +------+------+-------+    +------+------+-------+    +------+------+-------+
|  NULL |  17  |   *--+<-->+--*   |   4  |    *--+<-->+--*   |  91  |    *--+<-->+--*   |  62  |    *--+<-->+--*   |   1  |  NULL |
-+------+------+------+    +------++------+------+    +------++------+------+    +------++------+------+    +------++------+------+
          head              (prev)         (next)

The introduction of a second pointer requires slightly more upkeep and overhead from the algorithm perspective. Again, I leave it as an exercise to the reader to implement a doubly-linked list using the singly-linked list as a guide.

Pros:

• Can grow arbitrarily large
• Appending can be made a constant time operation

Cons:

• Can be costly to search through

1. Implement a singly linked list node as an inner class in Java. It should contain an integer data field and a next reference. Then implement a LinkedList class with a head field initialized to null and a constructor that sets up an empty list.
2. Implement append from Listing 3 in Java. The chapter notes that the pseudocode is missing an edge case check — identify what it is and handle it in your implementation. Test by appending the values (17, 4, 91, 62, 1) and printing each node.
3. The chapter notes that Listing 4 is missing two distinct case checks. Identify both before implementing insert in Java. Hint: think about what happens when inserting at index 0 and when inserting beyond the end of the list.
4. Implement delete from Listing 5 in Java. The chapter notes it is also missing two case checks — identify and handle them. Test by deleting the head, the tail, and a middle element from your list.
5. Implement search for your linked list. It should traverse the list and return a reference to the first node whose data matches the search value, or null if not found. What is the worst case number of nodes that must be visited to find an element?
6. The chapter lists "appending can be made a constant time operation" as a pro of linked lists. Currently append traverses the entire list to find the last node. Add a tail reference to your LinkedList class that always points to the last node and update append, insert, and delete to maintain it correctly. Verify that append no longer needs to traverse the list.
7. The chapter shows in Listing 2 that linked list nodes can be stored at non-contiguous memory addresses. Write a program that allocates five nodes and prints the identity hash code of each using System.identityHashCode(node). Are they contiguous? What does this confirm about how linked lists use memory compared to arrays?
8. Java's garbage collector reclaims unreachable objects automatically. When you delete a node from your linked list by removing all references to it, does it need to be explicitly freed? Verify by deleting all nodes from your list one at a time and confirming that your LinkedList class correctly sets head to null when empty. What would happen in C if you forgot to free a deleted node?
9. Implement a doubly linked list in Java using the singly linked list as a guide. Each node should have both a next and a prev reference. Update append, insert, and delete to maintain both references correctly. What additional steps are required compared to the singly linked list versions?
10. The chapter lists "can be costly to search through" as a con of linked lists. Write a program that creates a linked list of 1000 integers and searches for a value stored at the very end. Count the number of nodes visited during the search and print it. Then repeat the same experiment with a value stored at the front. What does the difference tell you about the relationship between where an element is stored and how long it takes to find it? How does this compare to retrieving an element from a Vector<Integer> using get at any index?