Deque or Double Ended Queue is a generalized version of Queue data structure that allows insert and delete at both ends. In previous post Implementation of Deque using circular array has been discussed. Now in this post we see how we implement Deque using Doubly Linked List.
Operations on Deque :
Mainly the following four basic operations are performed on queue :
insertFront() : Adds an item at the front of Deque. insertRear() : Adds an item at the rear of Deque. deleteFront() : Deletes an item from front of Deque. deleteRear() : Deletes an item from rear of Deque.
In addition to above operations, following operations are also supported :
getFront() : Gets the front item from queue. getRear() : Gets the last item from queue. isEmpty() : Checks whether Deque is empty or not. size() : Gets number of elements in Deque. erase() : Deletes all the elements from Deque.
Doubly Linked List Representation of Deque :
For implementing deque, we need to keep track of two pointers, front and rear. We enqueue (push) an item at the rear or the front end of deque and dequeue(pop) an item from both rear and front end.
Declare two pointers front and rear of type Node, where Node represents the structure of a node of a doubly linked list. Initialize both of them with value NULL.
Insertion at Front end :
1. Allocate space for a newNode of doubly linked list. 2. IF newNode == NULL, then 3. print "Overflow" 4. ELSE 5. IF front == NULL, then 6. rear = front = newNode 7. ELSE 8. newNode->next = front 9. front->prev = newNode 10. front = newNode
Insertion at Rear end :
1. Allocate space for a newNode of doubly linked list. 2. IF newNode == NULL, then 3. print "Overflow" 4. ELSE 5. IF rear == NULL, then 6. front = rear = newNode 7. ELSE 8. newNode->prev = rear 9. rear->next = newNode 10. rear = newNode
Deletion from Front end :
1. IF front == NULL 2. print "Underflow" 3. ELSE 4. Initalize temp = front 5. front = front->next 6. IF front == NULL 7. rear = NULL 8. ELSE 9. front->prev = NULL 10 Deallocate space for temp
Deletion from Rear end :
1. IF front == NULL 2. print "Underflow" 3. ELSE 4. Initalize temp = rear 5. rear = rear->prev 6. IF rear == NULL 7. front = NULL 8. ELSE 9. rear->next = NULL 10 Deallocate space for temp
Insert element '5' at rear end Insert element '10' at rear end Rear end element: 10 After deleting rear element new rear is: 5 Inserting element '15' at front end Front end element: 15 Number of elements in Deque: 2 After deleting front element new front is: 5
Time Complexity : Time complexity of operations like insertFront(), insertRear(), deleteFront(), deleteRear()is O(1). Time Complexity of erase() is O(n).