Singly Linked Lists

A singly linked list is a sequence of nodes where each node stores a value and a pointer to the next node.

struct Node {
  int value;
  struct Node* next;
};

The list usually stores a pointer to the head node. It may also store a tail pointer to make appending $O(1)$.

Nodes

A node is not stored next to the next node in memory. Traversal follows pointers from one node to the next:

head -> [value | next] -> [value | next] -> [value | NULL]

Because nodes are not contiguous, linked lists have worse cache locality than arrays.

Complexity

Operation	Without tail pointer	With tail pointer
Access by index	$O(n)$	$O(n)$
Search by value	$O(n)$	$O(n)$
Insert at head	$O(1)$	$O(1)$
Insert at tail	$O(n)$	$O(1)$
Delete head	$O(1)$	$O(1)$
Delete tail	$O(n)$	$O(n)$
Delete known next node	$O(1)$	$O(1)$
Concatenate lists	$O(n)$	$O(1)$
Space	$O(n)$	$O(n)$

When to Use

Use a singly linked list when you need cheap insertion or removal at the head, stable node references, or simple queue-like behavior with a tail pointer.

Do not use it when you need fast random access, binary search, or tight cache performance. Arrays and dynamic arrays are usually better defaults.