Talk:Skip list
From Wikipedia, the free encyclopedia
Contents |
[edit] Adversarial User
Why is the author concerned about 'adversarial users' messing with his data structures? Security through obscurity is not very secure anyway. Doesn't this discussion of security of data structures belong in a separate article?
- The "adversarial user" is a hypothetic user (think, evil demon), that knows exactly the order in which to execute operations on a data structure that would incur the worst possible run time of the execution of those operations. It is a common technique in algorithm analysis to think of your algorithm working against such an adversarial user. Sancho McCann 22:00, 10 February 2007 (UTC)
- See Adversary_(online_algorithm) and Competitive_analysis_(online_algorithm). Sancho McCann 01:53, 11 February 2007 (UTC)
[edit] Style
Wikipedia's manual of style has a section on writing in mathematics articles that I think applies here (see Wikipedia:Manual_of_Style_(mathematics)#Writing_style_in_mathematics). If we could remove the conversational style and have the article read more like an encyclopedia rather than a textbook, it would be an improvement to this article. Sancho McCann 22:02, 10 February 2007 (UTC)
[edit] ICS 23
The part about Jacobson could use a rewrite.
[edit] Skip Lists with two pointers
I wonder if it's possible to implement these cute Skip Lists using only TWO fields to navigate in it, i.e. "below" and "next", instead of the usually suggested FOUR including "above" and "before"...? However, I'm not sure how to handle the tower construction if one can't get levels up and nodes before a particular node. How about removing a node? Again, all the tower nodes need to be isolated, isn't that so? How do we do this, using only a "next" and a "below" fields? Could any expert comment on this?
Epsilon1 20:34, 1 April 2007 (UTC)
