Double Linked List

Assignment 


  1. In this assignment, create a double linked list using classes. Somecharacteristics of the Linked List are –
    i. Insert in a sorted manner.
    Eg: If your Linked List is
    1 2 4 5
    If you want insert 3 it will be inserted as –
    1 2 3 4 5
    ii. A deletion causes an inversion. EG: If you delete 3 it becomes5 4 2 1 . Then any insertion will be in sorted descendingorder.
    iii. Solve the reverse of a linked list with a recursion method without anextra linked list.
    iv. Provide a search method that will return the searched element.

THE LINKED LIST IS TO BE CREATED WITH CLASSES.

  1. Construct a circular queue.

Operations on Circular Queue:
● Front: Get the front item from queue.
● Rear: Get the last item from queue.
● enQueue(value) This function is used to insert an element into thecircular queue. In a circular queue, the new element is always inserted atRear position.
■Steps:
◆Create a new node dynamically and insert value into it.
◆Check if front==NULL, if it is true then front = rear = (newlycreated node)
◆If it is false then rare=(newly created node) and rear node alwayscontains the address of the front node.
● deQueue() This function is used to delete an element from the circularqueue. In a queue, the element is always deleted from front position.
■Steps:
◆Check whether queue is empty or not means front == NULL.
◆If it is empty then display Queue is empty. If queue is not emptythen perform next step
◆Check if (front==rear) if it is true then set front = rear = NULL elsemove the front forward in queue, update address of front in rearnode and return the element.

THE CIRCULAR QUEUE IS TO BE CREATED WITH CLASSES.

  1. Show the workout for the following and explain each step:
    i. Insert in the following order
    19 , 17, 15, 13 , 12, 5, 3 , 1, 7, 9
    ii. Delete 15.
    iii. Show the inorder, preorder and postorder traversal.
    iv. Balance the AVL tree.
    4. Follow the uploaded code and slides for Binary tree insertion. Add a methodAVLRotation to balance an unbalanced tree.

 

 

Message:

 

This assignment is to be written in the Java programming language.

Here is the “uploaded trees code” to work off of for question 4:

// Java program to demonstrate insert operation in binary search tree
class BinarySearchTree {

/* Class containing left and right child of current node and key value*/

private class Node {
int key;
Node left, right;

public Node(int item) {
key = item;
left = right = null;
}
}

// Root of BST
private Node root;

// Constructor
public BinarySearchTree() {
root = null;
}

// This method mainly calls insertRec()
public void insert(int key) {
root = insertRec(root, key);
}

/* A recursive function to insert a new key in BST */
public Node insertRec(Node root, int key) {

/* If the tree is empty, return a new node */
if (root == null) {
root = new Node(key);
return root;
}

/* Otherwise, recur down the tree */
if (key <= root.key)
root.left = insertRec(root.left, key);
else if (key >root.key)
root.right = insertRec(root.right, key);

/* return the (unchanged) node pointer */
return root;
}

// This method mainly calls InorderRec()
public void inorder()  {
inorderRec(root);
}

public void preorder()  {
preorderRec(root);
}

public void postorder()  {
postorderRec(root);
}
// A utility function to do inorder traversal of BST
public void inorderRec(Node root) {
if (root != null) {
inorderRec(root.left);
System.out.print(root.key + ” “);
inorderRec(root.right);
}
}

public void preorderRec(Node root) {
if (root != null) {

System.out.print(root.key+ ” “);
preorderRec(root.left);
preorderRec(root.right);
}
}

public void postorderRec(Node root) {
if (root != null) {

postorderRec(root.left);
postorderRec(root.right);
System.out.print(root.key+ ” “);
}
}

private  intminValue(Node root)
{
intminv = root.key;
while (root.left != null)
{
minv = root.left.key;
root = root.left;
}
return minv;
}
public void deleteKey(int key)
{
root = deleteRec(root, key);
}

/* A recursive function to insert a new key in BST */
public Node deleteRec(Node root, int key)
{
Node curr = root;
/* Base Case: If the tree is empty */
if (curr == null)  return curr;

/* Otherwise, recur down the tree */
if (key <curr.key)
curr.left = deleteRec(curr.left, key);
else if (key >curr.key)
curr.right = deleteRec(curr.right, key);

// if key is same as root’s key, then This is the node
// to be deleted
else
{
// node with only one child or no child
if (curr.left == null)
return curr.right;
else if (curr.right == null)
return curr.left;

// node with two children: Get the inorder successor (smallest
// in the right subtree)
curr.key = minValue(curr.right);

// Delete the inorder successor
curr.right = deleteRec(curr.right, curr.key);
}

return curr;
}

}

