Introduction to LinkedList

Grokking Data Structures & Algorithms for Coding Interviews

Ask Author

Back to course home

0% completed

Vote For New Content

Introduction to LinkedList

Table of Contents

Contents are not accessible

A linked list consists of nodes that are connected sequentially. Each node contains:

Data – The value stored in the node.
Pointer (Next Reference) – A reference to the next node in the list.

A linked list always has a starting point (Head) and may have an ending point (Tail), depending on the type of linked list. If a node does not point to another node, its reference is set to NULL.

Key Components of a Linked List

1. Node

A node is the building block of a linked list. Each node consists of two parts:

Data → Stores the actual value.
Next Pointer → Points to the next node in the sequence.

2. Head

The head is the first node of the linked list. It stores the reference to the first node. If the list is empty, the head is set to NULL.

3. Tail

The tail is the last node of the linked list. In a singly linked list, the tail’s next pointer is NULL. In circular linked lists, it points back to the head.

4. Null Reference

The last node in a singly linked list points to NULL, indicating the end of the list.

Basic Representation of a Singly Linked List

The head stores a reference to the first node.
Each node contains data and a next pointer.
The last node’s pointer is NULL, indicating the end of the list.

Comparison: Linked List vs. Array

Feature	Arrays	Linked Lists
Memory Allocation	Fixed size (Static)	Grows dynamically
Insertion/Deletion	Costly (O(n) shifting required)	Efficient (O(1) if head/tail known)
Random Access	O(1) (Direct access via index)	O(n) (Sequential access)
Memory Utilization	May have unused slots	Uses only required memory
Contiguous Memory	Yes	No
Search Complexity	O(1) for index-based access, O(n) for search	O(n)

Applications of Linked Lists

✅ Dynamic Memory Management – Used in operating systems for efficient memory allocation.
✅ Undo/Redo Operations – Applications like text editors maintain change history using linked lists.
✅ Graph Representations (Adjacency List) – Graphs use linked lists to store connected nodes efficiently.
✅ File Systems – Linked lists manage disk storage efficiently by linking file blocks.
✅ Music & Image Galleries – Used in applications where "Next" and "Previous" navigation is required.
✅ LRU Cache Implementation – Doubly linked lists help implement Least Recently Used (LRU) Cache.
✅ Polynomial Arithmetic – Polynomial equations are stored as linked lists for easy computation.

In the next lesson, we will explore the different types of linked lists (Singly, Doubly, and Circular) and their implementations!

.....

Like the course? Get enrolled and start learning!

Table of Contents

Contents are not accessible