This is not funny! Skiplist is essentially an optimized version of Doug's idea that ends up using a logrithmically scaling vector of pointers. Secondly, linked lists in real scenarios make sense only when there is some satellite data associated with the keys. So maintaining just pointers gives you speed at the cost of relatively small memory.
Updates/deletes can cause problems in this approach but more often than not keys themselves are never updated. Updates are processed by delete followed by insert. Deletes are easy to handle, follow a pointer and if it points to null then the value is not found. That said, raw implementation of Doug's idea is not recommended. Intelligence on how many different nodes you need to point to, how far apart they need to be, how many need to be changed if there is a change in the underlying order etc should be used and skiplist is one provably efficient scheme giving you that. On Wed, Jun 11, 2008 at 12:33 PM, Geoffrey Summerhayes <[EMAIL PROTECTED]> wrote: > > > > On Jun 11, 12:09 pm, "Douglas Diniz" <[EMAIL PROTECTED]> wrote: > > Well, if you have a classic linked list, O(n) is the best for you. But > you > > can do better if you have a sorted linked list. In every node keep a > vector > > of pointers for all other nodes. Then you can simulate a binary search. > > > > LOL ... Ummm, this IS a joke, right? > > --- > Geoff > > > > --~--~---------~--~----~------------~-------~--~----~ You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to algogeeks@googlegroups.com To unsubscribe from this group, send email to [EMAIL PROTECTED] For more options, visit this group at http://groups.google.com/group/algogeeks -~----------~----~----~----~------~----~------~--~---
