Don't forget to have the main method A. Write a class that maintains the top ten...

Question

Question

Don't forget to have the main method A. Write a class that maintains the top ten...

Don't forget to have the main method

A. Write a class that maintains the top ten scores for a game application, implementing the add and remove methods but using a singly linked list instead of an array.

B. 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.

Engineering Computer-Science

0 0

Add a comment Transcribed image text

Answer 1

Answer #1

Answer -1:-

File: DoublyLinkedList.java

// DoublyLinkedList class implementation
public class DoublyLinkedList
{
// ---------------- nested Node class ----------------
public static class Node
{
private GameEntry element;
private Node prev;
private Node next;

public Node(GameEntry e, Node p, Node n)
{
element = e;
prev = p;
next = n;
}

public GameEntry getElement()
{
return element;
}

public Node getPrev()
{
return prev;
}

public Node getNext()
{
return next;
}

public void setPrev(Node p)
{
prev = p;
}

public void setNext(Node n)
{
next = n;
}
} // ----------- end of nested Node class -----------

// instance variables
private Node header;
private Node trailer;
private int size = 0;

public DoublyLinkedList()
{
header = new Node(null, null, null);
trailer = new Node(null, header, null);
header.setNext(trailer);
}

public int size()
{
return size;
}

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

public Node getHeader()
{
return header;
}

public Node getTrailer()
{
return trailer;
}

public GameEntry first()
{
if (isEmpty())
return null;

return header.getNext().getElement();
}

public GameEntry last()
{
if (isEmpty())
return null;

return trailer.getPrev().getElement();
}

public void addFirst(GameEntry e)
{
addBetween(e, header, header.getNext());
}

public void addLast(GameEntry e)
{
addBetween(e, trailer.getPrev(), trailer);
}

public GameEntry removeFirst()
{
if (isEmpty())
return null;

return remove(header.getNext());
}

public GameEntry removeLast()
{
if (isEmpty())
return null;
return remove(trailer.getPrev());
}

private void addBetween(GameEntry e, Node predecessor, Node successor)
{
Node newNode = new Node(e, predecessor, successor);
predecessor.setNext(newNode);
successor.setPrev(newNode);
size++;
}

private GameEntry remove(Node node)
{
Node predecessor = node.getPrev();
Node successor = node.getNext();
predecessor.setNext(successor);
successor.setPrev(predecessor);
size--;
return node.getElement();
}

public String toString()
{
StringBuilder sb = new StringBuilder("(");
Node walk = header.getNext();
while (walk != trailer)
{
sb.append(walk.getElement());
walk = walk.getNext();
if (walk != trailer)
sb.append(", ");
}
sb.append(")");
return sb.toString();
}

public void add(GameEntry ge)
{
if(size == 10 && ge.getScore() < header.next.element.getScore())
{
return;
}

if (isEmpty())
{
Node newNode = new Node(ge, header, trailer);
header.next = newNode;
trailer.prev = newNode;
}
else if(ge.getScore() < header.next.element.getScore())
{
Node newNode = new Node(ge, header, header.next);
header.next = newNode;
header.next.prev = newNode;
}
else if(ge.getScore() > trailer.prev.element.getScore())
{
Node newNode = new Node(ge, trailer.prev, trailer);
trailer.prev.next = newNode;
trailer.prev = newNode;
}
else
{
Node current = header.next;
Node previous = null;

while(current != trailer && ge.getScore() > current.element.getScore())
{
previous = current;
current = current.next;
}

Node newNode = new Node(ge, previous, previous.next);
previous.next = newNode;
previous.next.prev = newNode;
}

incrementSize();

if(size > 10)
{
header.next = header.next.next;
decrementSize();
}
}

public GameEntry remove(int i)
throws IndexOutOfBoundsException
{
if (i < 0 || i >= size)
{
throw new IndexOutOfBoundsException(
"Invalid index: " + i);
}

int count = 0;
Node current = header.next;
Node previous = null;
while (current != trailer && count < i)
{
previous = current;
current = current.next;
count++;
}
GameEntry result = null;
if (i == 0)
{
result = header.next.element;
header.next = header.next.next;
}
else if (i == size - 1)
{
result = trailer.prev.element;
previous.next = trailer;
trailer = previous.next;
}
else
{
result = previous.next.element;
previous.next = current.next;
current.next.prev = previous;
}
decrementSize();

if (size == 0)
trailer = null;

return result;
}

public void incrementSize()
{
size++;
}

public void decrementSize()
{
size--;
}

} // end of DoublyLinkedList class

File: SinglyLinkedListDriver.java

// SinglyLinkedListDriver class implementation
public class SinglyLinkedListDriver
{
public static void main(String[] args)
{
SinglyLinkedList highscores = new SinglyLinkedList();
String[] names = { "Rob", "Mike", "Rose", "Jill", "Jack", "Anna", "Paul", "Bob" };
int[] scores = { 750, 1105, 590, 740, 510, 660, 720, 400 };

for (int i = 0; i < names.length; i++)
{
GameEntry gE = new GameEntry(names[i], scores[i]);
System.out.println("Adding " + gE);
highscores.add(gE);
}

System.out.println("\nTraversing the linked list:");
SinglyLinkedList.Node node = highscores.getHead();
while (node != null)
{
System.out.printf("%s -> ", node.getElement());
node = node.getNext();
}
System.out.println("null");

System.out.println("\nRemoving " + highscores.remove(3));

System.out.println("\nTraversing the linked list:");
node = highscores.getHead();
while (node != null)
{
System.out.printf("%s -> ", node.getElement());
node = node.getNext();
}
System.out.println("null");
}
} // end of SinglyLinkedListDriver class

File: GameEntry.java

// GameEntry class implementation
public class GameEntry
{
private String name;
private int score;

public GameEntry(String n, int s)
{
name = n;
score = s;
}

public String getName()
{
return name;
}

public int getScore()
{
return score;
}

public String toString()
{
return "(" + name + ", " + score + ")";
}
} // end of GameEntry class

Sample Output:

Adding (Rob, 750)
Adding (Mike, 1105)
Adding (Rose, 590)
Adding (Jill, 740)
Adding (Jack, 510)
Adding (Anna, 660)
Adding (Paul, 720)
Adding (Bob, 400)

Traversing the linked list:
(Bob, 400) -> (Jack, 510) -> (Rose, 590) -> (Anna, 660) -> (Paul, 720) -> (Jill, 740) -> (Rob, 750) -> (Mike, 1105) -> null

Removing (Anna, 660)

Traversing the linked list:
(Bob, 400) -> (Jack, 510) -> (Rose, 590) -> (Paul, 720) -> (Jill, 740) -> (Rob, 750) -> (Mike, 1105) -> null

-----------------------------------------------------------------------

Answer 2 (DoublyLinkedList):