Java – Designing an efficient implementation of a random access queue based on a linkedlist

designjavalinked listqueue

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?

Best Answer

Warning: this is not something that you'd ever want to do. But I'm guessing it's in the "Creative Problems" section (looking at the fourth edition non-Java-specific version of Algorithms, it seems like it might be question 1.2.38 -- which refers the reader to chapter 3 for possible solutions).

OK, with that out of the way, what are some basic constraints on the problem?

  • To find an element M in a linked list of size N, you must linearly search each element in the list. While M <= N, this is still O(N).
  • In order to reduce the big-O runtime, we must find another way to access the nodes in the list.
  • A divide-and-conquer algorithm is O(logN)
  • An array is O(1), but if you had that, you wouldn't need the linked list.

So, how do you divide-and-conquer a linked list? The answer: each non-leaf element in the list contains another list.

L0
+--L1
|  +--E0
|  +--E1
+--L2
   +--E2
   +--E3

So, the top-level list holds two child lists, and those child lists hold the actual elements. We need a couple more constraints:

  • Any list L knows (1) whether it contains sublists or elements, and (2) the total number of elements held by all descendents.
  • Any list L has a limited number of children. In this case 2, but it could be any number. This is critical to the big-O evaluation: any set of operations that has a fixed size not dependent on N is equivalent to O(1).

So, let's look at how this works to find element E2:

  1. Start with node L1, which we know is a list that contains 2 elements.
  2. Since E2 is the third element, move on to node L2.
  3. We know that L2 has two children, and they're elements, so we can return element E2.

It may not be immediately obvious that search is a logN operation. If that's the case, then take a piece of paper and draw out a 14-element list.

Adding elements to this list is also an O(logN) operation, unlike a normal linked-list (which is either O(1) or O(N) depending on whether it's a singly- or doubly-linked list). Here's how it works:

  1. Find the last descendent sublist. This is again a recursive operation (so logN), which for every list element follows its right child.
  2. If that descendent sublist has only 1 element, add the new element, and recompute the sizes of all parents.
  3. If the sublist is full, you need to add another child to its parent; this is also a recursive operation, up the tree of lists.
  4. You might have to add a new root element, where the left child is the previous root and the right element is the new element.

Confused? Here's a walk-through of adding the elements to the list shown above. It starts with a single element, which is the left child of the root (I'm keeping the numbering the same as in the 4-element list).

L1
+-- E0

When we add the next element, we can store it in the right child of the root:

L1
+-- E0
+-- E1

At this point our list is full, so we have to add another level. The original root of the list is the left child of the new root, and we add another list as the right child. This new list (L2) is where we put element E2.

L
+-- L1
|   +-- E0
|   +-- E1
+-- L2
    +-- E2
Related Topic