3

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?

  • With your approach: if you use a dubly linked list you can decrease the worst-case performance from O(n) to O(n/2) – marstato Mar 17 '17 at 14:14
  • @marstato which is still O(n) ;-) – mgoeminne Mar 18 '17 at 10:41
  • Arguably no. The constant factor per Iteration remains the same between the two algorithms. When you run both on an Infinite, random number of inputs, the optimized version will turn out to be twice as fast. – marstato Mar 18 '17 at 10:44
  • It will be twice as fast, but the complexity remains O(n). – mgoeminne Mar 18 '17 at 10:49
  • @mgoeminne true, but the question asks for efficiency, not just the best possible complexity. The constant factor is relevant here. – Jules Mar 18 '17 at 14:11
1

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
1

Because a put operation only adds elements at the end of the queue, you can easily and efficiently implement it by maintaining a reference to the last node of the list.

Using arrays can help you to decrease the time needed to access a random element, but they will only divide this time by a ~ constant factor. So it doesn't reduce the complexity.

I would try an approach based on skewed binary random access lists. Technically, these are not lists anymore, but trees that represent lists. Given the exercise, I would introduce them as "lists represented by linked nodes".

The structure of the traversed tree mirrors the positions of the contained values, in such a way you can convert an arbitrary value position into a binary representation, and traverse the tree according to this representation to reach/set the value corresponding to the specified position.

Inserting and retrieved the value at a particular position are O(log n) operations. Even better, insertion and retrieving at the end (or the beginning) of the list are O(1) operations.

  • For curiosity's sake, through which way would the array-based implementation reduce runtime by a constant factor? The current implementation I had in my head was generating a random number of the array, accessing that node, checking if that node was part of a linked list (Something I'm not sure yet how to do) and rerunning the method if the element is not part of the linked list. – Isofruit Mar 18 '17 at 11:05
  • 1
    Well, my idea was to place fixed size arrays of values in nodes. If you have arrays of T values, if you want to access to value in position N, you must traverse the N/T first nodes and then read entry N%T in the array of your current node. Accessing the element in the array is a O(1) operation, and accessing node N/T is O(N/T) = O(N). If you double T, you divide your traversal time by ~2, but it's still linear to N. – mgoeminne Mar 18 '17 at 11:56
1

Sorry for the late answer but I think this will give O(1) insertion, removal and random access.

Store the linked list nodes in a pre-allocated array.

Addition involves adding the new node to the first free slot in the array.

Removal is the complicated part. It may leave an empty slot in the middle of the array. However, this free slot can be immediately filled with the node that is currently at the end of the array. So the node at the end is moved into the free slot, thus ensuring that nodes are always at sequential locations in the array. For this to work when given a node as input, each node will need to store its index in the array.

So o(1) random access is given because the nodes are always at sequential locations in the array.

0

This approach might only be more efficient for very large linked-lists that are only moderately dynamic. If we implement the linked-list using an array of Nodes (called nodeArray), it is possible to keep track of all indices of the nodeArray using a second array int[] of the length nodeArray.length*2 (called indexArray) together with the int 'start' and int 'end'. The nodeArray also needs an int 'listSize' that keeps track of the length of the linkedList (initialized at 0, incremented if put() is called, decremented if get() is called.

start is always the index of the cell containing the head of the linked-list. end is always the index of the cell after the tail of the linked-list. A cell with a value of indexArray.length between 'start' and 'end' indicates a cell that used to contain an index to a cell in nodeArray, but that Node got removed by the get method. All cells between start and end (including index start, excluding index end and cells with a value of indexArray.length) are all indices of the nodeArray that make up the linked-list in correct order.

This array needs the following methods accessing it:

  1. The put method, besides putting a new Node containing a value at the end of the linked-list in nodeArray, now also needs to put the index in which the new Node is put in the nodeArray in indexArray[end] and increment 'end' by 1.
  2. The get method generates a random number rng between 0 and listSize. It then iterates through the indexArray, starting from 'start' and going through rng iterations, not counting cells it encounters with a value of indexArray.length - this should be faster than iterating through a normal node-based linked list.

This has the following problems:

  1. The put method always increases the amount of cells between 'start' and 'end' by 1 every time it gets invoked while no method reduces them (get only sets a cell between the two to indexArray.length). This eventually will cause in indexOutOfBoundsException, forcing the insertion of additional code that creates a new array of double the size and then copying over the content of all cells in indexArray into this new array, ignoring all cells with a value of indexArray.length of course.
  2. Since you still iterate through an array, the complexity stays the same. So this only gains some speed by the fact that iterating through indexArray is faster than through a normal linkedList but you also lose some through the more clunky put and get methods in addition to the memory you need to sacrifice to make the indexArray.

Therefore this solution might only be marginally better in the case of huge linked lists and definitely not if the initiation size of indexArray was chosen badly.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.