Introduction to Linked Lists

Introduction to Linked Lists
by Shadow Mint

This serves only as a simple introduction to linked lists; if you know a little about them, it might help clarify some things, or give you some ideas; if you know nothing, it should help you to understand them. If you're already familiar with linked lists, you are likely to find it very straight forward.

To start with, what is a linked list, why to use it, and why not to use it? Basically, a linked list is an array of connected objects, where each object is, if you like an independent variable. In this, it is very similar to an array, however, unlike an array, the objects are not bound into a single reference object. For example, and array of 20 items can all be referred to through the single variable containing them; a linked list, you have 20 different variables. It sounds like a waste of time and effort to do; manual implementation of an array. However, it does have certain advantages; if you want to increase the size of the list, you simply create a new variable. If you want to remove an item or change the order of the items, its easy to do. Additionally, you can have a list of objects which are: not the same type, and also, contain a large amount of data.

So, in terms of why you might want to use it, its very flexible, and dynamic. Ideal for things like items in a database index; which is size is not specifically know, or to represent events or units in a game; where the number of them at any time is uncertain. On the down side, linked lists have two major problems; firstly, they're more difficult to find elements in. Since you have n unique elements, with (typically) no specific index to find which one you require, in the worst case scenario, you have to actually check each one of the elements. Secondly, since most machines use virtual memory in some form to aid a smaller-than-required RAM, there is a time overhead in allocating and freeing elements as required / no longer required for the list; this is sometimes an issue for real time systems, where event lists quickly change, and you don't want to be stuck with a long allocation / free when you should be doing something important.

With that in hand, lets look at some common ways of organising linked lists; different people call them different things: I'm going to stick with: single linked, duel linked and multi linked. This is because it very accurately describes them. The idea of having all these independent variables is bad, because when you dynamically allocate them, you end up with a big list of variables, that simply cannot be sorted unless you use some kind of holder for each one... which defeats the purpose of using a linked listed. To overcome this, each of the objects is "linked" to a number of other objects. That is, each object has a number of links, each pointing one other object in the list. Thus, you can search through the list, by moving through the list, using links. This additionally allows you to order the manner in which the items are sorted, which is often significant.

The three main types of linked lists are: single link lists; where each object links to one other object; presumably to form a linear list of items; double linked lists, the same as the first type, but in which the searching position can go in either direction, up or down the list (significant; remember, links of this type only work in one direction). Finally, you can have multi linked lists, in which every item is linked to n other items, often forming a tree like hierarchical structure of nodes which makes finding data in the list easier.

Briefly, let me go through a couple of very simple linked list examples:

Let's talk in more specific terms about actually implementing a linked list. As previously mentioned, links only work in one direction. This is because of the nature of a) the variables, and b) the links, and how they are implemented;

// This is java specific; normally, we'd have to say temp2 = temp.nextunit,
// handles memory, so we don't need to.
// Temp now refers to the unit after the unit which has just been killed.
temp = temp.nextunit;

// We "reform" the chain of units, by replacing the memory location of the
// now deceased unit with the location of the next unit. That unit now
// effectively no longer exists.

current_unit.nextunit = temp;

Since this works, why you might wonder, would be bother to find multiple links? To illustrate this, Im going to jump straight to multi links for the second example, since if you can handle them, you can handle duel links easily.

For this example, we load a database structure from a single large file. Sure, we could store the size of a required array in the database, but in this case, we don't want to. Our structure is as follows:

public DbItemClass
{
  int length;
  String name;
  DbFileClass file;
  DbItemClass next;
  DbItemClass prev;
  DbItemClass dir;
}

This means, we can have a hierarchy in the database; exactly like a directory structure! For example, if you have the following directory structure:

C:\
-> windows
 --> temp
  ---> junk.c
  ---> data.c
 --> windows.exe
 --> system
  ---> telnet.exe
 --> old
-> program files
 --> mygames
  ---> doom
  ---> quake
  ---> c&C

We could represent that with a list of objects; each item is represented by a DbItemClass, and those which are files rather than just directories, are represented by an additional object; file, which will hold data on the file.

However, since we can see that c:\ holds both the windows, and program files directories, we need a way to do this: thus the dir link. This lets us start a new path, using that item as the base for the structure. For example here, the windows item would hold a dir linking to temp and system, while program files links only to mygames.

We use the prev and next structures to hold the next item in a directory; and here we get complicated:

A directory entry has only a next and prev link; the others are Null (or 0), which means they link to nothing. This is a dangerous pitfall. If you ever attempt to find the address or element of an item they holds a null pointer you will cause your program to crash.

However, a directory with content also has a valid dir link: which points to the first element of that directory. The first element of that directory could possibly also be a directory: so we cant link backwards using that link; we could create another link object; DownDirectory or something to hold this, but its easier to just push the value into prev; which means you can always trace back simply through prevs, to the very first element of the directory (which will be the only the element to have a prev link equal to Null).

Now let us consider two things: firstly searching for the file "C:\windows\system\ping.exe" to do this, the easiest way is to split the request up into a number of different items; separated by the "\" so we get: "C:", "windows", "system" and "ping.exe". We can now search for each piece at each level; iterativly refining the search. A normal check reveals the base item (C:\) is not called "C:". Thus we return "no such item to the user".

That would be silly however; so we run a special check for the first item, and if it is "C:" we accept that. Then we move up one level. Now we're searching for "windows": and wow! It's the first item! We move our current_position object up to the next level of the structure and look for "system" now the first item is not that...so we move to the next (note this means we are looking at windows.exe, not junk.c). This doesn't match either. So we move to the next... and there. Found a "system" Move up it and look for "ping.exe". However! The next pointer on the "telnet.exe" structure is null: so we know we have reached the last element of this directory, with out a find for the last element we're seeking; so we have to return a no such item.

