Dequeue Using Linked List in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Dequeue Operations on Linked List

What is the printed state of the dequeue after these operations?

Operations:
1. EnqueueFront(10)
2. EnqueueRear(20)
3. EnqueueFront(5)
4. DequeueRear()
5. EnqueueRear(15)

Print the dequeue from front to rear.

DSA Go

package main
import "fmt"

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

type Dequeue struct {
    front *Node
    rear  *Node
}

func (dq *Dequeue) EnqueueFront(val int) {
    newNode := &Node{data: val}
    if dq.front == nil {
        dq.front = newNode
        dq.rear = newNode
    } else {
        newNode.next = dq.front
        dq.front.prev = newNode
        dq.front = newNode
    }
}

func (dq *Dequeue) EnqueueRear(val int) {
    newNode := &Node{data: val}
    if dq.rear == nil {
        dq.front = newNode
        dq.rear = newNode
    } else {
        dq.rear.next = newNode
        newNode.prev = dq.rear
        dq.rear = newNode
    }
}

func (dq *Dequeue) DequeueFront() int {
    if dq.front == nil {
        return -1
    }
    val := dq.front.data
    dq.front = dq.front.next
    if dq.front != nil {
        dq.front.prev = nil
    } else {
        dq.rear = nil
    }
    return val
}

func (dq *Dequeue) DequeueRear() int {
    if dq.rear == nil {
        return -1
    }
    val := dq.rear.data
    dq.rear = dq.rear.prev
    if dq.rear != nil {
        dq.rear.next = nil
    } else {
        dq.front = nil
    }
    return val
}

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

func main() {
    dq := &Dequeue{}
    dq.EnqueueFront(10)
    dq.EnqueueRear(20)
    dq.EnqueueFront(5)
    dq.DequeueRear()
    dq.EnqueueRear(15)
    dq.Print()
}

A 5 -> 10 -> 15 -> null

B 10 -> 5 -> 15 -> null

C 5 -> 10 -> 20 -> 15 -> null

D 10 -> 15 -> null

💡 Hint

Trace each operation step-by-step and update the front and rear pointers carefully.

After the operations, the dequeue contains 5 at front, then 10, then 15 at rear. The DequeueRear removed 20 before adding 15 at rear.

🧠 Conceptual

intermediate

Understanding Dequeue Front and Rear Pointers

In a dequeue implemented using a doubly linked list, which statement is TRUE about the front and rear pointers after removing the last element?

A Both front and rear pointers become nil (empty dequeue).

B Only front pointer becomes nil; rear remains pointing to the last node.

C Only rear pointer becomes nil; front remains pointing to the last node.

D Both pointers remain unchanged pointing to the removed node.

💡 Hint

Think about what happens when the last node is removed from the dequeue.

When the last element is removed, the dequeue becomes empty, so both front and rear pointers must be set to nil to indicate emptiness.

🔧 Debug

advanced

Identify the Bug in Dequeue Rear Removal

What error will occur when running this DequeueRear method if the dequeue has only one element?

DSA Go

func (dq *Dequeue) DequeueRear() int {
    if dq.rear == nil {
        return -1
    }
    val := dq.rear.data
    dq.rear = dq.rear.prev
    dq.rear.next = nil
    return val
}

A No error; returns the correct value

B runtime error: invalid memory address or nil pointer dereference

C Compilation error: dq.rear.next undefined

D Returns -1 even if element exists

💡 Hint

Consider what happens when dq.rear.prev is nil and you try to access dq.rear.next.

If the dequeue has one element, after dq.rear = dq.rear.prev, dq.rear becomes nil. Accessing dq.rear.next causes a nil pointer dereference runtime error.

📝 Syntax

advanced

Correct Syntax for EnqueueFront Method

Which option correctly implements the EnqueueFront method for a dequeue using a doubly linked list in Go?

A

func (dq *Dequeue) EnqueueFront(val int) {
    newNode := Node{data: val}
    if dq.front == nil {
        dq.front = &newNode
        dq.rear = &newNode
    } else {
        newNode.next = dq.front
        dq.front.prev = &newNode
        dq.front = &newNode
    }
}

B

func (dq *Dequeue) EnqueueFront(val int) {
    newNode := &Node{data: val}
    if dq.front == nil {
        dq.front = newNode
    } else {
        newNode.next = dq.front
        dq.front.prev = newNode
        dq.front = newNode
    }
}

C

func (dq *Dequeue) EnqueueFront(val int) {
    newNode := &Node{data: val}
    if dq.front == nil {
        dq.front = newNode
        dq.rear = newNode
    } else {
        newNode.next = dq.front
        dq.front.prev = newNode
        dq.front = newNode
    }
}

D

func (dq *Dequeue) EnqueueFront(val int) {
    newNode := &Node{val}
    if dq.front == nil {
        dq.front = newNode
        dq.rear = newNode
    } else {
        newNode.next = dq.front
        dq.front.prev = newNode
        dq.front = newNode
    }
}

💡 Hint

Check struct initialization and pointer usage carefully.

Option C correctly initializes newNode as a pointer with data field set, and updates front and rear pointers properly. Option C uses a local variable whose address may be unsafe. Option C has wrong struct initialization syntax. Option C misses setting rear when dequeue is empty.

🚀 Application

expert

Resulting Dequeue State After Mixed Operations

Given an empty dequeue implemented with a doubly linked list, perform these operations in order:
EnqueueRear(1), EnqueueRear(2), EnqueueFront(0), DequeueFront(), EnqueueRear(3), DequeueRear(), EnqueueFront(-1)

What is the printed state of the dequeue from front to rear?

DSA Go

package main
import "fmt"

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

type Dequeue struct {
    front *Node
    rear  *Node
}

func (dq *Dequeue) EnqueueFront(val int) {
    newNode := &Node{data: val}
    if dq.front == nil {
        dq.front = newNode
        dq.rear = newNode
    } else {
        newNode.next = dq.front
        dq.front.prev = newNode
        dq.front = newNode
    }
}

func (dq *Dequeue) EnqueueRear(val int) {
    newNode := &Node{data: val}
    if dq.rear == nil {
        dq.front = newNode
        dq.rear = newNode
    } else {
        dq.rear.next = newNode
        newNode.prev = dq.rear
        dq.rear = newNode
    }
}

func (dq *Dequeue) DequeueFront() int {
    if dq.front == nil {
        return -1
    }
    val := dq.front.data
    dq.front = dq.front.next
    if dq.front != nil {
        dq.front.prev = nil
    } else {
        dq.rear = nil
    }
    return val
}

func (dq *Dequeue) DequeueRear() int {
    if dq.rear == nil {
        return -1
    }
    val := dq.rear.data
    dq.rear = dq.rear.prev
    if dq.rear != nil {
        dq.rear.next = nil
    } else {
        dq.front = nil
    }
    return val
}

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

func main() {
    dq := &Dequeue{}
    dq.EnqueueRear(1)
    dq.EnqueueRear(2)
    dq.EnqueueFront(0)
    dq.DequeueFront()
    dq.EnqueueRear(3)
    dq.DequeueRear()
    dq.EnqueueFront(-1)
    dq.Print()
}

A 1 -> 2 -> 3 -> null

B 0 -> 1 -> 3 -> null

C -1 -> 1 -> null

D -1 -> 1 -> 2 -> null

💡 Hint

Perform each operation carefully and update front and rear pointers after each step.

After all operations, the dequeue contains -1 at front, then 1, then 2 at rear.

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