public class TreesMain{
/* Let us create following BST
50
/     \
30      70
/  \    /  \
20   40  60   80 */

public static void main(String args[]){
int[] arr = new int[]{80, 70 , 50 , 30 , 20, 10 ,40 , 25, 35, 37};

BinarySearchTree tree = new BinarySearchTree();
for (int i = 0 ;i <arr.length; i++)
{

tree.insert(arr[i]);
}

// print inorder traversal of the BST
System.out.println(“\nInorder: “);
tree.inorder();

System.out.println(“\nPreorder: “);
tree.preorder();

System.out.println(“\nPostorder: “);
tree.postorder();

System.out.println();

System.out.println(“\nDelete 30”);
tree.deleteKey(30);
System.out.println(“Inorder traversal of the modified tree”);
tree.inorder();

}
}

Question 3 can be written out and attached separately.

 

 

 

Solution

 

 

CircularQueue.java

 

public class CircularQueue {

 

class Node{

int data;

Node next;

 

Node(int d) {

data = d;

}

}

 

Node front;

Node rear;

 

public void printQueue(){

Node temp=front;

System.out.println(“Circular Queue:”);

while(temp.next!=front){

System.out.print(temp.data+” “);

temp=temp.next;

}

System.out.print(temp.data);

System.out.println(“”);

}

 

public void enQueue(int number){

Node temp=new Node(number);

if (front == null) {

front=temp;

}

else{

rear.next=temp;

}

rear=temp;

rear.next=front;

}

 

publicintdeQueue(){

intdequed_element;

if(front==null) {

System.out.println(“Empty Queue”);

return -1;

}

if(front.equals(rear)){

dequed_element=front.data;

front=null;

rear=null;

}

else{

Node temp=front;

rear.next=front.next;

front=rear.next;

dequed_element=temp.data;

}

returndequed_element;

}

 

public static void main(String args[]){

CircularQueue q=new CircularQueue();

q.deQueue();

q.enQueue(12);

q.enQueue(7);

q.enQueue(13);

q.deQueue();

q.enQueue(11);

q.printQueue();

q.deQueue();

System.out.println(“After Dequeue”);

q.printQueue();

}

}

 

 

DoubleLinkedList.java

 

public class DoubleLinkedList {

Node head; // head of list

int z;

/* Doubly Linked list Node*/

class Node

{

int data;

Node prev;

Node next;

Node(int d){data=d;}

}

DoubleLinkedList(int d){

head=new Node(d);

z=1;

}

 

public void insert(intnum){

Node v=head;

while(v!=null) {

if(num*z>v.data*z){

if(v.next!=null)

v=v.next;

else {

InsertAfter(v, num);

return;

}

}

else{

if(v.prev==null){

Node new_node = new Node(num);

new_node.next=v;

v.prev=new_node;

head=v.prev;

return;

}

else {

InsertAfter(v.prev, num);

return;

}

}

}

}

voiddeleteNode(Node node) {

if (head == null || node == null) {

return;

}

if (head == node) {

head = node.next;

}

if (node.next != null) {

node.next.prev = node.prev;

}

if (node.prev != null) {

node.prev.next = node.next;

}

reverse(head);

z=z*-1;

return;

}

 

//recursive reverse method

void reverse(Node current) {

Node temp;

if(current!=null) {

temp = current.prev;

current.prev = current.next;

current.next = temp;

if (current.prev!=null) {

current = current.prev;

reverse(current);

} else {

head = temp.prev;

return;

}

}

}

 

public void InsertAfter(Node prev_Node,intnew_data)

{

if(prev_Node == null)

{

 

}

Node new_node = new Node(new_data);

new_node.next = prev_Node.next;

prev_Node.next = new_node;

new_node.prev = prev_Node;

if(new_node.next != null)

new_node.next.prev = new_node;

}

//search method

public Node search(intnum){

Node current=head;

while(current!=null){

if(current.data==num){

return current;

}

else if(current.data*z>num*z){

return null;

}

current=current.next;

}

return null;

}

 

public void printlist(Node node)

{

System.out.println(“Double Linkedlist:”);

while(node != null)

{

System.out.print(node.data + ” “);

node = node.next;

}

System.out.println(“”);

}

 

public static void main(String args[]){

DoubleLinkedListdouble_list=new DoubleLinkedList(5);

double_list.insert(7);

double_list.insert(3);

double_list.insert(1);

double_list.insert(4);

double_list.insert(8);

double_list.printlist(double_list.head);

 

//search Node 4

Node node_to_be_deleted=double_list.search(4);

//delete Node with value 4

double_list.deleteNode(node_to_be_deleted);

 

System.out.println(“After Deleting 4:”);

double_list.printlist(double_list.head);

//System.out.println(double_list.search(3).data);

System.out.println(“Insert number 6”);

double_list.insert(6);

double_list.printlist(double_list.head);

 

System.out.println(“After deleting number next to head”);

double_list.deleteNode(double_list.head.next);

//Again Reverses

double_list.printlist(double_list.head);

}

}

 

 

 

TreesMain.java

 

importjava.util.*;

