7.4 Prepending Nodes to a Linked List

linked list prepending

worst-case: $\text{O}\left(1\right)$

When working with an unordered list, new values can be inserted at any point within the list. Since we only maintain the head reference as part of the list structure, we can simply prepend new items with little effort. Prepending a node can be done in constant time since no traversal is required. The implementation is provided below:

Suppose we want to add the value 96 to our example list

Adding an item to the front of the list requires several steps. First, we must create a new node to store the new value

and then set its next field to point to the node currently at the front of the list

We then adjust head to point to the new node since it is now the first node in the list.

Note the order of the new links since it is important we first link the new node into the list before modifying the head reference. Otherwise, we lose our external reference to the list and in turn, we lose the list itself. The results, after linking the new node into the list are shown below.

When modifying or changing links in a linked list, we must consider the case when the list is empty. For our implementation, the code works perfectly as illustrated in Figure 7.4.1. The head reference will be null when the list is empty and the first node inserted needs the next field set to None. Thus, the next field will be set correctly.

Figure 7.4.1: The result of each step when prepending a node to an empty list.

Question 7.4.1

Consider the sequence of statements used to prepend a node to a linked list.

newNode = ListNode(item)
newNode.next = head
head = newNode

What would happen if the last two statements were reversed and head = newNode was done before newNode.next = head?

The nodes that comprise the current list would be destroyed. The head reference is the only external reference to the linked list. If it is redirected to the new node, before the new node is connected to the list, there will be no reference to the first node and it will be destroyed, resulting in a cascading effect that destroys all of the nodes.

Question 7.4.2

Suppose we want to build a linked list from the contents of a Python list by prepending each element of the Python list to the linked list. Design and implement a Python function buildList that accepts a Python list as its argument and builds and returns a linked list constructed from the elements of the Python list. The order of the values in the linked list is not important.

One possible solution is provided below:

def buildList(theValues) :
  head = None
  for element in theValues :
    newNode = ListNode(element)
    newNode.next = head
    head = newNode

  return head