CS211: 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
• is_empty
  • 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 a struct in C. It should contain an integer data field and a next pointer. Then implement init which initializes an empty linked list with a head pointer set to NULL.
2. Implement append from Listing 3 in C. The lecture 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 lecture notes that Listing 4 is missing two distinct case checks. Identify both before implementing insert in C. 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 C. The lecture 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 pointer 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 lecture lists "appending can be made a constant time operation" as a pro of linked lists. Currently, append from Listing 3 traverses the entire list to find the last node, making it O(n). Add a tail pointer to your linked list struct 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 lecture shows in Listing 2 that linked list nodes can be stored at non-contiguous memory addresses. Write a program that allocates five nodes using malloc and prints the memory address of each. Are they contiguous? What does this confirm about how linked lists use memory compared to arrays?
8. Implement free for your linked list. It should traverse the entire list and free each node individually. Run your full linked list implementation under valgrind to confirm there are no memory leaks.
9. Implement a doubly linked list in C using the singly linked list as a guide. Each node should have both a next and a prev pointer. Update append, insert, and delete to maintain both pointers correctly. What additional steps are required compared to the singly linked list versions?
10. The lecture 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 using get at any index?