2.2 Singly Linked Lists

Singly linked lists are one of the first dynamic data structures you'll encounter. Unlike arrays, which store elements in contiguous memory, a singly linked list chains together individual nodes that can live anywhere in memory. This makes insertion and deletion at the front extremely fast, but it means you lose the ability to jump directly to any element by index.

Singly Linked List Fundamentals

Structure of singly linked lists

A singly linked list is built from nodes, where each node holds two things: some data and a pointer (or reference) to the next node in the sequence. You can think of it like a scavenger hunt where each clue tells you where to find the next one.

• Each node contains a data field and a next pointer (e.g., Node { int data; Node* next; })
• The last node's next pointer is set to null, which signals the end of the list
• A head pointer points to the first node and serves as your entry point to the entire list
• A tail pointer (optional) points to the last node, which lets you skip the traversal when inserting at the end

Without a tail pointer, you'd have to walk through every node just to reach the end. With one, appending becomes much cheaper.

Operations for singly linked lists

Insertion

1. At the beginning:

   • Create a new node and set its next pointer to the current head
   • Update the head pointer to the new node
   • Time complexity: $O(1)$ (no traversal needed)

2. At the end (without a tail pointer):

   • Traverse the list to find the last node
   • Create a new node and set the last node's next pointer to it
   • Time complexity: $O(n)$
   • With a tail pointer, this drops to $O(1)$ since you can go straight to the last node

3. At a specific position:

   • Traverse to the node before the desired position
   • Create a new node, point it to the current node's next
   • Update the current node's next pointer to the new node
   • Time complexity: $O(n)$

Deletion

1. From the beginning:

   • Save a reference to the current head
   • Update the head pointer to head.next
   • Deallocate the old head node
   • Time complexity: $O(1)$

2. From the end:

   • Traverse to the second-to-last node
   • Set its next pointer to null
   • Update the tail pointer (if used) to this node
   • Deallocate the old last node
   • Time complexity: $O(n)$ (even with a tail pointer, because you need the second-to-last node)

3. From a specific position:

   • Traverse to the node before the target
   • Update its next pointer to skip over the target node
   • Deallocate the deleted node
   • Time complexity: $O(n)$

A common mistake: forgetting to update the head or tail pointer after insertion or deletion. If you delete the only node in the list, both head and tail should become null.

Traversal starts at the head and follows next pointers until you hit null. Time complexity: $O(n)$. There's no way to go backwards in a singly linked list, so if you pass the node you need, you have to start over from the head.

Singly Linked List Analysis and Applications

Complexity of linked list operations

Space complexity is $O(n)$ for $n$ elements, but each node carries overhead for storing its next pointer. For small data types like integers, this overhead can be significant compared to a plain array.

Applications of singly linked lists

• Hash table chaining: Each bucket in a hash table can be a linked list. When two keys hash to the same index (a collision), the new element is simply appended to that bucket's list. This is called separate chaining, and it's one of the most common collision resolution strategies.
• Polynomial representation: Each term of a polynomial is stored as a node containing a coefficient and an exponent. For example, $3x^2 + 2x + 1$ would be three nodes. The linked list structure makes it straightforward to add or remove terms without shifting elements around.
• Graph adjacency lists: Each vertex in a graph has a linked list of its neighbors. This is memory-efficient for sparse graphs (graphs with relatively few edges) compared to storing a full adjacency matrix.
• Undo functionality: Some implementations store each user action as a node. To undo, you walk back through the list and reverse the most recent action. (In practice, a stack is more common for undo, but a linked list can serve as the underlying structure for that stack.)