Back

Linked lists - an introduction

Introduction
A linked list is an example of a data structure, a structure that a programmer sets up in code. Once set up, the programmer can then add data to it, search for data in it and find data in it to amend or delete. Linked lists are dynamic data structures - they shrink and grow, depending on how much data needs to be stored. They can be an almost unlimited size, although they are often set up inside an array, which is in some programming languages a fixed size.

How linked lists work
A programmer wants to store a list of fish alphabetically in a linked list data structure. We want to store Carp, Perch, Roach and Shark. Below is an illustration of how the computer works with a linked list. The programmer will initialise the data structure in the program (in pseudo-code below) but they will have no idea what actual memory locations are selected by the computer when the program is translated. For illustration purposes, however, we will select a range of memory addresses. We will select a range of memory addresses only to illustrate that, in a linked list, the individual pieces of data can be all over the available RAM!

    • The computer will store the beginning of the list in an area of RAM we will call the Head of Lists.
    • We will call the memory location that holds where to find the first piece of data the START(FISH).
    • If the computer looks at the contents of the START memory location, it will show it the memory location of the first node. A node is a piece of data plus the address of the next node. It’s memory location 2300!
    • The computer can then go to memory location 2300, and it will find the data item Carp!
    • Not only that, however. It will also find the memory location of the next piece of data, 400.
    • If the computer goes to memory location 400, it will find the next node; it will get the next piece of data, Perch, as well as the memory location of the next piece of data, 9930, and so on.
    • At some point the computer will get to the end of the list. When it gets to the last piece of data, the pointer at that node is given a null value - it is given a value that is not a valid memory address e.g. XXX

If you are having trouble working out what is going on, then a diagram might help!

llista

A diagram showing a linked list is characterised by 4 things:

     1) The head of the list. (This points to the first node).
     2) Pointers to nodes. (They either point at the next place to look for a node or contain a null value).
     3) Nodes (A node is a memory location that contains a piece of data and another memory location).
     4) A null pointer. (This indicates the end of the list. We have used XXX).

Note also that linked lists can make use of any spare memory addresses going. If, for example, the computer had two applications running in RAM, separated by a couple of empty RAM addresses, it could make use of that little bit of memory in a linked list. The memory addresses don't have to be next to each other. Linked lists can help a computer ensure that memory is used wisely!

Algorithms for linked lists
When you store sets of data, whether the data structure is an array, a linked list or any other structure, there will be times when you need to do things with it! For example, you might want to:

    • Search for a data item.
    • Add a data item.
    • Delete a data item.

It would be useful to write algorithms to describe how we could do the above. We know that an algorithm is simply a set of step-by-step instructions that describe how to do a particular task. Algorithms can be written in semi-English, or pseudo-code! When writing algorithms, you should first concentrate on getting the logic correct and then start dealing with any special cases.

Searching for a data item in a linked list
To search for a data item ALPHA in a linked list, we could write out a description.

Start by getting the pointer in the Head of Lists. Then we need to test the pointer to see if it is the null pointer – it might be an empty list. If it is, we need to report that the list is empty and stop. If it isn’t, we need to follow the pointer to the first node. (Remember, a node contains a data item and another pointer). We need to look at the data item at that node. Is it the one that we are looking for? If it is, then we can report that we have found the data item and stop. If it isn’t we need to get the pointer at the node. We then check it because if that pointer is the null pointer we need to report that the data item we are looking for is not in the list and stop. If it isn’t the null pointer, we need to go to the node pointed at by this pointer and repeat. We keep doing this until either we find the data item or we come to the end of the list.

There is nothing wrong with the above description, although it is not so easy to code up into a programming language because there is no indication of programming structure in the description. It is written as an English paragraph. If we use pseudo-code, however, we can use programming structures, which makes converting the design into real code easy! On top of that, pseudo-code is language-independent. That means a programmer expert in any language should easily be able to convert pseudo-code into their particular language. With pseudo-code, we can make up any keywords we like so long as they broadly describe what we want to do. An algorithm written in pseudo-code to search for an item in a list might look like the following. As you study the algorithm, there are a number of things to note about it:

    • Some Boolean variables have been used to store whether some events have happened or not.
    • All IF and WHILE statements have a corresponding ENDIF or ENDWHILE statement to aid clarity.
    • Programming constructs were used to aid the step from pseudo-code to writing in actual code.
    • Indentation, meaningful variable names and comments help the reader follow the logic of the code.
    • Special cases e.g. if the list is empty in the first place, if data isn't present in the list.

Here is the algorithm. See if you can follow it:

llistc

Adding a data item to a linked list
The following algorithm describes how to add a new data item BETA to a linked list.

llistd

For example, suppose the computer needed to add Salmon to the linked list of Fish. The computer inserts Salmon in memory
location 850. A diagrammatic representation of the result would look like this:

lliste

Notice how the pointer at Roach's node has been changed to point to Salmon's location, and the pointer for Salmon has been set to the memory location that was pointed to by Roach's node.

Deleting a data item from a linked list
The following is an algorithm for deleting an item in a linked list.

llistf

For example, suppose the computer needed to delete Perch from the linked list of Fish. This diagram describes the process.

llistg

Notice that Perch is still in memory location 400. It's just that no pointer points to it anymore so it is not part of the linked list. The computer will keep a record of memory locations that have been freed up, and may at some point overwrite the contents of those memory locations when they are needed again. Also notice that the pointer in the node Carp has now changed. Some further points about linked lists.

    • Inserting data and deleting data is straightforward compared to arrays. If you are storing data in an array in an organised manner and you want to insert or delete an item, then you need to actually move the data items in the array to new locations to maintain the proper order. You don't have to do this with linked lists. You just find the appropriate place and then adjust appropriate pointers.
    • To find a piece of data in a linked list, you have to traverse through all the nodes in a serial fashion. This can be slow compared to a direct access data structure, such as an array.
    • Linked lists grow and shrink depending on how much data is stored. There are no blocks of memory that have been reserved in RAM as there are with arrays. Linked lists therefore use RAM more efficiently.
    • With arrays, you reserve space when the program is compiled. This doesn't happen with linked lists. It's possible you might not be able to store what you want to with a linked list data structure!

Back