Jump list

Jump list

In computer science, a jump list is a data structure which resembles an ordered doubly linked list. Instead of only "next" and "previous" links, several nodes contain links to nodes farther away, with the distance increasing geometrically. This allows the dictionary operations "search", "insert" and "delete" to be executed in O(3√"n") time.

ee also

* Dictionary
* Linked list
* Skip list

References

*
* Arne Andersson and Thomas Ottmann, [http://user.it.uu.se/~arnea/ps/andetigh.ps "New Tight Bounds on Uniquely Represented Dictionaries"] , SIAM Journal of Computing, 24(5):1091-1103, 1995.


Wikimedia Foundation. 2010.

Игры ⚽ Поможем сделать НИР

Look at other dictionaries:

  • Jump search — In computer science, a jump search or block search refers to a search algorithm for ordered lists. It works by first checking all items L km , where k in mathbb{N} and m is the block size, until an item is found that is larger than the search key …   Wikipedia

  • List of terms relating to algorithms and data structures — The [http://www.nist.gov/dads/ NIST Dictionary of Algorithms and Data Structures] is a reference work maintained by the U.S. National Institute of Standards and Technology. It defines a large number of terms relating to algorithms and data… …   Wikipedia

  • List of role-playing video games: 1990 to 1991 — Part of a series on …   Wikipedia

  • Jump Start (comic) — Jump Start is a daily comic strip by cartoonist Robb Armstrong. Armstong attended Syracuse University, where in 1982 he created a popular comic strip in the student newspaper The Daily Orange . That strip was called Hector and its main characters …   Wikipedia

  • Jump Off Entertainment — is an independent record label that was started in Kissimmee, Florida in 2001 by Rishard Big Dawg Brown and rapper Christopher Choppa Hill Pinellas. Jump Off was ignited by Choppa Hill s single 420 (Bout 2 Get It). The song was an underground… …   Wikipedia

  • Jump Start Records — is an independent record label based out Philadelphia, Pennsylvania run by Jeremy Myers. They began as a punk, ska, and hardcore mailorder distro in 1994 and released their first record in 1996 from the Montreal ska band The Planet Smashers. Jump …   Wikipedia

  • Jump Records — was a subsidiary of Island Records. See also * List of record labels …   Wikipedia

  • List of MADtv cast members — List of cast members = The following is a complete list of cast members which includes both featured and repertory players. The dates given are the dates of the season in which they first appeared as a player and the season when they left. Cast… …   Wikipedia

  • List of people connected to Gothenburg — List of notable people connected to Gothenburg, Sweden.*Deathstars, Cybergoth Industrial Metal group *Jan Eliasson, former Swedish Minister of Foreign Affairs *Ace of Base, pop group *Daniel Alfredsson, captain and MVP of the NHL s Ottawa… …   Wikipedia

  • List of California companies — includes notable companies that are, or once were, headquartered in California.0–9* 20th Century Fox * 23andMe * 24 Hour FitnessA* ABM Industries * ACC Capital Holdings * AECOM * AMD * Accelrys * Accept Software * Activision * Actuate Corporation …   Wikipedia

Share the article and excerpts

Direct link
Do a right-click on the link above
and select “Copy Link”