1.In Java, write a program that maintains the top ten scores for a game application, implementing the add and remove methods using a singly linked list instead of an array.

2. Perform the previous project but use a doubly linked list. Moreover, your implementation of remove(i) should make the fewest number of pointer hops to get to the game entry at index i.

Please use the SinglyLinkedList and DoublyLinkedList classes shown below as well as the GameEntry and ScoreBoard classes modified with singly linked list and doubly linked list instead of an array. Also create driver classes for both to show output.

public class SinglyLinkedList { private static class Node { private E element; private Node next; public Node(E e, Node n) { element = e; next = n; }

public E getElement() { return element; }

public Node getNext() { return next; }

public void setNext(Node n) { next = n; } } private Node head = null; private Node tail = null; private int size = 0; public SinglyLinkedList() { }

public int size() { return size; }

public boolean isEmpty() { return size == 0; }

public E first() { if (isEmpty()) return null; return head.getElement(); }

public E last() { if (isEmpty()) return null; return tail.getElement(); } public void addFirst(E e) { head = new Node(e, head); if (size == 0) tail = head; size++; } public void addLast(E e) { Node newest = new Node(e, null); if (isEmpty()) head = newest; else tail.setNext(newest); tail = newest; size++; } }

1 /** A basic doubly linked list implementation. */ 2 public class DoublyLinkedList { 3 //--------------.- nested Node class 4 private static class Node { 5 private E element; // reference to the element stored at this node 6 private Node prev; // reference to the previous node in the list 7 private Node next; // reference to the subsequent node in the list 8 public Node(E e, Node p, Node n) { 9 element = e; 10 prev = p; 11 next = n; 12 } 13 public E getElement() { return element; } 14 public Node getPrev() { return prev; } 15 public Node get Next() { return next; } 16 public void setPrev(Node p) { prev = p; } 17 public void setNext(Node n) { next n; } 18 }//--------- end of nested Node class 19 1 /** A basic doubly linked list implementation. */ 2 public class DoublyLinkedList { 3 //--------------.- nested Node class 4 private static class Node { 5 private E element; // reference to the element stored at this node 6 private Node prev; // reference to the previous node in the list 7 private Node next; // reference to the subsequent node in the list 8 public Node(E e, Node p, Node n) { 9 element = e; 10 prev = p; 11 next = n; 12 } 13 public E getElement() { return element; } 14 public Node getPrev() { return prev; } 15 public Node get Next() { return next; } 16 public void setPrev(Node p) { prev = p; } 17 public void setNext(Node n) { next n; } 18 }//--------- end of nested Node class 19 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 // public update methods /** Adds element e to the front of the list. */ public void addFirst(E e) { addBetween(e, header, header.getNext()); // place just after the header } /** Adds element e to the end of the list. */ public void addLast(E e) { addBetween(e, trailer.getPrev(), trailer); // place just before the trailer } /** Removes and returns the first element of the list. */ public E removeFirst() { if (isEmpty()) return null; // nothing to remove return remove(header.getNext()); // first element is beyond header } /** Removes and returns the last element of the list. */ public E removeLast() { if (isEmpty()) return null; // nothing to remove return remove(trailer.get Prev()); // last element is before trailer 62} 64 // private update methods 65 /** Adds element e to the linked list in between the given nodes. */ 66 private void add Between(E e, Node predecessor, Node successor) { 67 // create and link a new node 68 Node newest = new Node(e, predecessor, successor); 69 predecessor.setNext(newest); 70 successor.setPrev(newest); 71 size++i 72 } 73 /** Removes the given node from the list and returns its element. */ 74 private E remove(Node node) { 75 Node predecessor = node.getPrev(); 76 Node successor = node.getNext(); 77 predecessor.setNext(successor): 78 successor.setPrev(predecessor); 79 size-- 80 return node.getElement(); 81 } 82 } //----------- end of DoublyLinked List class A game entry stores the name of a player and her best score so far in a game 1 public class GameEntry { 2 private String name; // name of the person earning this score 3 private int score; // the score value 4 /** Constructs a game entry with given parameters., */ 5 public GameEntry(String n, int s) { 6 name = n; 7 score = si 8 } /** Returns the name field. */ 0 public String getName() { return name; } 1 /** Returns the score field. */ 2 public int getScore() { return score; } 3 /** Returns a string representation of this entry */ 4 public String toString() { 5 return "(" + name + " + score + ")"; 6 } 7 } 9 11 . Keep track of players and their best scores in an array, board The elements of board are objects of class GameEntry Array board is sorted by score 11 1 /** Class for storing high scores in an array in nondecreasing order. */ 2 public class Scoreboard { 3 private int numEntries = 0; // number of actual entries 4 private GameEntry[ ] board; // array of game entries (names & scores) 5 /** Constructs an empty scoreboard with the given capacity for storing entries. */ public Scoreboard (int capacity) { 7 board = new GameEntry[capacity]: 8 } // more methods will go here 36} /** Attempt to add a new score to the collection (if it is high enough) */ public void add(GameEntry e) { int newScore = e.getScore(); // is the new entry e really a high score? if (numEntries board[numEntries-1).getScore()) { if (numEntries 0 && board[j-1].getScore() = numEntries) throw new IndexOutOfBoundsException("Invalid index: " + i); GameEntry temp = board[i]; // save the object to be removed for (int j = i; j { 3 //--------------.- nested Node class 4 private static class Node { 5 private E element; // reference to the element stored at this node 6 private Node prev; // reference to the previous node in the list 7 private Node next; // reference to the subsequent node in the list 8 public Node(E e, Node p, Node n) { 9 element = e; 10 prev = p; 11 next = n; 12 } 13 public E getElement() { return element; } 14 public Node getPrev() { return prev; } 15 public Node get Next() { return next; } 16 public void setPrev(Node p) { prev = p; } 17 public void setNext(Node n) { next n; } 18 }//--------- end of nested Node class 19 1 /** A basic doubly linked list implementation. */ 2 public class DoublyLinkedList { 3 //--------------.- nested Node class 4 private static class Node { 5 private E element; // reference to the element stored at this node 6 private Node prev; // reference to the previous node in the list 7 private Node next; // reference to the subsequent node in the list 8 public Node(E e, Node p, Node n) { 9 element = e; 10 prev = p; 11 next = n; 12 } 13 public E getElement() { return element; } 14 public Node getPrev() { return prev; } 15 public Node get Next() { return next; } 16 public void setPrev(Node p) { prev = p; } 17 public void setNext(Node n) { next n; } 18 }//--------- end of nested Node class 19 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 // public update methods /** Adds element e to the front of the list. */ public void addFirst(E e) { addBetween(e, header, header.getNext()); // place just after the header } /** Adds element e to the end of the list. */ public void addLast(E e) { addBetween(e, trailer.getPrev(), trailer); // place just before the trailer } /** Removes and returns the first element of the list. */ public E removeFirst() { if (isEmpty()) return null; // nothing to remove return remove(header.getNext()); // first element is beyond header } /** Removes and returns the last element of the list. */ public E removeLast() { if (isEmpty()) return null; // nothing to remove return remove(trailer.get Prev()); // last element is before trailer 62} 64 // private update methods 65 /** Adds element e to the linked list in between the given nodes. */ 66 private void add Between(E e, Node predecessor, Node successor) { 67 // create and link a new node 68 Node newest = new Node(e, predecessor, successor); 69 predecessor.setNext(newest); 70 successor.setPrev(newest); 71 size++i 72 } 73 /** Removes the given node from the list and returns its element. */ 74 private E remove(Node node) { 75 Node predecessor = node.getPrev(); 76 Node successor = node.getNext(); 77 predecessor.setNext(successor): 78 successor.setPrev(predecessor); 79 size-- 80 return node.getElement(); 81 } 82 } //----------- end of DoublyLinked List class A game entry stores the name of a player and her best score so far in a game 1 public class GameEntry { 2 private String name; // name of the person earning this score 3 private int score; // the score value 4 /** Constructs a game entry with given parameters., */ 5 public GameEntry(String n, int s) { 6 name = n; 7 score = si 8 } /** Returns the name field. */ 0 public String getName() { return name; } 1 /** Returns the score field. */ 2 public int getScore() { return score; } 3 /** Returns a string representation of this entry */ 4 public String toString() { 5 return "(" + name + " + score + ")"; 6 } 7 } 9 11 . Keep track of players and their best scores in an array, board The elements of board are objects of class GameEntry Array board is sorted by score 11 1 /** Class for storing high scores in an array in nondecreasing order. */ 2 public class Scoreboard { 3 private int numEntries = 0; // number of actual entries 4 private GameEntry[ ] board; // array of game entries (names & scores) 5 /** Constructs an empty scoreboard with the given capacity for storing entries. */ public Scoreboard (int capacity) { 7 board = new GameEntry[capacity]: 8 } // more methods will go here 36} /** Attempt to add a new score to the collection (if it is high enough) */ public void add(GameEntry e) { int newScore = e.getScore(); // is the new entry e really a high score? if (numEntries board[numEntries-1).getScore()) { if (numEntries 0 && board[j-1].getScore() = numEntries) throw new IndexOutOfBoundsException("Invalid index: " + i); GameEntry temp = board[i]; // save the object to be removed for (int j = i; j