Examples to show for Circular Linked Lists and Skip Lists

I would like to ask for your ideas on wh开发者_如何学编程at type of programs or even techniques in which I can better explain the usefulness of the theory of Circular Linked Lists and Skip Lists to my peers.

My programming belief is that one can grasp a concept better if you give them examples and metaphors.

Just your idea of sample programs to create or solutions (programming technique or algorithm).

Cheers!

A good use for circular linked lists is a job scheduling system where each job gets a certain amount of time with a given resource (such as processes in a simple operating system).

In that case, it makes little sense to have a specific head since you're always cycling around the list, all you need is the current pointer. You can add new jobs after the current one and use current to locate one for deletion. Advancing to the next job is a simple:

current = current->next

A possible skip list is a dictionary in list form. You maintain a pointer to the first word a and it contains a normal pointer to aardvark and a skip pointer to baa ^*a.

^*a: I actually don't know if they're the correct words but they should be close, and you'll hopefully get the idea.

Skip lists are basically an additional set of lists (or really links) placed on top of a regular sorted linked list to assist in searching through the list.

Skip lists create a kind-of binary search tree on top of the regular linked list, so that search operations take O(log N) time instead of O(N), making them faster. You would use them anywhere you would want to use a regular linked list, but need faster access.

The following page has a really nice, easy-to-follow discussion on skip lists: http://igoro.com/archive/skip-lists-are-fascinating/

From Wikipedia:

A circularly linked list may be a natural option to represent arrays that are naturally circular, e.g. the corners of a polygon, a pool of buffers that are used and released in FIFO order, or a set of processes that should be time-shared in round-robin order. In these applications, a pointer to any node serves as a handle to the whole list.

An easy to visualize example of how a circular list works might be to imagine a group of people standing in a circle where each person only knows the name of the person to his left. Thus to search for a person in the group, you start with the first person (an arbitrary person in this case) and move to the person he know the name of (i.e. to his left) until you find who you are looking for or come back to the first person again. Adding or removing a person to this group is simply done by placing/taking away a person from the circle and changing the name known by the person to his right (and telling him the name of the person to his left if it is an add). I hope this example makes sense, it is basically the way I used to visualize it when I was learning about linked lists.

Skip Lists support fast (O(log(n))) operations and can be used as a sorted data structure - much like balanced binary search tree. This makes them useful wherever we need fast data insert/remove times (like a linked list but unlike array) and also have fast access times (like an array but unlike in a linked list). They are also good for making fast range queries (e.g. find the sum (or max, min, product, etc.) of all elements in indices [i,j] of the structure).

I cannot think of a sufficiently simple real world metaphor for a skip list, the data structure looks quite more intricate than anything I can expect to see with objects in everyday life. But the wikipedia explanation is quite clear and working through the proof and algorithm for building it should be a good starting point. Here's a link to the original paper which is also quite readable IMO.