Random access Queue : LinkedList or array ?

[somjit{}]

i have to create a queue where the dequeue operations will be random. that is , a random location will be chosen, and deleted after returning the data stored at that location.

i was going through the two underlying datastructures that im allowed to use : linked list , and arrays. ( i cant use any prebuilt java api like the prebuilt LinkedList or ArrayList classes for the task, and have to create the data structure on my own. )

my question is, which datastructure implementation would be the overall faster process? linked lists are faster in adding and deleting elements, also doesn't need resizing, but arrays are faster at random accessing. I wanted to go with linked list as i feel it will be easier to code, but im reading in a lot of places over the web at linkedlists being old, unfashioned n stuff... and arrays are the way to go.

any suggestion , and some explanations if possible, would be great..

thanks for your help. :)
somjit.

[JamesCherrill]

Unless you are processing a vast number of dequeues against a huge queue then "faster" is not going to be relevant. Do you reeally care if they take 1 microSecond vs 2 microSeconds?
Easy to code, easy to read and understand, easy to debug, easy to modify or enhance - those are the issues that matter (listed in increasing order of importance).
Arrays seem simple, but you have to deal with low-level issues like growing the array when its initial capacity is exceeded, of shuffling down all gthe following elements when you delete one in the middle.
IMHO linked lists are better to work with in every respect, except for the speed of accesing random elements by their index number (but see first sentence above).
As for " linkedlists being old, unfashioned n stuff... and arrays are the way to go" - that sounds like total rubbish to me - anyone else want to offer an opinion?

Final observation: in real life, if this was a critical part of some performance sensitive big application, I would write a small class to encapsulate this functionality, and keep the implementation (array / linked list / tree set etc) private. That way, if it became necessary, I could try different implementations without having to change or break anything else.

[somjit{}]

that sounds like total rubbish to me

i also wanted to go with linked list, as its easy to code, and doesnt involve all the low level issues that you mentioned. .. really needed that clarification :D the only reason i made this post was to clear up the confusion i was having after reading a few of those posts over the web where they were making those claims...

But yes, this is an algorithm assignment, and the course involves in making algorithms to increase performance of codes in real world applications. so it probably will be tested for speed, with im assuming some pretty large queue size. Also, just like you mentioned, we have to keep our implementation private, such that the client doesnt have to know how the data structure is implemented, and design the code keeping in mind that it will be a part of a bigger application, as stacks and queues are fundamental datastructures.

So the part you talked about writing a small class to encapsulate the functionality, if you could tell more about that, it would really help me out a lot...

[JamesCherrill]

a small class to encapsulate the functionality

Basically, start a class called (eg) MyQueue, and write method headers for all the public methods your queue will need (public cnstructor, add... , delete... etc). Then chose an implementation and fill in the method bodies (these will be 99% just calling the corresponding method for Linked List, somewhat harder for an array implementation). Now anyone can use your class by calling the public methods, and you can change the impelmentation anytime without affecting them.

[somjit{}]

this is a code i came up for randomized deque. its all good , except its failing in timing tests... my code takes up too much time, and its because i put up a getRanPointer() method that takes linear time to get each random node from the linked list...

if you could give some solutions on how to make the whole process run in constant amortized time (thats what is required) , it would be great...

import java.util.Iterator;

public class RandomizedQueue<Item> implements Iterable<Item> {

    private int size;
    private Node head, tail;

    private class Node {
        Item item;
        Node next;
        Node prev;
    }

    public RandomizedQueue() {
        head = new Node();
        head.next = null;
        head.prev = null;
        head.item = null;
        tail = head;
    }

    public boolean isEmpty() {
        return tail == head;
    }

    public int size() {
        return size;
    }

    public void enqueue(Item item) {
        if (item == null)
            throw new java.lang.NullPointerException(
                    " adding null values is not allowed ");
        else {
            Node oldTail = tail;
            tail = new Node();
            tail.item = item;
            tail.next = null;
            tail.prev = oldTail;
            oldTail.next = tail;
            size++;
        }
    }

