Dequeue Using Linked List in DSA Go - Execution Trace

Concept Flow - Dequeue Using Linked List

Create new node

↓

Is Dequeue empty?

Yes→Set head and tail to new node

No↓

Insert at front or rear

↓

Update pointers accordingly

↓

Done

Shows how nodes are added or removed from front or rear by updating pointers in the linked list.

Execution Sample

DSA Go

type Node struct {
  data int
  next *Node
  prev *Node
}

// InsertFront, InsertRear, DeleteFront, DeleteRear methods

Basic operations to add or remove nodes at both ends of a doubly linked list representing a dequeue.

Execution Table

Step	Operation	Nodes in List	Pointer Changes	Visual State
1	InsertRear(10)	10	head -> 10, tail -> 10	10 <-> null
2	InsertRear(20)	10 -> 20	tail.next -> 20, 20.prev -> tail, tail -> 20	10 <-> 20 <-> null
3	InsertFront(5)	5 -> 10 -> 20	5.next -> head, head.prev -> 5, head -> 5	5 <-> 10 <-> 20 <-> null
4	DeleteFront()	10 -> 20	head -> 10, 10.prev -> null	10 <-> 20 <-> null
5	DeleteRear()	10	tail -> 10, 10.next -> null	10 <-> null
6	DeleteFront()	empty	head -> null, tail -> null	null
7	DeleteRear()	empty	No change, list empty	null

💡 Operations stop after list becomes empty and further deletes have no effect.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 5	After Step 6	After Step 7
head	null	Node(10)	Node(10)	Node(5)	Node(10)	Node(10)	null	null
tail	null	Node(10)	Node(20)	Node(20)	Node(20)	Node(10)	null	null
list size	0	1	2	3	2	1	0	0

Key Moments - 3 Insights

Why do we update both head and tail when inserting the first node?

Because when the list is empty (step 1), the new node is both the first and last node, so head and tail must point to it (see execution_table step 1).

Why does deleting from front update head.prev to null?

To disconnect the removed node and mark the new head's prev pointer as null, ensuring no backward link to old node (see execution_table step 4).

What happens if we delete from an empty dequeue?

No pointer changes occur and the list remains empty, as shown in step 7 where delete rear on empty list does nothing.

Visual Quiz - 3 Questions

Look at the execution table, what is the list state after step 3?

A 5 <-> 10 <-> 20 <-> null

B 10 <-> 20 <-> null

C 10 <-> null

D null

💡 Hint

Check the Visual State column at step 3 in the execution_table.

At which step does the list become empty?

A Step 5

B Step 6

C Step 4

D Step 7

💡 Hint

Look at the Nodes in List column to find when it shows 'empty'.

If we insert 15 at the front after step 2, what will be the new head's data?

A 10

B 20

C 15

D 5

💡 Hint

Refer to the pointer changes and head updates shown in step 3.

Concept Snapshot

Dequeue using doubly linked list:
- InsertFront: add node before head, update head
- InsertRear: add node after tail, update tail
- DeleteFront: remove head, update head
- DeleteRear: remove tail, update tail
- Handle empty list by setting head and tail to null

Full Transcript

This visual trace shows how a dequeue works using a doubly linked list. We start with an empty list. When we insert at rear, if empty, head and tail point to the new node. Otherwise, tail's next points to new node and new node's prev points to old tail. Insert front is similar but at head. Deleting front moves head forward and removes backward link. Deleting rear moves tail backward and removes forward link. When list becomes empty, head and tail are null. Trying to delete from empty list does nothing. The variable tracker shows how head, tail, and list size change after each operation. Key moments clarify why pointers update certain ways. The quiz tests understanding of list state after operations.

Practice

1. What is the main advantage of implementing a dequeue using a linked list compared to an array?

easy

A. It automatically sorts the elements.

B. It uses less memory than an array.

C. It allows insertion and deletion from both ends in constant time.

D. It prevents duplicate elements.

Solution

1. Step 1: Understand dequeue operations

   A dequeue supports insertion and deletion at both front and rear ends.

2. Step 2: Compare linked list vs array

   Linked list allows these operations in constant time without shifting elements, unlike arrays.

3. Final Answer:

   It allows insertion and deletion from both ends in constant time. -> Option C

4. Quick Check:

   Linked list dequeue = O(1) insert/delete both ends [OK]

Hint: Linked list avoids shifting, so both ends operate fast [OK]

Common Mistakes:

• Thinking arrays allow O(1) insert/delete at both ends
• Confusing memory usage advantage
• Assuming automatic sorting

