Variations On the Theme

Quick Note

A linked list is a linked list is a linked list. That part doesn't change. However, with a small adjustment, you can create a linked list that can work a little differently. The following represent a couple of examples.

The Doubly Linked List

As you recall, a linked list has two fundamental components: 1) The data to be stored, and 2) a reference to a potential next node. However, there is no law that says you cannot have other links. For example, you could have a second reference that references a previous link. Consider the following.

Like all linked lists, it must have a head reference, and to iterate between nodes, you will need a working reference. However, consider the following code.

    // move from node with 'C' to node with 'B'
    wkgRef = wkgRef->prevRef;

    // move from node with 'C' to node with 'D'
    wkgRef = wkgRef->nextRef;

This adds some overhead since the node data has to have another reference variable but if you need to be able to easily move either direction in a linked list, this is the tool for you.

The Circularly Linked List

This is an interesting linked list if you need to roll back over to the beginning of your list smoothly. Consider the following.

Note that a head reference is still required since you still need to find the first node, but once you are in the list, you can iterate across it as many times as you like. When you insert at the "end" of the list, you just make sure to set its next reference is to the head reference so it refers to the first item in the list. As mentioned, you can use this when you simply need to follow the list continuously and the "beginning" or "end" are not critical themselves. A good example of using this could be in a queue data structure where the beginning and end change regularly.

Different Approaches To The Same Data Structure

This brief topic provides you with a couple of alternatives to the linked list data structure. All data structures can be tweaked in various ways to make them more useful for some given operation and these are a good example of that. One more time, linked lists are just not difficult to deal with, or even modify, as along as you have your paper and pencil out in front of you as you figure out what you want to do. Keep at it.