Question

Create a method for a singlyLinked class

• public void remove( )
  • removes a randomly selected entry from the bag

I don't know how to make it random I just know how to remove the first on the list this is what I have

/**
*
* @return Removes and returns the first node of the bag
*/
@Override
public E remove()
{
if(bagHead == null)
{
return null;
}
E element = bagHead.getElement();
bagHead = bagHead.getNext();
count--;
return element;
}

It needs to be random

Answer 1

I don't know Java so I would not be able to help you with code, but I just want to help with the idea of solving your question and also I will provide the algorithm to do that so that it can be easily convertable to Java.

If you want to remove a random element then first generate random number in the range 0 to size of linked list. maintain two pointers previous and current, use loop to traverse to that randomly generated number node. now you can easily delete because you have previous pointer. set the current pointer's next to previous pointer's next and set current pointer's next to null and finally reduce the size because we have deleted the node. I have provided the visual representation of the removal process below.

ALGORITHM:

####################################################

int random = some random number between (0 , length)

set current = head or start, set prev = head or start

for i from 0 to random:

prev = current

current = current -> next element

//comment: now your current is at random number position and we have to delete it

prev -> next element = current -> next element

current -> next element = NULL

//comment: now that element is deleted, let's reduce the length of linked list

length = length - 1

##############################################################################

MORE HELP: to generate random number you can use  java.util.Random class in Java. Now that everything is answered it should not difficult to code in Java. If you have liked my explanation please like. If you have any doubts please comment.