Dequeue Using Linked List in DSA Python - 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 efficient insertion and deletion at both ends without shifting elements, making it ideal for Dequeue operations.

beginner

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

The main operations are: insert_front, insert_rear, delete_front, delete_rear, and display.

intermediate

How does delete_rear operation work in a linked list based Dequeue?

It removes the last node by traversing to the second last node and updating its next pointer to None, then freeing the last node.

intermediate

What is the time complexity of insert_front and delete_front in a linked list Dequeue?

Both insert_front and delete_front operations take O(1) time because they directly add or remove the first node.

Which operation is NOT supported by a Dequeue?

A Insert in the middle

B Delete from rear

C Delete from front

D Insert at front

Dequeue supports insertion and deletion only at the front and rear ends, not in the middle.

What is the advantage of using a linked list for Dequeue over an array?

A Uses less memory always

B Faster random access

C Fixed size

D Dynamic size and no shifting needed

Linked lists allow dynamic size and efficient insertions/deletions at both ends without shifting elements.

What happens when you delete the rear element in a singly linked list Dequeue?

A You must traverse to the second last node first

B You can directly remove the last node

C You remove the first node

D You cannot delete rear in singly linked list

To delete the rear node, you must find the second last node to update its next pointer to None.

What is the time complexity of deleting the rear node in a singly linked list Dequeue?

A O(1)

B O(n)

C O(log n)

D O(n log n)

Deleting the rear node requires traversal to the second last node, which takes O(n) time.

Which pointer is updated when inserting a node at the front of a linked list Dequeue?

A Rear pointer

B Next pointer of last node

C Next pointer of new node

D Previous pointer of new node

The new node's next pointer is set to the current front node, then front pointer is updated to new node.

Explain how insertion at the rear end works in a linked list based Dequeue.

Think about how to add a node at the end of a linked list.

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

Focus on removing the first node safely.