LogList

What is LogList? LogList is a complex but efficient data structure implemented as a Java package. It is designed to provide users a simple way to store all types of data for quick retrieval, no matter how large the list gets.

How do you make it quick? Most lists require O(n) lookup - that is, if you store twice as much data, it takes twice as long on average to access any one piece of it. LogList makes a tradeoff - it takes more RAM than a simple list, but as a result has an O(log n) lookup - If you square the amount of data, it takes twice as long on average to find a single piece. This is possible because LogList is what's known as a "skip list" - it skips over a large number of unimportant entries on its way to the requested data. Below image, created by Stefankoenze, is considered public domain; more info

A graphical representation of a Skip List

Why not use other quick-lookup structures, such as Arrays? The main advantage of LogList is that not only does it look up elements in O(log n) time, it can add elements in that time as well. With an array, adding a new element can be extremely costly, especially if the array is full. As well as this, arrays require a separate sorting algorithm to provide answers in order - LogList automatically alphabetizes all of its data, making many functions easier with no penalty towards performance.

Where can I get LogList? You can download LogList here.