Hi,

A friend of mine was asked a question during a CS exam about finding and maintaining the minimal element in a linked list in constant time, as elements are randomly added to and deleted from the list. He could not answer it, and after he related this to me, neither could I.

Sure, when elements are being added, you can figure out which one is the minimal by keeping it in an outside variable, but if they are deleted, how do you find the next smallest if the minimal one is gone? Is there a particular weird data structure to be used?

Thanks!

(No, it's not a homework question. Just a pointer would be sufficient to satisfy our curiousity.

Kevin

Keep the list sorted at all times, then the smallest node is always the first. Finding the smallest is a constant operation for obvious reasons, and maintaining it is also a constant operation because insertion of a smaller node is constant as is deletion of the current smallest node. Otherwise insertion and deletion are linear operations, but the requirements say nothing about their time complexity. QED

Well, the inserts and deletes in the general case are not really done in constant time - I don't think the answer is so easy...


Thanks anyway!

Maybe they were speaking of average case efficiency, not worst case. You have 'random' insertions and deletions. On any deletion the probability that the minimal element is deleted is 1/n, assuming elements are distinct, where n is the size of the list. Then it only takes O(n) operations to scan through the list and recompute the minimal element. On average, this will be an O(1) cost per deletion.

(It would help to have more details about the question. How are elements 'added' or 'deleted' from the list? If the list is used like a stack or queue, with insertions and deletions on the ends, it is certainly possible to keep track of the minimal element in constant time.)

>Well, the inserts and deletes in the general case are not really done in constant time
And you didn't require that they needed to be done in constant time. If you want an accurate answer then stop paraphrasing and give us the exact problem that was given on the exam. Chances are good that you're missing an important element that gives us a loophole for a trick, much like how I was assuming that maintaining the smallest node didn't include constant time insertions and deletions.

So... the precondition for this linkedlist in add() should be that the first element in the list is always the minimum element in the list.

add(3)

3

add(10)

3, 10

add(1)

1, 3, 10

add(5)

1, 5, 3, 10


you see, when you add, you compare the element you're adding with the one at the beginning. if bigger, add after the first element. if smaller, add this element as the first in the list.

constant time, because you will always make one comparison and you will always add. linkedlist always has an addFirst() method of constant time.

*thumbsup*?

*EDIT*

NVM, i didn't read the question in it's entirety. it looks like it's not as easy.

It's a pity you didn't read the post dates either