Linked List

A linked list is a linear data structure made up of nodes connected through references. Unlike arrays, linked lists do not store elements in contiguous memory locations. Each node contains data and a reference to the next node in the sequence, allowing flexible memory usage and efficient insertions and deletions.

Linked lists are widely used in areas such as dynamic memory management, implementation of stacks and queues, adjacency lists in graphs, and operating system kernels.

What Is a Linked List?

A linked list consists of:

• Nodes - individual elements that store data
• Links (Pointers) - references that connect nodes
• Head - the first node in the list
• Tail - the last node in the list (optional but common)

A key property of linked lists is that elements are not stored contiguously, and traversal must occur sequentially.

Basic Terminology

Understanding linked list terminology is essential before working with linked list algorithms.

Node

A node is the basic building block of a linked list. Each node contains:

• Data
• Reference to the next node

[Data | Next] → [Data | Next] → [Data | Next]

Head

The head is the first node in the linked list. All traversals begin from the head.

Head
 ↓
[1] → [2] → [3]

Tail

The tail is the last node in the linked list. Its next reference is usually null.

[1] → [2] → [3]
               ↑
             Tail

Next Pointer

The next pointer connects one node to the next node in the sequence.

[Data | Next] ──► Next Node

Traversal

Traversal means visiting each node in order, starting from the head and following the next pointers until the end of the list is reached.

Head → Node 1 → Node 2 → Node 3 → null

Types of Linked Lists (High-Level Overview)

Here are common linked list variations:

Common Operations

Linked lists commonly support:

• Insertion (at head, tail, or middle)
• Deletion (by value or position)
• Traversal
• Searching
• Reversal

These operations behave differently compared to arrays due to pointer-based access.

Linked List vs Array

Why Linked Lists Are Useful

Linked lists are particularly useful when:

• Frequent insertions and deletions are required
• Memory size is dynamic or unknown
• Sequential access is sufficient
• Building higher-level data structures

Although linked lists do not support fast random access, their flexibility makes them a fundamental building block in many systems.