classBinarySearchTree {

 

/* Class containing left and right child of current node and key value*/

public class Node {

int key;

Node left, right;

 

public Node(int item) {

key = item;

left = right = null;

}

}

 

// Root of BST

Node root;

 

// Constructor

publicBinarySearchTree() {

root = null;

}

 

//creates an pre order arraylist

ArrayList<Node>create_inorder_list(Node root,ArrayList<Node> list)

{

// Base case

if (root == null)

return list;

create_inorder_list(root.left, list);

list.add(root);

create_inorder_list(root.right, list);

return list;

}

 

// Recursive Function to create tree

Node BalancedTree(ArrayList<Node> list, int start,

int end)

{

if (start > end)

return null;

int mid = (start + end) / 2;

Node temp = list.get(mid);

temp.left = BalancedTree(list, start, mid – 1);

temp.right = BalancedTree(list, mid + 1, end);

return temp;

}

 

// unbalanced to Balanced BST

Node AVLRotation(Node root)

{

ArrayList<Node>inorder_list=new ArrayList<Node>();

ArrayList<Node>ordered_list=create_inorder_list(root,inorder_list);

int n = ordered_list.size();

returnBalancedTree(ordered_list, 0, n – 1);

}

 

 

// This method mainly calls insertRec()

public void insert(int key) {

root = insertRec(root, key);

}

 

/* A recursive function to insert a new key in BST */

public Node insertRec(Node root, int key) {

 

/* If the tree is empty, return a new node */

if (root == null) {

root = new Node(key);

return root;

}

 

/* Otherwise, recur down the tree */

if (key <= root.key)

root.left = insertRec(root.left, key);

else if (key >root.key)

root.right = insertRec(root.right, key);

 

/* return the (unchanged) node pointer */

return root;

}

 

// This method mainly calls InorderRec()

public void inorder()  {

inorderRec(root);

}

public void preorder()  {

preorderRec(root);

}

 

public void postorder()  {

postorderRec(root);

}

// A utility function to do inorder traversal of BST

public void inorderRec(Node root) {

if (root != null) {

inorderRec(root.left);

System.out.print(root.key + ” “);

inorderRec(root.right);

}

}

 

public void preorderRec(Node root) {

if (root != null) {

 

System.out.print(root.key+ ” “);

preorderRec(root.left);

preorderRec(root.right);

}

}

 

 

public void postorderRec(Node root) {

if (root != null) {

postorderRec(root.left);

postorderRec(root.right);

System.out.print(root.key+ ” “);

}

}

 

private  intminValue(Node root)

{

intminv = root.key;

while (root.left != null)

{

minv = root.left.key;

root = root.left;

}

returnminv;

}

public void deleteKey(int key)

{

root = deleteRec(root, key);

}

 

/* A recursive function to delete a key in BST */

public Node deleteRec(Node root, int key)

{

Node curr = root;

/* Base Case: If the tree is empty */

if (curr == null)  return curr;

 

/* Otherwise, recur down the tree */

if (key <curr.key)

curr.left = deleteRec(curr.left, key);

else if (key >curr.key)

curr.right = deleteRec(curr.right, key);

 

// if key is same as root’s key, then This is the node

// to be deleted

else

{

// node with only one child or no child

if (curr.left == null)

returncurr.right;

else if (curr.right == null)

returncurr.left;

// node with two children: Get the inorder successor (smallest

// in the right subtree)

curr.key = minValue(curr.right);

// Delete the inorder successor

curr.right = deleteRec(curr.right, curr.key);

}

returncurr;

}

 

}

 

public class TreesMain{

/* Let us create following BST

50

/     \

30      70

/  \    /  \

20   40  60   80 */

 

public static void main(String args[]){

int[] arr = new int[]{19 , 17, 15, 13 , 12, 5, 3 , 1, 7, 9};

 

BinarySearchTree tree = new BinarySearchTree();

for (int i = 0 ;i <arr.length; i++)

{

 

tree.insert(arr[i]);

}

 

 

// print inorder traversal of the BST

System.out.println(“\nInorder: “);

tree.inorder();

 

System.out.println(“\nPreorder: “);

tree.preorder();

 

 

System.out.println(“\nPostorder: “);

tree.postorder();

 

System.out.println();

 

System.out.println(“\nAfter Deleting 15”);

tree.deleteKey(15);

System.out.println(“\nInorder: “);

tree.inorder();

 

System.out.println(“\nPreorder: “);

tree.preorder();

 

 

System.out.println(“\nPostorder: “);

tree.postorder();

 

System.out.println();

System.out.println(“\nAfter Balancing”);

tree.root = tree.AVLRotation(tree.root);

System.out.println(“root key:”+tree.root.key);  //After Rotation

System.out.println(“\nInorder: “);

tree.inorder();

 

System.out.println(“\nPreorder: “);

tree.preorder();

 

System.out.println(“\nPostorder: “);

tree.postorder();

 

}

}