Why Doubly Linked List Over Singly Linked List in DSA Javascript - Why It Works

Concept Flow - Why Doubly Linked List Over Singly Linked List

Start with Singly Linked List

↓

Can only move forward

↓

Operations like reverse/traverse backward are hard

↓

Add 'prev' pointer to each node

↓

Now Doubly Linked List

↓

Can move forward and backward easily

↓

More flexible but uses more memory

Shows how adding a backward pointer to singly linked list nodes creates a doubly linked list that supports two-way traversal.

Execution Sample

DSA Javascript

class Node {
  constructor(data) {
    this.data = data;
    this.next = null;
    this.prev = null;
  }
}

Defines a doubly linked list node with data, next, and prev pointers.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	Create node A	A	head -> A	A(prev: null, next: null)
2	Create node B	A -> B	A.next -> B, B.prev -> A	A(prev: null, next: B) <-> B(prev: A, next: null)
3	Create node C	A -> B -> C	B.next -> C, C.prev -> B	A <-> B <-> C (C.next: null)
4	Traverse forward from head	A -> B -> C	No pointer changes	Traverse order: A -> B -> C
5	Traverse backward from tail	A -> B -> C	No pointer changes	Traverse order: C -> B -> A
6	Remove node B	A -> C	A.next -> C, C.prev -> A	A <-> C (B removed)
7	Try backward traversal after removal	A -> C	No pointer changes	Traverse order: C -> A
8	End	A -> C	No pointer changes	Final list: A <-> C

💡 Traversal ends when next or prev pointer is null; removal updates pointers to skip removed node.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 6	Final
head	null	A	A	A	A	A
tail	null	A	B	C	C	C
A.next	null	null	B	B	C	C
A.prev	null	null	null	null	null	null
B.next	null	null	null	C	null	null
B.prev	null	null	A	A	null	null
C.next	null	null	null	null	null	null
C.prev	null	null	null	B	A	A

Key Moments - 3 Insights

Why do we need the 'prev' pointer in a doubly linked list?

The 'prev' pointer allows moving backward through the list easily, as shown in steps 4 and 5 where traversal happens forward and backward. Without it, backward traversal is not possible.

What happens to pointers when a node is removed?

When node B is removed at step 6, pointers of adjacent nodes A and C are updated to point to each other, skipping B. This keeps the list connected without B.

Does a doubly linked list use more memory than a singly linked list?

Yes, because each node stores an extra 'prev' pointer, which uses more memory but provides more flexibility, as seen in the node structure in the execution sample.

Visual Quiz - 3 Questions

Look at the execution table at step 3, what is the 'prev' pointer of node C pointing to?

A null

B Node A

C Node B

D Node C itself

💡 Hint

Check the 'Pointer Changes' and 'Visual State' columns at step 3.

At which step does the list no longer contain node B?

A Step 6

B Step 5

C Step 4

D Step 7

💡 Hint

Look for the 'Remove node B' operation in the execution table.

If we remove the 'prev' pointer from nodes, which operation becomes impossible as shown in the table?

A Forward traversal

B Backward traversal

C Node creation

D Node removal

💡 Hint

Check steps 4 and 5 where forward and backward traversals are shown.

Concept Snapshot

Doubly Linked List nodes have two pointers: next and prev.
Allows traversal in both directions.
More flexible than singly linked list.
Uses more memory due to extra pointer.
Useful for operations needing backward movement.
Pointers must be updated carefully on insert/delete.

Full Transcript

A doubly linked list is like a singly linked list but with an extra pointer in each node pointing to the previous node. This allows moving forward and backward through the list easily. The code example shows a node with data, next, and prev pointers. The execution table traces creating nodes A, B, and C, linking them forward and backward. Traversals forward and backward are demonstrated. Removing node B updates pointers of A and C to skip B, keeping the list connected. The variable tracker shows how pointers change after each step. Key moments clarify why the prev pointer is needed, how removal updates pointers, and the memory cost of extra pointers. The quiz tests understanding of pointer directions, removal step, and traversal capabilities. Overall, doubly linked lists offer more flexibility at the cost of extra memory and pointer management.

Practice

1. Why might you choose a doubly linked list over a singly linked list in a program?

easy

A. Because it only stores one pointer per node

B. Because it uses less memory than singly linked list

C. Because it allows traversal in both directions easily

D. Because it is simpler to implement

Solution

1. Step 1: Understand traversal directions

   A singly linked list allows moving only forward through nodes, while a doubly linked list allows moving forward and backward.

2. Step 2: Compare memory and complexity

   Doubly linked lists use more memory because each node stores two pointers, but they enable easier backward traversal.

