Simple Linked Lists

What Is a Simple Linked List?

A simple (singly) linked list is a chain of nodes where each node stores two things: a value and a reference (pointer) to the next node in the sequence. The list is identified by a head pointer to the first node; the last node points to null (or None).

Unlike arrays, linked lists are not stored contiguously in memory. This makes inserting and removing elements simple when you know the relevant node, but accessing an element by index requires walking the list from the head.

Core Concepts and Terminology

• Node: Contains value and next reference.
• Head: Pointer/reference to the first node (may be null for an empty list).
• Null terminator: next is null on the last node.
• Singly vs. doubly: A simple list has only a next pointer; doubly linked lists also have a prev pointer.
• Optional tail: Keeping a tail pointer allows O(1) appends.

Operations and Time Complexity

• Traversal: O(n) to visit all nodes.
• Search by value: O(n) in the worst case.
• Access by index: O(n) (must traverse).
• Insert at head: O(1).
• Insert after a known node: O(1).
• Append at tail: O(n), or O(1) if you maintain a tail pointer.
• Delete head: O(1).
• Delete after a known node: O(1).

When to Use a Simple Linked List

• You need frequent insertions/removals at the beginning or after known nodes.
• The data size changes often and you want dynamic growth without resizing.
• Predictable O(1) head operations are important (e.g., stack-like behavior).

Avoid a linked list when you need fast random access by index or tight cache locality; arrays or dynamic arrays may be better in those cases.

Illustrative Pseudocode

// Node structure (conceptual)
node {
  value
  next // reference to next node or null
}

// Insert at head
function push_front(ref head, value):
  n = new node(value)
  n.next = head
  head = n

// Insert after a given node u
function insert_after(u, value):
  if u is null: error
  n = new node(value)
  n.next = u.next
  u.next = n

// Delete first node with matching value
function delete_first(ref head, value):
  cur = head
  prev = null
  while cur != null and cur.value != value:
    prev = cur
    cur = cur.next
  if cur == null: return false
  if prev == null: head = cur.next
  else: prev.next = cur.next
  free(cur)
  return true

Compact C Example

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

typedef struct Node {
    int data;
    struct Node* next;
} Node;

void push_front(Node** head, int x) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = x;
    n->next = *head;
    *head = n;
}

void push_back(Node** head, int x) {
    Node* n = (Node*)malloc(sizeof(Node));
    n->data = x; n->next = NULL;
    if (!*head) { *head = n; return; }
    Node* cur = *head;
    while (cur->next) cur = cur->next;
    cur->next = n;
}

bool delete_first(Node** head, int x) {
    Node** cur = head;
    while (*cur && (*cur)->data != x) cur = &(*cur)->next;
    if (!*cur) return false;
    Node* tmp = *cur;
    *cur = tmp->next;
    free(tmp);
    return true;
}

void print_list(Node* head) {
    for (Node* p = head; p; p = p->next) printf("%d -> ", p->data);
    printf("NULL\n");
}

void free_list(Node* head) {
    while (head) { Node* n = head; head = head->next; free(n); }
}

int main(void) {
    Node* head = NULL;
    push_front(&head, 3);
    push_front(&head, 1);
    push_back(&head, 5);
    print_list(head);      // 1 -> 3 -> 5 -> NULL
    delete_first(&head, 3);
    print_list(head);      // 1 -> 5 -> NULL
    free_list(head);
    return 0;
}

Compact Python Example

class Node:
    def __init__(self, data, nxt=None):
        self.data = data
        self.next = nxt

class SinglyList:
    def __init__(self):
        self.head = None

    def push_front(self, x):
        self.head = Node(x, self.head)

    def append(self, x):
        n = Node(x)
        if not self.head:
            self.head = n
            return
        cur = self.head
        while cur.next:
            cur = cur.next
        cur.next = n

    def delete_first(self, x):
        cur, prev = self.head, None
        while cur and cur.data != x:
            prev, cur = cur, cur.next
        if not cur:
            return False
        if prev is None:
            self.head = cur.next
        else:
            prev.next = cur.next
        return True

    def __iter__(self):
        cur = self.head
        while cur:
            yield cur.data
            cur = cur.next

lst = SinglyList()
lst.push_front(3)
lst.push_front(1)
lst.append(5)
print(list(lst))   # [1, 3, 5]
lst.delete_first(3)
print(list(lst))   # [1, 5]

Design Variations and Tips

• Sentinel (dummy) head: Use a non-data head node to simplify insert/delete edge cases.
• Tail pointer: Keep a pointer to the last node for O(1) appends.
• Size counter: Maintain a length field to avoid O(n) size queries.
• Functional style: In immutable lists, operations return new heads; garbage collection reclaims unused nodes.
• Cycle detection: Use Floyd’s tortoise–hare algorithm to detect loops.

Trade-offs and Pitfalls

• Cache locality: Poorer than arrays due to non-contiguous storage.
• Memory overhead: Each node stores a pointer; may increase memory use.
• Pointer safety: In manual-memory languages, watch for leaks, double frees, and dangling pointers.
• Boundary cases: Empty list, single-node list, insertion/deletion at head and tail.

Common Uses

• Implementing stacks and queues (especially when head/tail operations dominate).
• Separate chaining in hash tables.
• Adjacency lists in graphs.
• Streaming buffers and schedulers where order and dynamic resizing matter.

Next Topic