Queue doubly linked list Java

TwitterFacebookLinkedInBufferRedditTumblr

Table of Contents

Nội dung chính Show

Problem Statement
insertFront(x)
insertEnd(x)
deleteFront()
deleteEnd()
Java code for Implementation of Deque using Doubly Linked List
C++ Code for Implementation of Deque using Doubly Linked List

Problem Statement
Example
Algorithm
- insertFront(x)
- insertEnd(x)
- deleteFront()
- deleteEnd()
- getFront()
- getEnd()
- isEmpty()
- size()
- erase()
Code
- Java code for Implementation of Deque using Doubly Linked List
- C++ Code for Implementation of Deque using Doubly Linked List

Problem Statement

The problem Implementation of Deque using Doubly Linked List states that you need to implement the following functions of Deque or Doubly Ended Queue using a doubly linked list,

insertFront(x) : Add element x at the starting of Deque
insertEnd(x) : Add element x at the end of Deque
deleteFront() : Delete an element from the starting of Deque
deleteEnd() : Delete an element from the end of Deque
getFront() : Return the element at the starting of Deque
getEnd() : Return the element at the end of Deque
isEmpty() : Returns whether the Deque is empty
size() : Return the size of Deque
erase() : Delete all the elements of Deque

Example

insertFront(5) insertEnd(10) insertEnd(11) insertFront(19) getFront() getEnd() deleteEnd() getEnd() deleteFront() getFront() size() isEmpty() erase() isEmpty()19 11 10 5 2 false true

Algorithm

To implement a Deque using a doubly linked list. We maintain two pointers front and rear, where front points to the front of a doubly linked list and rear points to the end. Also we need to maintain an integer size, that stores the number of nodes in the Deque.

To insert, delete, or get an element from starting we use the front pointer.

To insert, delete, or get an element from the end we use the rear pointer.

Implementation of Deque using Doubly Linked List Pin

insertFront(x)

To insert an element at the front of Deque, do the following

Create a new node with the required value and call it node.
If the front is null, make the front and rear equals node.
Else, insert the node before front and mark the node as a new front.
Increment size

insertEnd(x)

To insert an element at the end of Deque, do the following

Create a new node with required value and call it node.
If rear is null, make front and rear equals node.
Else, insert node after rear and mark the node as new rear.
Increment size

Time Complexity O(1)

Pseudo Code

Create a new node with required value and call it node if (rear == null) { front = rear = node } else { rear.next = node node.prev = rear rear = node } size++

deleteFront()

To delete an element from front of Deque, do the following

If front is null, there is no element to delete, simply return.
If front is equals to rear, there is only 1 node, make front and rear null.
Else, make front equals front.next and delete front.prev
Decrement size

Time Complexity = O(1)

Pseudo Code

if (front == null) { return } if (front == rear) { front = rear = null } else { temp = front front = front.next front.prev = null deallocate space for temp } size--

deleteEnd()

To delete an element from the end of Deque, do the following

If rear is null, there is no node to delete, simply return.
If rear is equals to front, there is only one node, make front and rear null.
Else make rear as rear.prev and delete rear.next.
Decrement size

Time Complexity = O(1)

Pseudo Code

if (rear == null) { return; } if (rear == front) { front = rear = null } else { temp = rear rear = rear.prev rear.next = null deallocate space for temp } size--

getFront()

The front element of the Deque is pointed by front, so if front is not null return front.data

getEnd()

The end element of Deque is pointed by rear, so if rear is not null return rear.data

Time Complexity = O(1)

Pseudo Code

if (rear != null) { return rear.data } return -1

isEmpty()

If the Deque is empty both front and rear will be null, so if front is null return true, else return false.

Time Complexity = O(1)

Pseudo Code

if (front == null) { return true } return false

size()

The size of the Deque is stored in the variable named size, so simply return size.

Time Complexity = O(1)

Pseudo Code

return size

erase()

Erasing Deque means deleting all the nodes of the Deque. To delete all the nodes do the following,

Set rear as null.
Create a temporary pointer temp, pointing to front.
Traverse in the Deque and repeat step 4, that is, while front is not null repeat step 4.
Set temp as front, front as front.next and deallocate space for temp.
Finally set temp as null and front as null and set size as 0.

Time Complexity = O(n),where n is the number of nodes in the Deque

Pseudo Code

rear = null Node temp = front while (front != null) { temp = front front.prev = null front = front.next deallocate space for temp } temp = front = null size = 0

Code

Java code for Implementation of Deque using Doubly Linked List

