Dequeue Using Linked List in DSA Go

Mental Model

A dequeue lets you add or remove items from both ends quickly using a linked list.

Analogy: Imagine a line of people where you can add or remove someone from the front or the back easily.

front -> [node1] -> [node2] -> [node3] -> back -> null

Dry Run Walkthrough

Input: Start with empty dequeue, then add 1 at front, add 2 at back, remove from front, add 3 at front

Goal: Show how items are added and removed from both ends in a linked list dequeue

Step 1: Add 1 at front

front -> [1] -> back -> null

Why: First item becomes both front and back

Step 2: Add 2 at back

front -> [1] -> [2] -> back -> null

Why: Add new node after back to keep order

Step 3: Remove from front

front -> [2] -> back -> null

Why: Remove first node and update front pointer

Step 4: Add 3 at front

front -> [3] -> [2] -> back -> null

Why: Add new node before current front

Result:

front -> [3] -> [2] -> back -> null

Annotated Code

DSA Go

package main

import "fmt"

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

type Dequeue struct {
	front *Node
	back  *Node
}

func (dq *Dequeue) AddFront(val int) {
	newNode := &Node{value: val}
	if dq.front == nil {
		dq.front = newNode
		dq.back = newNode
		return
	}
	newNode.next = dq.front
	dq.front.prev = newNode
	dq.front = newNode
}

func (dq *Dequeue) AddBack(val int) {
	newNode := &Node{value: val}
	if dq.back == nil {
		dq.front = newNode
		dq.back = newNode
		return
	}
	dq.back.next = newNode
	newNode.prev = dq.back
	dq.back = newNode
}

func (dq *Dequeue) RemoveFront() (int, bool) {
	if dq.front == nil {
		return 0, false
	}
	val := dq.front.value
	if dq.front == dq.back {
		dq.front = nil
		dq.back = nil
	} else {
		dq.front = dq.front.next
		dq.front.prev = nil
	}
	return val, true
}

func (dq *Dequeue) RemoveBack() (int, bool) {
	if dq.back == nil {
		return 0, false
	}
	val := dq.back.value
	if dq.front == dq.back {
		dq.front = nil
		dq.back = nil
	} else {
		dq.back = dq.back.prev
		dq.back.next = nil
	}
	return val, true
}

func (dq *Dequeue) Print() {
	curr := dq.front
	for curr != nil {
		fmt.Printf("%d -> ", curr.value)
		curr = curr.next
	}
	fmt.Println("null")
}

func main() {
	dq := &Dequeue{}
	dq.AddFront(1)       // Step 1
	dq.AddBack(2)        // Step 2
	val, ok := dq.RemoveFront() // Step 3
	if ok {
		fmt.Printf("Removed from front: %d\n", val)
	}
	dq.AddFront(3)       // Step 4
	dq.Print()
}

if dq.front == nil { dq.front = newNode; dq.back = newNode; return }

handle empty dequeue by setting front and back to new node

newNode.next = dq.front; dq.front.prev = newNode; dq.front = newNode

insert new node before current front and update front pointer

if dq.back == nil { dq.front = newNode; dq.back = newNode; return }

handle empty dequeue by setting front and back to new node

dq.back.next = newNode; newNode.prev = dq.back; dq.back = newNode

insert new node after current back and update back pointer

if dq.front == nil { return 0, false }

check if dequeue is empty before removing front

if dq.front == dq.back { dq.front = nil; dq.back = nil } else { dq.front = dq.front.next; dq.front.prev = nil }

remove front node and update pointers accordingly

if dq.back == nil { return 0, false }

check if dequeue is empty before removing back

if dq.front == dq.back { dq.front = nil; dq.back = nil } else { dq.back = dq.back.prev; dq.back.next = nil }

remove back node and update pointers accordingly

Output

Removed from front: 1

3 -> 2 -> null

Complexity Analysis

Time: O(1) for all add and remove operations because we update pointers directly without traversal

Space: O(n) because each element is stored in a node linked by pointers

vs Alternative: Compared to array-based dequeue, linked list avoids shifting elements on add/remove at front, making operations faster

Edge Cases

Empty dequeue when removing

RemoveFront and RemoveBack return false and zero value without error

DSA Go

if dq.front == nil { return 0, false }

Single element dequeue when removing

Both front and back pointers set to nil after removal

DSA Go

if dq.front == dq.back { dq.front = nil; dq.back = nil }

When to Use This Pattern

When you need to add or remove items from both ends efficiently, use a dequeue with a doubly linked list to get O(1) operations.

Common Mistakes

Mistake: Not updating both front and back pointers when dequeue becomes empty
Fix: Set both front and back to nil when last element is removed

Mistake: Forgetting to update prev or next pointers when adding/removing nodes
Fix: Always update both next and prev pointers to maintain list integrity

Summary

Implements a dequeue using a doubly linked list allowing fast add/remove at both ends.

Use when you want quick insertions and deletions from front and back without shifting elements.

The key is to keep track of front and back pointers and update next and prev links carefully.

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