    private Node getRanPointer() {
        int ran = 1 + StdRandom.uniform(size); // since head is a sentinel, so
                                                // actual database starts after
                                                // head , hence 1 is added
        Node pointer = head.next;
        for (int i = 1; i < ran; i++) { // as data starts from index 1 instead
                                        // of index 0 (which denotes the head)
            pointer = pointer.next;
        }
        return pointer;
    }

    public Item dequeue() {
        if (isEmpty())
            throw new java.util.NoSuchElementException(
                    " cannot remove from an empty deque");
        else {
            Node pointer = getRanPointer();
            Item item;

            if (pointer == head) {
                item = head.item;
                head = head.next;
                head.prev = null;
                size--;
            } else if (pointer == tail) {
                item = tail.item;
                tail = tail.prev;
                tail.next = null;
                size--;
            } else {
                item = pointer.item;
                pointer.prev.next = pointer.next;
                pointer.next.prev = pointer.prev;
                pointer = null; // deletes the pointer
                size--;
            }
            return item;
        }
    }

    public Item sample() {
        if (isEmpty())
            throw new java.util.NoSuchElementException(
                    " cannot remove from an empty deque");
        else {
            Node pointer = getRanPointer();
            return pointer.item;
        }
    }

    @Override
    public Iterator<Item> iterator() {

        return new Iterator<Item>() {

            private Node current = head.next;

            @Override
            public boolean hasNext() {
                return current != null;
            }

            @Override
            public Item next() {
                if(current == null)
                    throw new java.util.NoSuchElementException("no more items to iterate");
                Item temp = current.item;
                current = current.next;
                return temp;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException(
                        "remove is illegal to use as per the API");
            }

        };
    }
}

[JamesCherrill]

If you really want to access random elements in constant time and not O(n) then I guess you have to use an array rather than a linked list. Of course the time to remove an element will then go up, ands some adds will be expensive when yopu have to re-size the array.

[somjit{}]

will this work?

1. create an array of size 1000 to start.
2. with every new Node created , hold the address of the node in the array
3. getRanPointer() method will return the value (address) stored at a particular element at random , and assign that elemnt now with a value -1
4. deque() works with the returned address
5. when linked list size becomes greater than the array size, double the array, when its size becomes less than 1/4 the array size, reduce array size by 1/2 . ( these i can do in amortized time )

at step 3 , there will be some checks to see whether or not the array element chosen at random holds value -1 , if it doesnt , it will return the value and assign -1 to it , else iterate again till it finds a valid element.

[bguild]

Normally when someone says "random access" the meaning is that you can access any element you want, not that the element you get is chosen for you by some random process beyond your control. Since you actually do mean to give the client no control over which element gets dequeued, you should certainly use an array.

It seems that you made a mistake in your post. Instead of -1, surely you meant null, since you were talking about an array of addresses, not ints. Even so, don't worry about that because you can get a much better effect by just using an array of Items, without a linked list.

Your linked list structure is what someone would use to keep track of a queue where order is important, but order is important in a queue only because elements are dequeued in the order that they arrived. In your queue elements are dequeued in random order, so stop trying to keep track of their order.

Instead, just create an Item[] content with a size that is approximately what you will need. You can store your queue in the first few elements of content, and if the queue becomes too large make a larger array. Store the size of the queue in a field such as size, and store the items at indices 0 to size - 1. When an item is enqueued, store it in content[size - 1] and increment size. When an item is dequeued, pick an random index i in the range of 0 to size - 1 and store that item somewhere so you can return it later, then decrement size, then make content[i] = content[size] so the last element of the queue doesn't get lost. The order of the elements is changed by doing that, but you don't care about the order of the elements.

That's constant time to dequeue an element every time. Amortization is not necessary. A linked list couldn't do any better than that.

[somjit{}]

thankyou so much for the detailed answer !

ill practice this method.. thanks again :)