Using Arrays

Using Singly Linked List

Using Doubly Linked List

Problem $1$: Write the Java code for performing add$($e$)$ and remove$($e$)$ methods for the

Scoreboard class, as shown below, except this time, don$$t maintain the game entries in

order. Assume that we still need to keep n entries stored in indices $0$ to n$-1.$ You should

be able to implement the methods without any loop so that the number of steps they

perform does not depend on n$.$ Create a Driver class to test your code.

CSC $260$ Fundamental Data Structures Page of$13/**$ Class for storing high scores in an array in nondecreasing order. $*/$

public class Scoreboard $\{$

private int numEntries $=0$;$\frac{,}{\frac{?}{?}}$ number of actual entries

private GameEntry$[]$ board;

$\frac{\frac{?}{?}}{?}$ array of game entries $($names & scores$)$

$\frac{?}{?}****$ Constructs an empty scoreboard with the given capacity for storing entries. $*/$

public Scoreboard$($int capacity$)\{$

board $=$ new GameEntry$[$capacity$]$;

$\}$

$/**$ Attempt to add a new score to the collection $($if it is high enough$)*/$

public void add$($GameEntry e$)\{$

int newScore $=$ e$.$getScore$()$;

$\frac{\frac{?}{?}}{?}$ is the new entry e really a high score?

if $($numEntries $$ board.length $||$ newScore $>$ board$[$numEntries$-1].$getScore$())\{$

if $($numEntries $$ board.length$)$

$\frac{\frac{?}{?}}{?}$ no score drops from the board

numEntries$++$;

$//$ so overall number increases

$//$ shift any lower scores rightward to make room for the new entry

int $j=$ numEntries $-1$ ;

while $(j>0$ && board $j-1.$getScore $)$ newScore$)\{$

board$[$j$]=$ board$[$j$-1]$; $\frac{,}{\frac{?}{?}}$ shift entry from $j-1$ to $j$

j$--$; $//$ and decrement $j$

$\}$

board$[$j$]=$ e; $\frac{,}{\frac{?}{?}}$ when done, add new entry

$\}$

$\}$

$/**$ Remove and return the high score at index i$.*/$

public GameEntry remove$($int i$)$ throws IndexOutOfBoundsException $\{$

if $(i($:$0||i$:$)=$ numEntries$)$

throw new IndexOutOfBoundsException$("$Invalid index: $"+$ i$)$;

GameEntry temp $=$ board$[$i$]$; $//$ save the object to be removed

for $($int $j=i$;$j$ numEntries $-1$;$j++)//$ count up from $i($not down$)$

board$[$j$]=$ board$[$j$+1]$; $\frac{,}{\frac{?}{?}}$ move one cell to the left

board$[$numEntries $-1]=$ null; $\frac{,}{\frac{?}{?}}$ null out the old last score

numEntries$--$;

return temp;

$\frac{\frac{?}{?}}{?}$ return the removed object

$\}$

Problem $2$: Write a class that maintains the top ten scores for a game

application, implementing the add and remove methods as discussed in the

previous problem, but using a Singly Linked List instead of an array. Create a

Driver class to test your code.

Problem $3$: Perform the previous problem using a Doubly Linked List. Your

implementation of the remove method should make the fewest number of pointer

hops to get to the game entry. Create a Driver class to test your code.

CSC $260$ Fundamental Data Structures Page of$33$