Back

Linked lists - further study

Introduction
We know that a linked list is a way a computer can keep a set of data in a predefined sequence. It is usually given as an example of a ‘dynamic data structure’ because its size can shrink and grow, unlike a static data structure such as an array. However, linked lists can also be implemented within an array structure. A truly dynamic linked list data structure would use pointers to an area of free space in the main memory called known as the ‘heap’. This is a record of free memory locations that can be used by any program as they need them. When a new location is required, an address can be fetched from the heap. When an item is deleted from a list, the memory location can be returned to the heap for use by other applications. We will look at algorithms that use a linked list in an array. It is a dynamic data structure, in that it can grow and shrink, but is not truly dynamic because the structure is held in a table (an array), so its size is predefined - there are limits to how much it can grow by. Just to remind you of what we said in an earlier chapter, the key features of linked lists are:

    • the head of each sequence of data is held in a 'Head of lists' area of memory
    • the head points to a node, where the first piece of data (assuming there is one) can be found
    • each node is made up of a piece of data and a pointer
    • the pointer points to the memory location where the next node can be found
    • the end of a list is signalled by a 'null pointer' . (We've used xxx.)

Do note that the data in a linked list can be stored all over the memory. They don’t have to be stored together in one block of memory. In the next example, memory locations 200, 132, 621 and 834 have been used. This leads to a very efficient use of memory because you can use up all of the gaps between other applications and data files! The downside of this, however, is that they can be slow structures to search through, not only because the data isn’t together but also because you have to serially search through a linked list. That means you have to start at the beginning of the list and work your way through the nodes to find any particular item. In a static structure such as an array, you can access data items directly, without going through all of the other items. For example, here is a linked list of degree courses held alphabetically.

llist1

Creating a new linked list from an old one
So far, we know that:

    • linked lists are dynamic data structures
    • each item in the list is known as a node
    • each node has a data part and a pointer part to it
    • linked Lists must have a start pointer held in the Head of Lists
    • linked lists must have a Null pointer
    • the Null pointer signals the end of the list.

A Linked List is a data structure. You set up the structure by writing programming code. As with any data structure in software, there will be times when you want to do some operations on it. These can include finding a piece of data in the structure, inserting a piece of data, deleting it, printing out all or some of the data items in a structure, re-organising the structure to create new structures and so on. Consider this example. Suppose I want to keep a Linked List of these students (Name, Age, Course) in ascending alphabetical (StudentList) order: Smith, 31, Maths; Holmes, 21, English; Sip, 19, History; Kaur, 50, Maths. Here is one way of representing what I want to do (Note that I have picked any ‘free’ memory addresses that were available to use, even though they weren't next to each other):

llist2

Another (easier?) way of showing this is diagrammatically:

llist3

Notice the introduction of a new pointer - the NEXTFREE pointer. It simply points to the next available node, the next memory location that could be used to store a data item if I needed to add an item to the linked list. If you start deleting nodes, the NEXTFREE pointer will become important because it will allow you to reuse deleted nodes, rather than leaving unrecoverable space in the data structure. In fact, it is possible to have a linked list of all the free spaces available! So you actually have two linked lists in a data structure - one for the data and one for the free nodes. If I wanted to set up a linked list of free space, I would have the start of the free space pointer in the head of lists pointing to memory location 1. Memory location 1 would point to 5. 5 would point to the next free space, and so on until the null point is reached. We’ll see this again later in this chapter. In the ‘linked list of students’ example, I could print out quickly a list of the students in alphabetical order. I can do that becauseI can follow an alphabetical path. However, I can't easily and quickly get back all the pupils who are doing a Maths course. I don't have a path to follow for that. I don’t have a linked list of Maths pupils. I need to create one from my existing list! How do you describe how this can be set up in software, in pseudo-code or otherwise? The idea is that you create a new head of list in your 'Main Index' table and then you create a new set of pointers to follow!

    • You get the pointer from the head of the linked list you want to create a new one from.
    • You check the list isn’t empty by seeing if it is the null pointer.
    • You follow the pointer to the first node.
    • You test the data in that node.
    • If it needs to be part of the new list, then you add it to the new list, adjusting pointers as necessary.
    • Else you follow that node’s pointer to the next node, and repeat, until you come to the end of the list.
    • The final job is to give the last node in the new list the null pointer.

A pseudo-code way of writing this might be as follows:

llist4

A diagrammatic representation of the second list would look like this:

llist5

If you want a list of all pupils, you get the START (StudentList) and follow the first pointers. If you want a list of all maths pupils, you get the START (MathsList) and follow the second pointers.

Adding an item to a linked list
Imagine we have a linked list of car manufacturers that we want held in alphabetical order. Imagine that we have decided to keep this information in a linked list. So far, we have entered 4 items. Our linked list looks like this:

llist6

Suppose we want to delete the item Ford, how could we do it? We would simply need to move pointers around. The actual data item Ford will still be in the table! However, no other data item will actually point to it! Refer back to chapter 18 if you are stuck!

More on managing free space
In the previous example, Ford was deleted. That made memory location 3 free. The question now is how to reclaim that memory location. How can we signal to the computer that memory location 3 is now available to use? Managing free space in a linked list is important. We need to keep track of which memory locations are free, or become free, so that we can add new data items to the linked list. If a data item is removed from a memory location in a linked list then we must not only remove it from the linked list of data but we must also add it to a linked list of free space! If we didn’t do this, memory locations would be lost to the computer! This would not be a very efficient use of our RAM.

An example of managing free space
We will use the example of car manufacturers in alphabetical order. The empty linked list looks like this:

llist7 

Notice that even though there is nothing in the linked list, a linked list of all the available free space exists! After inserting 4 car
manufacturers, we have:

llist8

Can you see that there are two linked lists, one for the data items and one for the free space? Notice that there is a null pointer for the end of the linked list of data items and also a null pointer for the end of the linked list of available free space!

Inserting data
Now we understand how free space is managed, we are in a position to write some algorithms to insert data. We will also need to consider special cases in the algorithm. For example what happens when there is no more free space available, what happens if the item is the first one in the list to be inserted and what happens if the linked list is completely empty, waiting for the first item to be inserted. Suppose we need now to insert Saab into the car manufacturer’s list. The basic algorithm would be:

    • Put Saab in the position pointed to by NEXTFREE.
    • Change NEXTFREE so that it contains the next value in the linked list of free items.
    • Starting at the head of lists, determine where Saab should fit in to the linked list of data.
    • Change Saab's pointer so that it points to Skoda.
    • Change Peugeot's pointer so that it points to Saab.

Special cases
With any algorithm you write, you should always ask yourself what the special cases are and then add pseudo-code to your algorithm to take these into account. 

    1. What happens if there is no free space available? At the beginning of the algorithm, check that the free linked list is not empty. If it is, report an error message and then stop.
    2. What happens if the item to be inserted is the first one in the list? Before you check where a new piece of data should go, check to see if the pointer at the HEAD OF LIST is the null pointer. If it is, then set the pointer     of NEWDATA to be the null pointer and set the pointer at the HEAD OF LIST to point to NEWDATA, then stop.
    3. What happens if an item to be inserted needs to go in the first position? Put the NEWDATA into the position pointed to by NEXTFREE. Change the HEAD OF LIST to point to NEWDATA. Make NEWDATA point to the second item. The trick with remembering all of this is not to try and remember algorithms! You should draw yourself a little linked list, with a few data items in it. Then run through the process of inserting a new item, writing down each step in your algorithm as you go.

Deleting and amending a data item

llist9

Suppose you want to delete Ford from the list of car manufacturers. The algorithm might look something like this:

    • Follow the pointers until you find Ford.
    • Change Fiat's pointer to point at Skoda.
    • Change Ford's pointer to point to NEXTFREE.
    • Change NEXTFREE to point to Ford.

Amending Data
The algorithm is:

llist10

Back