Topic : Introduction to Linked Lists
Author : Shadow Mint
Page : 1 Next >>
Go to page :

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:

-> 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 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

Page : 1 Next >>