Linked List

In another post, I talked about how an array can be used to implement a list ADT. Another way to implement the ADT is with a linked list, the implementation of which relies on pointers or memory references. Hence, to do a linked list, first and foremost, you have to understand the concept of pointers.

A pointer is a variable that stores the address of another variable. To understand this, consider a person as a variable. Suppose a gal named Betty stores a certain integer value, say the latest sales figure. Betty is then a 'normal' variable, one that hold an actual value of interest. Now consider a certain guy named Mat. He does not hold such value. He cannot tell you what's the latest sales count. He can however point you to Betty; he knows Betty's address and hence can point you to her. Mat is a pointer variable.

In C or C++, we can declare a pointer mat pointing to an integer variable betty as shown in the example below:

int betty;
int *mat = &betty;

'&' is to be read as address of, and 'int *' as 'pointer to integer'. Hence mat is a pointer to integer that stores the address of betty.

In a language such as Python, there is no explicit syntax for pointer or address. However, objects such as list or dict in Python are all implemented as pointer variables, and so when you do a copy operation such as follows, you are really copying addresses, not the actual data.

a = [1,2]
b = a

If you change the value of b, eg. with a statement such as follows:

b[0] = 5

the corresponding value in a will change too, since a and b have the same address.


Now, imagine this. Suppose each person has 2 values. One is an actual value, say his/her sales figure, and another is a pointer value that points to another person. We can achieve this in C or C++ with a struct that looks something like as follows:

struct Salesperson {
    int sales;
    Salesperson *next;
    }

There is no struct in Python, but we can use a dict to achieve a similar effect:

betty = { 'sales': 0, 'next': None}

Hence, as shown in the picture below, Alif holds a sales value and at the same time, he points to Mat. Mat holds his own value and he is pointing as well to Betty. What we get is a linked list.

A linked list consists of nodes (the persons above), linked up by pointers. The first node in the list (Alif in the pic), is the header. The last node (Betty) points to no other node (in python, we write it as None). What we have in the computer memory is something like as follows:

Unlike an array, consecutive locations in a linked list is unlikely to be in contiguous memory location, as shown below:

Operations on Linked List


Now, consider 2 basic operations on a linked list: 1) inserting a new node, and 2) deleting an existing node. We have of course to start from nothingness - a blank linked list, one where the header points to nothing:

In Python, this blissful state of nothingness would be created as follows:
header = None

Insertion into an Empty List

Naturally, the only meaningful operation in this state is the addition of a new node. Now suppose a node 'Ben' to be inserted:



ben = {'name': 'Ben', 'next': None}

Note that I choose to focus on just 2 fields  - a name and a pointer that points to the next node. The next value here is None since 'Ben' is by itself. To make 'Ben' be part of the list, since the list is still empty, all we need to do is to make header points to it:

header = ben




Insertion at the Head

Now suppose we have another node to be added:

alif = {'name': alif, 'next': None}



'Alif' can be after 'Ben' in the list, or it can be before, but to maintain an alphabetical order, it should of course be in front. We check on this with the following conditional:

if header['name'] > alif['name']:
 



If the above condition is true, and it is of course true, then we need to do some stitching: stitch the nodes together such that 'Alif'' is pointing to 'Ben', and header is pointing to 'Alif'.  One must be careful not to break up the list. The following order of action is correct:

• make 'Alif' points to 'Ben'
• make header points to 'Alif'

Why would it not work if you were to reverse the order of the operations?

Inserting at the End

Suppose now we have a node 'Charlie' to be inserted into the list:

You note that 'Charlie' is not less than the node currently pointed to by the header. So insertion at the head is out of question.You need to do some hard work then; track through the list to find the rightful position for 'Charlie'. You note that 'Alif' is not the last node..

and that the next node do not have a name greater than 'Charlie'. 

So you move on to 'Ben'. You can see that 'Ben' is currently last in the list. It means that ''Charlie' will be the new last.

It's simple to insert a node to the end of a linked list. Simply point the next var in the current last node to the node to be inserted, as shown below:

Insertion Somewhere in Between

We now a list of 3 nodes. Let's go further - we shall add one more node, 'Bung'.

Again, we start by placing a tracker at header, and we check if 'Bung' deserves to go in front there. It does not. So we start to iterate through the list until we find the right spot. We note that 'Alif' is not the last node, and the next node is not with a name bigger than 'Bung'.

So we move the tracker to the next node, and apply the same check. This time, with the tracker at 'Ben', we do note that the next node will be with a name bigger than 'Bung'. So we know that 'Bung' must be inserted between the current node and the next.

So some stitching work needs to be done here. We first stick 'Bung' to next node - 'Charlie' -,as shown below:

Then we make 'Ben' point to 'Bung' instead of to 'Charlie':

We are done here.