Singly Linked List

Singly Linked List

A Singly Linked List is a collection of nodes where each node contains:

• data — the value stored
• next — a pointer to the next node

The last node's next always points to NULL, marking the end.

Node Structure

+--------+--------+
|  data  |  next  |------>  next node
+--------+--------+

Key Properties

• Dynamic size — grows and shrinks at runtime
• Non-contiguous memory — nodes can be anywhere in RAM
• Unidirectional — can only traverse forward
• No random access — must traverse from head to reach any node

Operations & Complexity

Operation	Time	Notes
Insert at head	O(1)	Update head pointer
Insert at tail	O(N)	Traverse to end
Delete at head	O(1)	Update head pointer
Delete by value	O(N)	Traverse to find node
Search	O(N)	Linear scan
Traverse	O(N)	Visit all nodes

When to use

Use a singly linked list when you need frequent insertions/deletions at the head and don't need backward traversal or random access.