3. Final Answer:

   Because it allows traversal in both directions easily -> Option C

4. Quick Check:

   Traversal directions = Both ways [OK]

Hint: Doubly linked lists have two pointers per node [OK]

Common Mistakes:

• Thinking doubly linked lists use less memory
• Confusing simplicity with singly linked lists
• Assuming singly linked lists allow backward traversal

2. Which of the following is the correct way to define a node in a doubly linked list in JavaScript?

easy

A. class Node { constructor(value) { this.value = value; this.prev = null; this.next = null; } }

B. class Node { constructor(value) { this.value = value; this.prev = null; } }

C. class Node { constructor(value) { this.value = value; this.next = null; } }

D. class Node { constructor(value) { this.value = value; this.next = null; this.prev = value; } }

Solution

1. Step 1: Identify required pointers in doubly linked list node

   A doubly linked list node must have both prev and next pointers to link backward and forward.

2. Step 2: Check constructor correctness

   class Node { constructor(value) { this.value = value; this.prev = null; this.next = null; } } correctly initializes prev and next to null along with the value.

3. Final Answer:

   class Node { constructor(value) { this.value = value; this.prev = null; this.next = null; } } -> Option A

4. Quick Check:

   Node has prev and next pointers [OK]

Hint: Doubly linked list nodes have prev and next pointers [OK]

Common Mistakes:

• Omitting the prev pointer
• Assigning prev to value instead of null
• Defining only next pointer

3. Consider this code snippet for a doubly linked list traversal backward:

let current = tail;
let result = [];
while (current !== null) {
  result.push(current.value);
  current = current.prev;
}
console.log(result);

What will be the output if the list contains nodes with values 1 -> 2 -> 3 (head to tail)?

medium

A. [3, 2, 1]

B. [1, 2, 3]

C. [null]

D. Error: current.prev is undefined

Solution

1. Step 1: Understand traversal starting point

   The traversal starts at tail, which holds the value 3 in the list 1 -> 2 -> 3.

2. Step 2: Trace backward traversal

   It pushes values 3, then moves to 2, pushes 2, then moves to 1, pushes 1, then stops at null.

3. Final Answer:

   [3, 2, 1] -> Option A

4. Quick Check:

   Backward traversal outputs reversed list [OK]

Hint: Backward traversal prints list in reverse order [OK]

Common Mistakes:

• Assuming output is forward order
• Confusing head and tail starting points
• Expecting error due to null check missing

4. The following code tries to remove the last node from a doubly linked list but causes an error:

function removeLast(tail) {
  if (!tail) return null;
  let prevNode = tail.prev;
  prevNode.next = null;
  return prevNode;
}

What is the error and how to fix it?

medium

A. Error because tail is not updated; fix by returning tail instead

B. Error if tail.prev is null; fix by checking if prevNode exists before setting next

C. No error; code works fine

D. Error because next pointer should be set to tail, fix by assigning tail.next = null

Solution

1. Step 1: Identify error cause

   If the list has only one node, tail.prev is null, so prevNode.next causes an error.

2. Step 2: Fix by adding null check

   Before setting prevNode.next = null, check if prevNode exists to avoid error.

3. Final Answer:

   Error if tail.prev is null; fix by checking if prevNode exists before setting next -> Option B

4. Quick Check:

   Check prevNode before access [OK]

Hint: Check for null before accessing prevNode.next [OK]

Common Mistakes:

• Ignoring single-node list edge case
• Assuming tail always has a prev node
• Not returning updated tail correctly

5. You want to implement a feature that requires frequent backward and forward traversal and quick deletion of nodes from anywhere in the list. Which data structure is best and why?

hard

A. Stack, because it supports LIFO operations

B. Singly linked list, because it uses less memory

C. Array, because it allows random access

D. Doubly linked list, because it supports traversal in both directions and easy deletion

Solution

1. Step 1: Analyze traversal needs

   Frequent backward and forward traversal requires a structure that supports moving in both directions easily.

2. Step 2: Analyze deletion needs

   Quick deletion from anywhere is easier if nodes have pointers to previous nodes, so you can update links without full traversal.

3. Step 3: Compare options

   Singly linked lists lack backward pointers, arrays have costly deletions, stacks only allow LIFO access.

4. Final Answer:

   Doubly linked list, because it supports traversal in both directions and easy deletion -> Option D

5. Quick Check:

   Bidirectional traversal + easy deletion = Doubly linked list [OK]

Hint: Bidirectional traversal needs doubly linked list [OK]

Common Mistakes:

• Choosing singly linked list for backward traversal
• Choosing array ignoring deletion cost
• Confusing stack with linked list