Dequeue Using Linked List in DSA C - Cheat Sheet & Quick Revision

Recall & Review

beginner

What is a Dequeue (Double Ended Queue)?

A Dequeue is a data structure where elements can be added or removed from both the front and the rear ends.

beginner

Why use a linked list to implement a Dequeue?

A linked list allows dynamic memory allocation and efficient insertion and deletion at both ends without shifting elements.

beginner

What are the main operations in a Dequeue using linked list?

InsertFront, InsertRear, DeleteFront, DeleteRear, and Display.

intermediate

How does DeleteRear operation work in a singly linked list based Dequeue?

Traverse to the second last node, remove the last node, and update the second last node's next pointer to NULL.

intermediate

What is the time complexity of InsertFront and InsertRear in a linked list based Dequeue?

Both InsertFront and InsertRear operations take O(1) time if a tail pointer is maintained; otherwise, InsertRear takes O(n).

Which operation in a Dequeue adds an element at the front?

A InsertRear

B InsertFront

C DeleteRear

D DeleteFront

InsertFront adds an element at the front end of the Dequeue.

In a linked list based Dequeue, what is the pointer used to keep track of the last node?

A Previous pointer

B Head pointer

C Next pointer

D Tail pointer

The tail pointer keeps track of the last node for efficient rear operations.

What happens when you delete the front element in a Dequeue implemented with a linked list?

A The head pointer moves to the next node

B The tail pointer moves to the previous node

C The list is reversed

D The last node is removed

Deleting front means moving the head pointer to the next node and freeing the old front node.

Which of these is NOT a valid operation in a Dequeue?

A InsertMiddle

B DeleteRear

C DeleteFront

D InsertFront

InsertMiddle is not a standard Dequeue operation; Dequeue only allows insertion/removal at ends.

What is the worst-case time complexity of DeleteRear in a singly linked list without a tail pointer?

A O(1)

B O(log n)

C O(n)

D O(n^2)

Without a tail pointer, you must traverse the list to find the second last node, which takes O(n) time.

Explain how to insert an element at the rear end of a Dequeue implemented using a linked list.

Think about how to add a node at the end and update pointers.

Describe the steps to delete an element from the front of a Dequeue using a linked list.

Focus on removing the first node and updating the head.

Practice

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

easy

A. Dynamic size allows easy insertion and deletion at both ends

B. Faster access to elements by index

C. Uses less memory than arrays

D. Simpler to implement than arrays

Solution

1. Step 1: Understand linked list flexibility

   A linked list can grow or shrink dynamically without needing a fixed size.

2. Step 2: Compare with array limitations

   Arrays have fixed size and costly resizing; linked lists allow easy insertion/deletion at both ends.

3. Final Answer:

   Dynamic size allows easy insertion and deletion at both ends -> Option A

4. Quick Check:

   Linked list dynamic size = Advantage [OK]

Hint: Linked lists grow/shrink easily at ends [OK]

Common Mistakes:

• Confusing faster index access with linked list
• Thinking linked lists always use less memory
• Assuming arrays are simpler to implement

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

easy

A. struct Node { int data; struct Node* next; };

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

C. struct Node { int data; int next; int prev; };

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

Solution

1. Step 1: Identify node fields for dequeue

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

2. Step 2: Check pointer types

   Correct syntax uses pointers (struct Node*) for next and prev, not int or struct Node directly.

3. Final Answer:

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

4. Quick Check:

   Double linked node = data + next ptr + prev ptr [OK]

Hint: Double linked nodes need next and prev pointers [OK]

Common Mistakes:

• Using int instead of pointer for next/prev
• Missing prev pointer for dequeue
• Declaring next/prev as struct Node instead of pointer

3. Consider the following operations on an empty dequeue implemented using a linked list:
insertFront(10); insertRear(20); insertFront(5); deleteRear();
What will be the state of the dequeue from front to rear after these operations?

medium

A. 5 -> 10 -> null

B. 10 -> 5 -> null

C. 20 -> 10 -> null

D. 5 -> 20 -> null

Solution

1. Step 1: Perform insertFront(10) and insertRear(20)

   Dequeue: 10 (front) -> 20 (rear)

2. Step 2: Perform insertFront(5) and deleteRear()

   After insertFront(5): 5 -> 10 -> 20
   After deleteRear(): removes 20, so 5 -> 10

3. Final Answer:

   5 -> 10 -> null -> Option A

4. Quick Check:

   Front insert adds at front, rear delete removes last [OK]

Hint: Track front and rear changes stepwise [OK]

Common Mistakes:

• Confusing insertFront and insertRear order
• Forgetting to delete rear element
• Mixing up front and rear positions

4. The following C code snippet for deleting from the front of a dequeue has an error. What is the error?

void deleteFront() {
  if (front == NULL) {
    printf("Dequeue is empty\n");
    return;
  }
  struct Node* temp = front;
  front = front->next;
  if (front == NULL) {
    rear = NULL;
  }
  free(temp);
}

medium

A. Uses free() incorrectly

B. Does not check if dequeue is full

C. Does not update the prev pointer of new front node

D. Does not update rear pointer when dequeue becomes empty

Solution

1. Step 1: Analyze pointer updates after deletion

   After moving front to front->next, the new front's prev pointer still points to old node.

2. Step 2: Identify missing update

   Must set front->prev = NULL to maintain correct double link.

3. Final Answer:

   Does not update the prev pointer of new front node -> Option C

4. Quick Check:

   Update prev pointer after front deletion [OK]

Hint: Always reset prev of new front to NULL [OK]

Common Mistakes:

• Ignoring prev pointer update
• Checking dequeue full in delete function
• Not updating rear when empty (not shown here)

5. You want to implement a function to reverse a dequeue implemented using a doubly linked list. Which approach correctly reverses the dequeue?

hard

A. Only swap front and rear pointers without changing node links

B. Swap next and prev pointers of each node, then swap front and rear pointers

C. Delete all nodes and re-insert them from rear to front

D. Traverse from front to rear and copy data into a new list in reverse order

Solution

1. Step 1: Understand reversing a doubly linked list

   Reversing means each node's next and prev pointers must be swapped to reverse direction.

2. Step 2: Swap front and rear pointers

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

3. Final Answer:

   Swap next and prev pointers of each node, then swap front and rear pointers -> Option B

4. Quick Check:

   Swap links + swap ends = reverse dequeue [OK]

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

Common Mistakes:

• Only swapping front and rear pointers
• Rebuilding list instead of reversing links
• Copying data instead of changing pointers