Question

Using java:

Implement a basic doubly-linked list that implements a priority system sorting the elements that are inserted. Sort based on the speed of the warrior.

Driver code:

public class LinkedListDriver {
public static void main(String[] args) {
LinkedList list = new SortedDoublyLinkedList();

System.out.println(list);
Warrior krogg = new Warrior("Krogg", 30, 50, 200);
list.insert(krogg);

System.out.println(list);
Warrior gurkh = new Warrior("Gurkh", 40, 45, 180);
list.insert(gurkh);

System.out.println(list);
Warrior brynn = new Warrior("Brynn", 45, 40, 190);
list.insert(brynn);

System.out.println(list);
Warrior dolf = new Warrior("Dolf", 20, 65, 210);
list.insert(dolf);

System.out.println(list);
Warrior zuni = new Warrior("Zuni", 50, 35, 170);
list.insert(zuni);

System.out.println(list);
}
}

Warrior class:

public class Warrior {
private String name;
private int speed;
private int strength;
private int hp;
public Warrior(String name, int speed, int str, int hp) {
this.name = name;
this.speed = speed;
this.strength = str;
this.hp = hp;
}

public String getName() { return this.name; }
public int getSpeed() { return this.speed; }
public int getStrength() { return this.strength; }
public int getHp() { return this.hp; }

public String toString() { return this.name + "(" +
this.speed + ")"; }
}

Class that needs to be done:
interface LinkedList {
void insert(Warrior warrior);
String toString();
}

Expected output:
[ Zuni(50) Brynn(45) Gurkh(40) Krogg(30) Dolf(20) ]

Answer 1

SortedDoublyLinkedList class:

// create a SotredDoublyLinkedList class that implements LinkedList interface
public class SortedDoublyLinkedList implements LinkedList {
   // create a private Node class to store Warrior class data
   private class Node{
       Warrior warrior; // data member
       Node next; // link to next node
       Node prev; // link to previous node
       Node(Warrior w){ // constructor of inner class
           // initialize all members of inner class
           warrior = w;
           next = null;
           prev = null;
       }
   }
  
   public Node start; // first node of the list
   public Node end; // last node of list
  
   // constructor
   SortedDoublyLinkedList(){
       // initialize member variables
       start = null;
       end = null;
   }
  
   // implement interface methods

   @Override
   public void insert(Warrior warrior) {
       // add a node in the list,
       // in sorted order based on the speed of the warrior
      
       // create a node with given data
       Node n = new Node(warrior);
       // check if start is null
       if(start == null) {
           // enter first node
           start = n;
           end = n; // last node is first node(only node)
       }
       else {
           // check if node need to be inserted at start
           if(start.warrior.getSpeed()<n.warrior.getSpeed()) {
               // insert node at start
               n.next = start; // linked right side
               start.prev = n; // linked left side
               // reassign start
               start = n;
           }
           else {
               // iterate the list and insert node in sorted position
               Node itr = start;
               // create a flag to see if node is inserted
               boolean isNodeInseted = false;
               while(itr != end) {
                   if(itr.next.warrior.getSpeed()<n.warrior.getSpeed()) {
                       // insert node at the next location
                       n.next = itr.next; // link to right side
                       n.prev = itr; // link to left side
                       // reassign list node's links
                       itr.next.prev = n;
                       itr.next = n;
                       // set flag to true
                       isNodeInseted = true;
                       // break the while loop as node insertion is done
                       break;
                   }
                   else {
                       itr = itr.next;
                   }
               }//end of while loop
               // check if node is inserted or not
               if(!isNodeInseted) {
                   // insert the node at end of list
                   n.prev = end; // linked left side
                   end.next = n; // linked right side
                   // reassign end of list
                   end = n;
               }
           }// node inserted
       }
   }
  
   @Override
   public String toString() {
       // create a string to return
       String str = "[ ";
       // call toString of each node in the list
       // create iterator to loop the list
       Node itr = start;
       while(itr != null) {
           str = str + itr.warrior.toString() + " ";
           itr = itr.next;
       }
       str = str + "]";
       // return the string
       return str;
      
   }

}

LinkedListDriver class:

public class LinkedListDriver {
  
   public static void main(String[] args) {
       LinkedList list = new SortedDoublyLinkedList();
      
       System.out.println(list);
       Warrior krogg = new Warrior("Krogg", 30, 50, 200);
       list.insert(krogg);
      
       System.out.println(list);
       Warrior gurkh = new Warrior("Gurkh", 40, 45, 180);
       list.insert(gurkh);
      
       System.out.println(list);
       Warrior brynn = new Warrior("Brynn", 45, 40, 190);
       list.insert(brynn);
      
       System.out.println(list);
       Warrior dolf = new Warrior("Dolf", 20, 65, 210);
       list.insert(dolf);
      
       System.out.println(list);
       Warrior zuni = new Warrior("Zuni", 50, 35, 170);
       list.insert(zuni);
      
       System.out.println(list);
   }
}

Warrior class:

public class Warrior {
   private String name;
   private int speed;
   private int strength;
   private int hp;
   public Warrior(String name, int speed, int str, int hp) {
       this.name = name;
       this.speed = speed;
       this.strength = str;
       this.hp = hp;
   }
  
   public String getName() { return this.name; }
   public int getSpeed() { return this.speed; }
   public int getStrength() { return this.strength; }
   public int getHp() { return this.hp; }
  
   public String toString() {
       return this.name + "(" + this.speed + ")";
   }
}

LinkedLIst interface:

public interface LinkedList {
  
   void insert(Warrior warrior);
   String toString();

}