I'm currently working through Robert Sedgewicks "Algorithms in java" (3rd edition, german) on my own and am currently at one of the more complicated questions there. I think I may have the starting point for a solution, but I'm not sure if its really the best way to go.
The exercise (translated):
Create an abstract datatype of a random-access-queue: Write an interface and an implementation that uses a linked list as basic data structure. Be as efficient as possible in the implementations of "put" and "get" methods and analyze their cost in a worst case scenario.
For clarity: The put method inserts an element at the end of the queue. Only the get method has a random part, in which it accesses a random part of the linked list, returns its value and removes the element from the linked list.
My ideas so far:
1. Implement linked list using node objects
This is the more obvious implementation, implementing a linked list using Node objects that contain a value (may be primitive data type or an Object) and a reference to the next Node. Then have a "head" and a "tail" reference stored in the class of the queue implementation. The get method in this case would first calculate a number between 0 and "queueSize" (the number of elements in the queue) and then go from node to node (starting with head) using the reference in "next" "queueSize" times, return the value of the node you land on and then remove it from the list.
However, I doubt that is the most efficient method and don't see a way to make it efficient.
2. Implement linked list using an array of node objects
Implementing the linked list of the queue by using an array of nodes, node objects again containing a value (may be primitive datatype or an Object) and a reference to either another node or null. One could then access a random node by randomly generating an index between 0 and the array length and accessing the Node object in that cell. Problem here obviously lies in the fact that not every Node in the array is going to be part of the linked-list at all times. And I don't see an efficient/quick way to get that information.
Therefore my question is, what implementation of the linked list is the way to go here? Is there a way to make sure a randomly generated number in an array-based linked-list points only at array cells that are part of the linked list? Or is there a way to write an efficient get-method for the first approach?