Singly Linked List: Structure, Operations, and Traversal

Singly Linked List Fundamentals

A singly linked list is a linear data structure where each element (node) contains data and a pointer to the next node. Unlike arrays, linked list elements are not stored in contiguous memory.

Node Structure

class Node:
    data: any
    next: Node | null

Each node holds a value and a reference (next) to the following node. The last node's next pointer is null, marking the end of the list.

Core Operations

Insert at head — O(1):

newNode.next = head
head = newNode

Insert at tail — O(n): Traverse to the last node, then set lastNode.next = newNode. With a tail pointer, this becomes O(1).

Delete a node — O(n): Find the node before the target, then set prev.next = target.next. Deleting the head is O(1).

Search — O(n): Traverse from head, comparing each node's data until found or reaching null.

Traversal Pattern

current = head
while current is not null:
    process(current.data)
    current = current.next

This is the fundamental pattern for visiting every element. There is no random access — you cannot jump to the 5th element directly.

Advantages Over Arrays

• Dynamic size: No need to declare size upfront. Grows and shrinks as needed.
• Efficient insertion/deletion: Inserting or deleting at the head is O(1). No shifting of elements required.
• No wasted space: Each node uses exactly the memory it needs (plus pointer overhead).

Disadvantages

• No random access: Accessing the nth element requires traversing n nodes — O(n) vs O(1) for arrays.
• Extra memory: Each node stores a pointer in addition to data.
• Poor cache performance: Nodes may be scattered in memory, causing cache misses during traversal.