2. Which of the following is the correct way to declare a node struct for a dequeue using a linked list in Go?

easy

A. type Node struct { data int; next Node; prev Node }

B. type Node struct { data int; next *Node; prev *Node }

C. type Node struct { data int; next *Node }

D. type Node struct { data int; prev *Node }

Solution

1. Step 1: Identify node fields for dequeue

   A dequeue node needs data, pointer to next and previous nodes for double linking.

2. Step 2: Check pointer usage in Go

   Pointers to Node must be *Node, not Node, to avoid recursive struct size.

3. Final Answer:

   type Node struct { data int; next *Node; prev *Node } -> Option B

4. Quick Check:

   Double linked node uses *Node pointers [OK]

Hint: Use *Node for next and prev to avoid infinite struct size [OK]

Common Mistakes:

• Using Node instead of *Node for next/prev
• Missing prev pointer for double linking
• Declaring only next pointer

3. Given the following Go code snippet for a dequeue implemented with a linked list, what will be printed after the operations?

dq := NewDequeue()
dq.InsertFront(10)
dq.InsertRear(20)
dq.InsertFront(5)
dq.DeleteRear()
dq.Display()

Assuming Display prints elements from front to rear separated by ' -> ' and ends with ' -> null'.

medium

A. 5 -> 10 -> null

B. 10 -> 5 -> null

C. 20 -> 10 -> 5 -> null

D. 5 -> 20 -> null

Solution

1. Step 1: Trace insertions and deletions

   InsertFront(10) => [10], InsertRear(20) => [10, 20], InsertFront(5) => [5, 10, 20], DeleteRear() removes 20 => [5, 10]

2. Step 2: Determine display output

   Display prints front to rear: 5 -> 10 -> null

3. Final Answer:

   5 -> 10 -> null -> Option A

4. Quick Check:

   After operations, dequeue = 5, 10 [OK]

Hint: Track front and rear changes step-by-step [OK]

Common Mistakes:

• Forgetting DeleteRear removes last element
• Mixing order of InsertFront and InsertRear
• Printing rear to front instead of front to rear

4. Consider this buggy Go code snippet for deleting from the front of a dequeue implemented with a linked list:

func (dq *Dequeue) DeleteFront() {
    if dq.front == nil {
        fmt.Println("Dequeue is empty")
        return
    }
    dq.front = dq.front.next
    dq.front.prev = nil
}

What is the error in this code?

medium

A. It does not check if dq.front.next is nil before setting dq.front.prev.

B. It should not set dq.front.prev to nil.

C. It should update dq.rear.prev instead of dq.front.prev.

D. It should set dq.rear to nil when the last element is deleted.

Solution

1. Step 1: Analyze deletion when only one element exists

   If only one node exists, after dq.front = dq.front.next, dq.front becomes nil.

2. Step 2: Check rear pointer update

   Rear pointer still points to old node; it must be set to nil to avoid dangling pointer.

3. Final Answer:

   It should set dq.rear to nil when the last element is deleted. -> Option D

4. Quick Check:

   Update rear on last element deletion [OK]

Hint: Update rear pointer when dequeue becomes empty [OK]

Common Mistakes:

• Not updating rear when front becomes nil
• Assuming front.prev always exists
• Confusing prev and next pointers

5. You want to implement a function in Go that reverses the elements of a dequeue implemented using a doubly linked list. Which approach correctly reverses the dequeue in-place?

hard

A. Traverse each node, swap its next and prev pointers, then swap front and rear pointers of the dequeue.

B. Create a new dequeue and insert elements from the old dequeue's front to rear into the new dequeue's rear.

C. Swap only the data values of front and rear nodes repeatedly until the middle is reached.

D. Delete all elements from front and insert them at rear repeatedly until original dequeue is empty.

Solution

1. Step 1: Understand in-place reversal of doubly linked list

   Swapping next and prev pointers of each node reverses the links.

2. Step 2: Update dequeue front and rear pointers

   After swapping pointers, front and rear pointers must be swapped to reflect new ends.

3. Final Answer:

   Traverse each node, swap its next and prev pointers, then swap front and rear pointers of the dequeue. -> Option A

4. Quick Check:

   Swap pointers in nodes + swap front/rear [OK]

Hint: Swap next/prev in nodes, then swap front and rear [OK]

Common Mistakes:

• Creating new dequeue instead of in-place reversal
• Swapping only data values without pointers
• Deleting and reinserting nodes unnecessarily