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: Two-Way and Header Lists

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

Two-Way Lists (Doubly Linked Lists)

A Singly Linked List is a one-way street. You can only move forward. If you are at Node 50 and need Node 49, you must start from the beginning. A Doubly Linked List (DLL) constructs a two-way street.

DLL Node Structure:

[NULL|Prev] ← [Prev|Data|Next] ⇄ [Prev|Data|Next] ⇄ [Prev|Data|Next] → [Next|NULL]

SLL vs DLL vs CLL — Complete Comparison

FeatureSingly (SLL)Doubly (DLL)Circular (CLL)
Pointers per Node1 (Next)2 (Prev, Next)1 (Next, last→Head)
TraversalForward onlyForward & BackwardContinuous loop
Memory per NodeLess (1 pointer)More (2 pointers)Same as SLL
Delete given nodeNeed predecessor (O(n))Direct (O(1))Need predecessor
Insert before nodeO(n) — need predecessorO(1) — has prevO(n)
Last node accessO(n)O(1) with tailO(1) with tail
ComplexitySimplestMost flexibleGood for cycling

Insertion & Deletion — DLL vs SLL

OperationSLLDLL
Insert at Headnew→next = head; head = newnew→next = head; head→prev = new; head = new
Insert after node Xnew→next = X→next; X→next = newnew→next = X→next; new→prev = X; X→next→prev = new; X→next = new
Delete node XNeed to find predecessor of XX→prev→next = X→next; X→next→prev = X→prev
Reverse listO(n) — rebuild linksO(n) — swap prev/next for each node

Linked Lists with Headers

A Header Linked List uses a dedicated, permanent node at the front called the Header Node (instead of a simple pointer).

Header Node Roles:

  • Metadata Storage: Total count of nodes, max/min value, etc.
  • Sentinel: The list is never truly "empty" — simplifies boundary conditions.
TypeLast Node Points ToVisual
Grounded HeaderNULLHeader → A → B → C → NULL
Circular HeaderBack to Header NodeHeader → A → B → C → Header (loop)

Applications of Different List Types

ApplicationList TypeWhy
Browser HistoryDLLForward/Back navigation
Music Playlist (Repeat)Circular SLLLoops back to first song
Undo/Redo in EditorDLLNavigate both directions in history
Polynomial ArithmeticHeader ListHeader stores degree; terms as nodes
Round Robin SchedulingCircular HeaderOS cycles through processes continuously
Memory AllocationCircular DLLOS free-list management
LRU CacheDLL + Hash MapO(1) access and reordering