Please write in Java and include explanation and a run test. 1. Linked Lists – D
ID: 3757212 • Letter: P
Question
Please write in Java and include explanation and a run test.
1. Linked Lists – Deque (Double-ended queue) Implement a nested class DoubleNode for building doubly-linked lists, where each node contains a reference to the item preceding it and the item following it in the list (null if there is no such item). Then implement methods for the following tasks: • Insert at the beginning • Insert at the end • Remove from the beginning • Remove from the end • Insert before a give node • Insert after a given node • Remove a given node • Move to front (move an object to the front) • Move to end (moved and object to the end)
Explanation / Answer
package DS;
// Defines a class Node
class Node
{
// Instance variable to store data
int data;
// Link to next and previous
Node prev, next;
// static method to create a new node and returns it
static Node createNode(int data)
{
// Dynamically creates a node using default constructor
Node newNode = new Node();
// Assigns data
newNode.data = data;
// Sets next and previous link is null
newNode.prev = newNode.next = null;
// Returns the new node
return newNode;
} // End of method
}// End of class Node
// Defines a class Deque
class Deque
{
// Declares objects for front and rear end
Node front;
Node rear;
// To store the size
int Size;
// Default constructor to initialize instance variables
Deque()
{
front = rear = null;
Size = 0;
} // End of method
// Method to insert an element at front end
void insertFront(int data)
{
// Calls the method to create a node and stores the return object
Node newNode = Node.createNode(data);
// Checks if newNode is null then new element cannot be added and it is an 'Overflow' condition
if (newNode == null)
System.out.println("OverFlow ");
// Otherwise can insert node
else
{
// Checks if deque is empty
if (front == null)
// Set the rear and front to new node as first node
rear = front = newNode;
// Otherwise at least one node is available. Inserts node at the front end
else
{
// Assigns front to new node next
newNode.next = front;
// Assigns new node to front previous
front.prev = newNode;
// Assigns new node to front
front = newNode;
} // End of else
// Increase the size by one
Size++;
} // End of outer else
}// End of method
// Method to insert an element at rear end
void insertRear(int data)
{
// Calls the method to create a node and stores the return object
Node newNode = Node.createNode(data);
// Checks if newNode is null then new element cannot be added and it is an 'Overflow' condition
if (newNode == null)
System.out.println("OverFlow ");
// Otherwise can insert node
else
{
// Checks if deque is empty
if (rear == null)
front = rear = newNode;
// Otherwise at least one node is available. Inserts node at the rear end
else
{
// New node previous link is pointing to rear
newNode.prev = rear;
// Rear next is pointing to new node
rear.next = newNode;
// Rear is pointing to new node
rear = newNode;
} // End of else
// Increase the size by one
Size++;
} // End of outer else
}// End of method
// Method to delete a node from front end
void deleteFront()
{
// Checks if deque is empty then 'Underflow' condition
if (isEmpty())
System.out.println("UnderFlow ");
// Otherwise deletes the node from the front end and makes the adjustment in the links
else
{
// Creates a temporary node and assigns front to it
Node temp = front;
// Front is pointing to front next
front = front.next;
// Checks if only one element was present set the rear to null
if (front == null)
rear = null;
// Otherwise at least one node is available
else
// Assigns null to front previous link
front.prev = null;
// Decrease the size by one
Size--;
} // End of else
}// End of method
// Method to delete a node from rear end
void deleteRear()
{
// Checks if deque is empty then 'Underflow' condition
if (isEmpty())
System.out.println("UnderFlow ");
// Otherwise deletes the node from the rear end and makes the adjustment in the links
else
{
// Creates a temporary node and assigns front to it
Node temp = rear;
// Rear is pointing to rear previous node
rear = rear.prev;
// Checks if only one element is present set the front to null
if (rear == null)
front = null;
// Otherwise at least one node is available
else
// Set rear next to null
rear.next = null;
// Decrease the size by one
Size--;
} // End of else
}// End of method
// Method to return the front element
int getFront()
{
// Checks if deque is empty, then returns -1
if (isEmpty())
return -1;
// Otherwise returns the front element
return front.data;
}// End of method
// Method to return the rear element
int getRear()
{
// Checks if deque is empty, then returns -1
if (isEmpty())
return -1;
// Otherwise returns the rear element
return rear.data;
}// End of method
// Method to return current size
int size()
{
return Size;
}// End of method.
// Method to return true if Deque is empty
boolean isEmpty()
{
return (front == null);
}// End of method
// Method to display the Deque
void display()
{
// Creates a temporary node and assigns front to it
Node temp = front;
// Loops till end
while (temp != null)
{
// Displays data
System.out.print(temp.data + ", ");
// Move next
temp = temp.next;
}// End of while loop
System.out.println();
} // End of method
}; // End of class Deque
// Driver class DLLDoubleEndedQueue definition
public class DLLDoubleEndedQueue
{
// main method definition
public static void main(String[] args)
{
// Creates an object of the class Deque
Deque dq = new Deque();
System.out.println(" Insert element 10 - 15 at rear end ");
for(int x = 0; x <= 5; x++)
dq.insertRear(x + 10);
dq.display();
System.out.printf(" Rear end element: %d", dq.getRear());
dq.deleteRear();
System.out.printf(" After deleting rear element new rear is: %d", dq.getRear());
System.out.printf(" Inserting element '25' at front end ");
dq.insertFront(25);
dq.display();
System.out.printf(" Front end element: %d", dq.getFront());
System.out.printf(" Number of elements in Deque: %d", dq.size());
dq.deleteFront();
System.out.printf(" After deleting front element new front is: %d ", dq.getFront());
dq.display();
}// End of main method
}// End of driver class DLLDoubleEndedQueue
Sample Output:
Insert element 10 - 15 at rear end
10, 11, 12, 13, 14, 15,
Rear end element: 15
After deleting rear element new rear is: 14
Inserting element '25' at front end
25, 10, 11, 12, 13, 14,
Front end element: 25
Number of elements in Deque: 6
After deleting front element new front is: 10
10, 11, 12, 13, 14,