Home CPSC 340

Linked List Variations

 

Overview

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.


 

Circular Liked List

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:

In this linked list diagram, the last node has an arrow back to the first
node, and the first node has an arrow connecting to the last node
A circular linked list

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:


 

Self-Organizing Lists

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

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.

This linked list contains an array of 10 slots in each node, instead
of just a single box for data
An unrolled linked list

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:


 

Skip Lists

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:

The linked list contains three levels of links for each piece of data.
The first level has a link to each node.  The middle has a link to about
half the nodes, and the top has a link for about a quareter.
A skip 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:

  1. Insert the data.
  2. Insert the links on the bottom level of links.
  3. Flip a coin. If it's heads, insert the links on the second level, otherwise stop.
  4. Flip a coin. If it's heads, insert the links on the third level, otherwise stop.
  5. ...

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:

The links used to search for J are highlighted.  We traverse
the top layer of links until it runs out, then drop down to the next,
and so on until we get to J.
Searching a skip list

Copyright © 2019 Ian Finlayson | Licensed under a Creative Commons Attribution 4.0 International License.