Singly Linked List Insertion

Adding Nodes to a List

Unlike arrays, linked lists don't require shifting elements to make space for a new one. Instead, adding a node is a matter of carefully redirecting pointers. The logic is straightforward, but the order of operations is critical. One wrong move, and you could lose the entire rest of the list.

Inserting at the Head

Adding a new node to the front of the list, often called prepending, is the most efficient insertion operation. It's a constant time, $O(1)$ , operation because it doesn't matter how long the list is. The steps are always the same.

First, you create your new node. Then, you link it into the chain by setting its next pointer to the list's current head. Finally, you update the list's head pointer to reference your new node, making it the official start of the list.

To insert a new node at the front, we create a new node and point its next reference to the current head of the linked list.

What about inserting into an empty list? This same logic handles it perfectly. If the list is empty, head is null. The new node's next pointer is set to null, and the head is then updated to point to the new node. The result is a correct list with a single element.

```pseudocode
function prepend(list, value):
  // Create a new node with the given value
  newNode = new Node(value)

  // Point the new node's next to the current head
  newNode.next = list.head

  // Update the list's head to be the new node
  list.head = newNode

Inserting at the Tail

Adding a node to the end of the list, or appending, requires finding the last node first. This means we must traverse the list from the head until we find a node whose next pointer is null. This traversal makes appending an $O(n)$ operation, as its time cost grows linearly with the number of nodes.

Once we find the last node, the process is simple: we set its next pointer to our new node. The new node's next pointer will already be null by default, correctly marking it as the new end of the list. A common optimization to avoid the $O(n)$ traversal is to maintain a separate that always references the last node, making appends an $O(1)$ operation.

```pseudocode
function append(list, value):
  newNode = new Node(value)

  // If the list is empty, the new node is the head
  if list.head is null:
    list.head = newNode
    return

  // Traverse to find the last node
  current = list.head
  while current.next is not null:
    current = current.next
  
  // Point the last node to the new node
  current.next = newNode

Inserting in the Middle

To insert a node at a specific position, you must first traverse the list to find the node that will come before your desired insertion point. Let's call this the previous node. The traversal makes this an $O(n)$ operation.

Once you've located the previous node, the sequence of pointer assignments is crucial. If you change previous.next first, you lose your link to the rest of the list. You must first set your new node's next pointer to what previous.next is currently pointing to. Only then can you safely update previous.next to point to your new node. This two-step shuffle effectively splices the new node into the list without breaking the chain.

The golden rule: Always attach the new node to the rest of the list before you attach the front of the list to the new node.

This careful sequence ensures the list's integrity is maintained.

Quiz Questions 1/4

What is the time complexity of adding a new node to the front (prepending) of a singly linked list?

Quiz Questions 2/4

When inserting a newNode into a linked list after a previousNode, what is the correct sequence of operations to avoid losing the rest of the list?

Linked List Operations and Logic