Secondly, let us consider removing an item; the directory system is to be removed, but we want to keep telnet.exe; so we decide to drop it into the parent directory. The links here have to be very carefully kept intact (by (object name) I refer to a variable holding the address of the object with object name in it):

// Get the address of the object to remove
temp = (windows.exe).next;

// We want to keep telnet.exe, so we get that object too
temp2 = temp.dir;

// And finally we get the object after the one we want to remove;
temp3 = temp.next;

// Now rebind the chain, the next pointer now points to telnet.exe
(windows.exe).next = temp2;

// And replace the null pointer in telnet.exe by pointing it to the
// "old" directory
temp2.next = temp3;

// Finally we finish the chain by making the "old" directory point back to
// the telnet.exe, rather than the now deleted object.
temp3 = temp2;

Or in short form, get rid of the temporary variables:

(windows.exe).next.next.prev = (windows.exe).next.dir;
(windows.exe).next.dir.prev = (windows.exe);
(windows.exe).next.dir.next = (windows.exe).next.next;
(windows.exe).next = (windows.exe).next.dir;

This might be confusing; but it just cuts out the temps. For easy of reading and understanding code; either a) comment vigourly in your code, or b) use some kind of temporary variable.

These two examples should demonstrate the basic workings of a linked list. From here, lets move on to develop a generic class (a simple one mind you, but none the less), for holding a linked list. To start with, we need to choose what manipulators we want for the list. For example:

* add element (n)
* remove element (n)
* empty list
* create base object
* fetch element (n)
* set element (n)

These six basic manipulations allow for all the functionality you might want from a simple linked list. We could now go and implement that in c++, or java. However, since I don't particularly like c++, and java automatically handles memory, we'll settle for stand c for this example (which may be more complicated, but so be it).

We start by creating a class structure, to hold these manipulations, along with the base object.

typedef struct
{

} LLClass;

Now we need contents: for this, we're going to need seven basic items: pointers to hold the functions which will perform these tasks, and the base element pointer for the class. Since we want to be generic, we'll have to make some kind of generic structure for the base element as well:

struct LinkST
{
  long ID;
  void *data;
  struct LinkST *next;
  struct LinkST *prev;
}

// ...and just typedef it for easy reference.
typedef struct LinkST LinkTD;

This is a very basic link structure; all it contains is an identifier, a pointer for the data and two pointers for the links (this is a duel link linked list).

So for our LLClass we'll have:

// The base object
LinkTD *baseobj;

// Add an empty element
LinkTD *(* add_element) (LLClass *class, int n);

// Remove an element
int (* remove_element) (LLClass *class, int n);

// Free the list
int (* empty_list) (LLClass *class, );

// Create the base object
LinkTD (* create_list) (LLClass *class, );

// Set element n to element
int (* set_element) (LLClass *class, LinkTD *element, int n);

// Return element n
LinkTD *(* fetch_element) (LLClass *class, int n);

Now, when ever we create a new LLClass, we're going to have to set the values in it. We'll do this in some simple function like: initLLClass (), which simply sets the pointers for all of the functions (eg. myList.empty_list = (* empty_list);). Note how each of the function also takes an LLClass argument. Since the functions need to access the items in the class, they need to have access to the class. Thus running a function should be something along the lines of:

(* myClass.set_element) (myClass, new_val,-1);

(Note: If you've never learnt how to do pointers to functions this may be slightly difficult to understand. Look it up; many places on the net cover this topic)

I'm not going to go through the code for these functions, only a basic algorithm for each one. It is important to check each time, that the base object is not null, because if it is, any attempt to access it will cause a fault. In general, the functions return 1 on happy completion, and 0 on failure; unless they return a pointer, in which case NULL is returned on failure. Make special note of the empty list function! This is very important to avoid memory leaks in.

* add element (n)

return value = 0

if (class.baseobj != NULL)
  goto the nth element
  calloc one new LinkTD (so all values default to 0)
  connect links
  return value = pointer to new object
end-if

return the return value


* remove element (n)

return value = 0

if (class.baseobj != NULL)
  goto the nth element
  temporary = point to that element
  connect links on adjacent objects
  free temporary
  return value = 1
end-if

return the return value


* empty list

return value = 0

if (class.baseobj != NULL)
  goto the last element
  move back to the first element, freeing each next element
  free the baseobj
  baseobj = NULL
  return value = 1
end-if

return the return value


* create base object

return value = 0

// Here we make the opposite check, since a massive memory leak will
// occur if the baseobj is not null when a new one is created
if (class.baseobj == NULL)
  calloc one new LinkTD (so all values default to 0)
  baseobj = pointer to new object
  return value = pointer to new object
end-if

return the return value


* fetch element (n)

return value = 0

if (class.baseobj != NULL)
  goto element n
  return value = pointer to that element
end-if

return the return value


* set element (n)

return value = 0

if (class.baseobj != NULL)
  goto element (n - 1)
  temporary = pointer to next element
  next pointer of this element = insertion element
  reconnect links
  return value = 1
end-if

return the return value

Finally, note that we could also add functionality to sort the list and search the list using the identifier... there are also a huge number of other possibilities for things to do. Generally, every linked list is different. With any luck, this articles has given an understandable introduction into how they work. Good luck in doing what ever it is you do. =)

...and I must apologise for not making the full source avaliable for these algrothims, as I implemented them, but my exams are keeping me kinda tied up. Sorry.

Discuss this article in the forums

Date this article was posted to GameDev.net: 1/19/2001
(Note that this date does not necessarily correspond to the date the article was written)

See Also:
General
Sweet Snippets