Singly Linked List

data-structures

Definition

Singly Linked List

A singly linked list is a linear data structure consisting of a sequence of nodes, where each node contains:

• Value: The data stored in the node.
• Next: A pointer or reference to the subsequent node in the sequence, or null if it is the terminal node (tail).

Unlike an array, a linked list does not store elements in contiguous memory locations. Instead, nodes are linked using pointers, allowing for efficient insertions and deletions.

Visual Representation

Complexity

The following table outlines the time complexity of operations on a singly linked list of size $n$:

Operation	Complexity	Description
Access	$O(n)$	Must traverse from the head to the $i$-th node.
Search	$O(n)$	Linear scan for a specific value.
Insertion (at head)	$O(1)$	Update the head pointer.
Insertion (at tail)	$O(1)$	If a tail pointer is maintained; otherwise $O(n)$.
Deletion (at head)	$O(1)$	Move head pointer to the second node.
Deletion (at tail)	$O(n)$	Must find the penultimate node to update its next pointer.

Implementation Details

The head of the list is the entry point for all operations. If the head is null, the list is empty. Singly linked lists are primarily used for implementing other structures like stacks and queues.