Siksha Sarovar

Siksha Sarovar (sikshasarovar.com) is a free educational web application that helps students in India learn programming and prepare for academic and competitive exams. The platform offers structured coding courses (C, C++, Python, Java, HTML, CSS, PHP, Power BI, AI, Machine Learning, Data Science), complete university curriculum notes for BCA/MCA students with previous year question papers, Class 10 and Class 12 CBSE/HBSE school notes, and dedicated preparation material for SSC, UPSC, Banking, Railway and other government exams. Browsing the site is completely free and requires no account. Users may optionally sign in with Google solely to save their learning progress, quiz scores and personal preferences across devices.

Privacy Policy | Terms of Service | Contact Siksha Sarovar | About Siksha Sarovar

v4.0.9 · PWA
Siksha Sarovar logo
Siksha Sarovar
Your Learning Universe

Siksha Sarovar is a free e-learning platform for coding courses, BCA university notes and competitive exam preparation. Optional Google sign-in saves your learning progress across devices.

Initializing knowledge base…
Compiling modules 0%

Unit 2: Introduction to Linked Lists

Lesson 5 of 14 in the free Data Structure notes on Siksha Sarovar, written by Rohit Jangra.

Linked Lists: Conceptual Overview

A Linked List is a fundamental linear data structure that breaks away from the rigid memory allocation of arrays. Each element (node) contains the data AND a pointer to the next element.

Node Structure:

[ Data | Next ] → [ Data | Next ] → [ Data | NULL ]
   Head                                    Tail
  1. Data Field: The actual value (e.g., Student ID, Name, Integer).
  2. Next Pointer: A reference address pointing to the subsequent node. The last node points to NULL.

Array vs Linked List — Comprehensive Comparison

FeatureArrayLinked List
MemoryContiguous block, compile-timeScattered nodes, run-time
SizeFixed (must declare size)Dynamic (grows/shrinks)
AccessO(1) random access by indexO(n) sequential from Head
Insert at BeginningO(n) — shift all elementsO(1) — change Head pointer
Insert at EndO(1) if space availableO(n) — traverse to end (O(1) with tail pointer)
Insert in MiddleO(n) — shift elementsO(1) — if position known (pointer change)
DeleteO(n) — shift elementsO(1) — if position known
Memory OverheadNone (just data)Extra pointer per node
Cache PerformanceExcellent (locality)Poor (scattered memory)
Memory WastageIf over-allocatedOnly per-node pointer overhead

Types of Linked Lists

TypeStructureTraversalPointers per Node
Singly (SLL)A → B → C → NULLForward only1 (Next)
Doubly (DLL)NULL ← A ⇄ B ⇄ C → NULLForward & Backward2 (Prev, Next)
Circular (CLL)A → B → C → A (loops)Continuous loop1 (Next)
Circular DLLA ⇄ B ⇄ C ⇄ A (loops both ways)Bidirectional loop2 (Prev, Next)

Operations — Time Complexity

OperationSingly LLDoubly LLNotes
TraversalO(n)O(n)Visit every node
SearchO(n)O(n)Must traverse
Insert at HeadO(1)O(1)Change Head pointer
Insert at TailO(n) / O(1)*O(1)**With tail pointer
Insert at PositionO(n)O(n)Must traverse to position
Delete at HeadO(1)O(1)Update Head
Delete at TailO(n)O(1)DLL has prev pointer
Delete by ValueO(n)O(n)Search + unlink

Operations on Linked List: A Deeper Look

1. Traversal (The Walk) Starting from the Head, visit every node until NULL.

ptr = Head
while (ptr ≠ NULL):
    process(ptr→data)
    ptr = ptr→next

2. Insertion Cases

CaseStepsPointer Changes
At Beginning1. Create new node 2. Point new→next to Head 3. Update HeadHead = newNode
At End1. Traverse to last node 2. Point last→next to new nodelast→next = newNode
In Middle (after X)1. Find node X 2. Point new→next to X→next 3. Point X→next to newnew→next = X→next; X→next = new

3. Deletion (The Bypass) Find the node before the target. Change its pointer to skip the target. Free the target's memory.

4. Searching Iterate through the list, comparing each node's data with the search key. Return position or NULL.