Write the following using Java. Create a doubly linked list whose nodes contain

Question

Write the following using Java.

Create a doubly linked list whose nodes contain Strings. Your list should include the following methods:

• Insert a node in the list in alphabetical order

• Find a node that matches a String

• Traverse the list forwards and print

• Traverse the list backwards and print

• Delete a node from the list

• Delete/destroy the list

In addition to creating the class(es) for your linked list, you’ll need to create a main method that thoroughly tests each function you build to show that it works.

Explanation / Answer

import java.util.*;

class Node
{
private String value;
private Node back;
private Node next;

public String getValue(){
return value;
}
public Node getBack(){
   return back;
}
public Node getNext(){
   return next;
}
public void setValue(String val){
   value = val;
}
public void setBack(Node n){
   back = n;
}
public void setNext(Node n){
   next = n;
}
}

public class MyList
{
private Node front;
private Node last;
private int size;

MyList(){
   front = new Node();
   last = new Node();
front.setNext(last);
   last.setBack(front);
   size = 0;
}

public int getSize(){
   return size;
}

public Node getFront(){
   return front;
}

public Node getLast(){
   return last;
}
  
public void insert(String str){
   Node n = new Node();
   n.setValue(str);
   if(size == 0){
       front.setNext(n);
       n.setBack(front);
       n.setNext(last);
       last.setBack(n);
   }
   else{
       Node temp1 = front;
   Node temp2 = front.getNext();

       while(temp2 != last){
           int ret = temp2.getValue().compareTo(str);
           if( ret > 0){
               break;
           }
           else if(ret < 0 ){
               temp1 = temp2;
               temp2 = temp2.getNext();
           }
           else
               return;
       }
       temp1.setNext(n);
       n.setNext(temp2);
   n.setBack(temp1);
       temp2.setBack(n);
   }
   size++;
}

public Node search(String key){
Node temp = front.getNext();
   int i = 1;
if(size == 0){
       System.out.println("No such element found");
       return null;
   }
   while(temp != last){
if(temp.getValue().equals(key)){
       System.out.println("String " + key + " found at position : " + i);
       return temp;
}
   i++;
   temp = temp.getNext();
}
   System.out.println("No such element found");
   return null;
}

public void printForward(){
Node temp = front.getNext();
while(temp != last){
       System.out.print(temp.getValue() + " ");
       temp = temp.getNext();
   }
   System.out.println("");
}

public void printBackward(){
Node temp = last.getBack();
while(temp != front){
       System.out.print(temp.getValue() + " ");
       temp = temp.getBack();
   }
   System.out.println("");
}

public void deleteNode(String key){
   Node n = search(key);
   if(n == null){
       System.out.println("No such string present in the list");
       return;
}
   Node temp = n.getBack();
   temp.setNext(n.getNext());
   n.getNext().setBack(temp);
   System.out.println("Node <" + key +"> deleted");
}

public void destroyList(){
   Node temp = front.getNext();
   Node temp2;
   while(temp != last){
       temp2 = temp;
       temp = temp.getNext();
       temp2.setBack(null);
       temp2.setNext(null);
   }
   front.setNext(last);
   last.setBack(front);
}

public static void main(String []args){
   MyList list = new MyList();
   list.insert("Dbc");
   list.insert("Abs");
   list.insert("Kmo");
   list.insert("Elf");

   list.printForward();
   list.printBackward();
list.deleteNode("Elf");
   list.printForward();
   list.printBackward();
list.deleteNode("Abs");
   list.printForward();
   list.printBackward();
list.deleteNode("Abs");

   list.destroyList();
   list.printForward();
   list.printBackward();
}

}

Related Questions

Navigate

• Browse (All)
• Browse W
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.