There are many more data structures than the common ones we have studied so far. Arrays, linked lists, stacks and queues are all built in to the standard library of most programming languages, including Java.
Today we will look at four slightly more exotic structures that Java does not come with. The first is for specialized cases, and the others address specific performance requirements.
One advantage of learning data structures is that you can build things like this that your language does not come with, should you ever have the need to.
The idea behind a circular linked list is that, instead of having the last node's next link to null, it links back to the first node, making a loop. Likewise, the first node's previous links to the last node:
The point of this data structure is that we can loop through the list forever, and repeat the nodes over and over again. The list could be singly-linked or doubly-linked (as shown above), but won't generally have a "tail" node.
Circular linked lists are useful when you want to repeatedly loop through a set of data. For example:
A self-organizing list tries to address one of the flaws of a linked list, which is that they are not efficient to search. In an array, we can use the binary search algorithm. But with a linked list, we must use sequential search and visit each node in turn.
A self-organizing list is identical to a normal linked list in its structure. The difference comes in how it is used.
The idea is that, whenever we search for a piece of data, we move it to the front of the list. That way, if we search for it again, we will find it much more quickly next time. This will only be effective if we think we will search for the same items repeatedly.
Essentially, the front of the list acts as a "cache" for our most recently used items. The back of the list will come to store items we haven't searched for recently.
Unrolled linked lists try to address another flaw with linked lists, which is that they are not as efficient to loop through as arrays.
An unrolled linked list stores an array of data elements in each node instead of just a single value. For instance, let's say we use arrays of size 10. The advantage of this is that, most of the time, we will be looping through an array to get to the next element, and only sometimes using the links.
The arrays do not have to be full, they could have only a few elements filled. When we add elements, we add to one of the arrays in a node. When a node gets full, we will insert a new node into the linked list, either before or after the node we are in. Then we will need to shuffle some array elements into the other array.
Essentially an unrolled linked list is a trade-off between an array and a linked list:
A skip list is another data structure that attempts to address one of the flaws in linked lists, this time that they are slower to search than arrays.
The idea is that, normally in a linked list you must loop through each element in turn, which limits you to linear search. In a skip list you can "skip over" some of the elements. In addition to the normal links taking you from one node to the next, there are "express lanes" that only hit some of the nodes in the list:
A skip list is a probabilistic data structure which means that we use randomness and probability into its design. In this case, we have some probability, $p$, that a link will be included into the layer of links above it.
For example, if we use .5 as the probability, then there will be a 50% chance that a link will be in the second layer. Then another 50% chance that that link will be included up in the top layer, and so on.
If we are using $p = .5$, then when inserting a piece of data into the skip list, this is what we do:
Now, we can use a variant of binary search on this data. You begin in the "fast lane" on top, and keep going until you would overshoot the item you are searching for. When that happens, you drop down a level and repeat the process. Eventually you will find the item you are looking for without having to loop through the whole list.
For example, the figure below shows how we could search for "J" in this skip list:
Copyright © 2019 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.