class DequeUsingDoublyLinkedList { // class representing Node of a doubly linked list static class Node { int data; Node next, prev; public Node(int data) { this.data = data; } } // front points to start of Deque and rear points to the end of Deque private static Node front = null; private static Node rear = null; private static int size = 0; private static void insertFront(int x) { // Create a new Node with required parameters Node node = new Node(x); if (front == null) { // This is the first node to be inserted front = rear = node; } else { // Add the node before front node.next = front; front.prev = node; // update front front = node; } // Increment size size++; } private static void insertEnd(int x) { // Create a new Node with required parameters Node node = new Node(x); if (rear == null) { // This is the first node to be inserted front = rear = node; } else { // Insert the node after rear rear.next = node; node.prev = rear; // update rear rear = node; } // Increment size size++; } private static void deleteFront() { if (front == null) { // no node to delete return; } if (front == rear) { // only 1 node is present front = rear = null; } else { // delete front and move front ahead front = front.next; front.prev = null; // Garbage Collector will automatically delete first node // as no pointer is pointing to it } // decrement size size--; } private static void deleteEnd() { if (rear == null) { // no node to delete return; } if (rear == front) { // only 1 node is present front = rear = null; } else { // delete rear and move rear backwards rear = rear.prev; rear.next = null; // Garbage Collector will automatically delete last node // as no pointer is pointing to it } // decrement size size--; } private static int getFront() { if (front != null) { // front points to first element in Deque, return its data return front.data; } // no node is present return -1; } private static int getEnd() { if (rear != null) { // rear points to last element in Deque, return its data return rear.data; } // no node is present return -1; } private static boolean isEmpty() { if (front == null) { return true; } return false; } private static int size() { return size; } private static void erase() { // mark rear as null rear = null; // traverse the doubly linked list while (front != null) { // delete all the prev pointers front.prev = null; front = front.next; } // After this deque looks like // a -> b -> c -> d ..., all the previous pointers are destroyed // No pointer is pointing to a, so Garbage collector will delete the whole Deque // set size as 0 size = 0; } public static void main(String[] args) { // Example insertFront(5); // 5 insertEnd(10); // 5 <-> 10 insertEnd(11); // 5 <-> 10 <-> 11 insertFront(19); // 19 <-> 5 <-> 10 <-> 11 System.out.println(getFront()); System.out.println(getEnd()); deleteEnd(); // 19 <-> 5 <-> 10 System.out.println(getEnd()); deleteFront(); // 5 <-> 10 System.out.println(getFront()); System.out.println(size()); System.out.println(isEmpty()); erase(); System.out.println(isEmpty()); } }19 11 10 5 2 false true

C++ Code for Implementation of Deque using Doubly Linked List

#include<bits/stdc++.h> using namespace std; // class representing a tree node class Node { public: int data; Node *next; Node *prev; Node(int d) { data = d; next = NULL; prev = NULL; } }; // function to create a new node Node* newNode(int x) { Node *node = new Node(x); return node; } // front points to start of Deque and rear points to the end of Deque Node *front = NULL; Node *rear = NULL; // Variable representing size of Deque int Size = 0; void insertFront(int x) { // Create a new Node with required parameters Node *node = newNode(x); if (front == NULL) { // This is the first node to be inserted front = rear = node; } else { // Add the node before front node->next = front; front->prev = node; // update front front = node; } // Increment size Size++; } void insertEnd(int x) { // Create a new Node with required parameters Node *node = newNode(x); if (rear == NULL) { // This is the first node to be inserted front = rear = node; } else { // Insert the node after rear node->prev = rear; rear->next = node; // update rear rear = node; } // Increment size Size++; } void deleteFront() { if (front == NULL) { // no node to delete return; } if (front == rear) { // only 1 node is present front = rear = NULL; } else { // delete front and move front ahead Node *temp = front; front = front->next; front->prev = NULL; // deallocate the memory taken by temp delete(temp); } // Decrement size Size--; } void deleteEnd() { if (rear == NULL) { // no node to delete return; } if (front == rear) { // only 1 node is present front = rear = NULL; } else { // delete rear and move rear backwards Node *temp = rear; rear = rear->prev; rear->next = NULL; // deallocate the memory taken by temp delete(temp); } // Decrement size Size--; } int getFront() { if (front != NULL) { return front->data; } return -1; } int getEnd() { if (rear != NULL) { return rear->data; } return -1; } int size() { return Size; } bool isEmpty() { if (front == NULL) { return true; } return false; } void erase() { // mark rear as null rear = NULL; // traverse the doubly linked list while (front != NULL) { Node *temp = front; // delete all the prev pointers front->prev = NULL; front = front->next; // Deallocate the memory taken by temp delete(temp); } // Set size as 0 Size = 0; } int main() { // Example insertFront(5); // 5 insertEnd(10); // 5 <-> 10 insertEnd(11); // 5 <-> 10 <-> 11 insertFront(19); // 19 <-> 5 <-> 10 <-> 11 cout<<getFront()<<endl; cout<<getEnd()<<endl; deleteEnd(); // 19 <-> 5 <-> 10 cout<<getEnd()<<endl; deleteFront(); // 5 <-> 10 cout<<getFront()<<endl; cout<<size()<<endl; if (isEmpty()) { cout<<"true"<<endl; } else { cout<<"false"<<endl; } erase(); if (isEmpty()) { cout<<"true"<<endl; } else { cout<<"false"<<endl; } return 0; }19 11 10 5 2 false true

TwitterFacebookLinkedInBufferRedditTumblr