Previously in class when talking about linked lists, I had mentioned a technique in games where you might have a dynamic collection of entities $($such as enemy objects$)$ that you wish to iterate through to do some common procedure, like movement updates or collision detection. While this isn't quite what you would do in practice, this problem will illustrate certain considerations involved. We will model an enemy list as some sort of dynamic list of enemy IDs, where:

i$.$

The size of the list can be variable

ii$.$

We want to be able to iterate through the entire list efficiently

iii.

We will have to remove entries at any position in the list, in any order $($if the enemy dies, etc$)$

Consider the use of a doubly$-$linked list of integers to represent this. We care about the doubly$-$linked list over a singly$-$linked list because if we remove a node we have the link to both the node before and after it to reconnect the list. While typically removing arbitrary entries in a linked list is expensive since it doesn't have fast random access to find where those entries are, if we are deleting nodes during the full list iteration, any nodes to be deleted will already be available.

a$.$

Create an EntityList class that extends DoublyLinkedList from the Lecture $3$ notes. You will have to change the private fields and methods $($Node$,$ header, trailer, size, remove$())$ to protected in order to work with nodes.

b$.$

Write a private boolean method called checkRemove that takes a Node as input, and for the sake of simulation, generates a random number to see whether it should be removed or not. Give it a $1$ in $20$ chance to return true, otherwise return false.

b$.$

Write a similar private boolean method called checkCollided that takes a Node as input and generates a random number to see whether it "collided with the player". Give it a $1$ in $500$ chance to return true, otherwise return false.

c$.$

Write a public boolean method updateAll that starts at the head node $($not the dummy header$),$ and loops through each node. It should run checkRemove, and if it returns true, delete that node from the list. If not, it should run checkCollided, and if that returns true, it should set a flag variable to true. We use a flag variable for the method instead of returning right away so that later nodes get removed if needed. After the loop, return true if the flag variable was set to true.

d$.$

In a driver class, create an EntityList and fill it with integers from $0$ to $99.$ Then run a loop where updateAll is called; if it returns true the loop should end and print "Player hit!", otherwise it should print the size of the list.

e$.$

Suppose we were implementing this model with a fixed$-$size array instead. Draw a diagram showing a small example of what this array might look like and how its entries might have to adjust in the process of removing multiple random entities from it during one iteration of the list.