Back

Creating a linked list in Python

Introduction
A linked list is a collection of data items that have positions relative to other data items in the list. The items can be in some kind of order, such as ascending or descending, or they can be unordered. We are going to use Python to create a simple linked list of unordered data items and then carry out some common operations on it. A linked list has a head, which is the start of the linked list and holds a pointer that points to the first node in the list (or a null pointer, if the list is actually empty). A node holds two piece of information. The first piece of information is the actual data itself. The second piece of information is a pointer. This holds data that points to the next node. If there isn't a next node because it is the end of the linked list, then we will use a null pointer to signal this. Our null pointer will be shown by using xxx

Our approach to creating an unordered linked list
There are a number of ways we can implement a linked list. To keep things nice and simple, we will always add new nodes to the beginning of the linked list. For example, suppose we want to create a linked list by first adding Mark, then adding Zak, then Chris and finally Sue. This is an unordered list in the sense that the data isn't in alphabetical order, for example. No thought has been given to a logical ordering of the data items.

We would create an empty list to start with. The head would contain the null pointer.

list1

Then we add Mark.

list2

Then we add Zak.

list3 

Notice that Zak was inserted at the beginning of the queue. The pointer from the head was then changed so it pointed to Zak, and Zak's pointer was made to point at Mark. Now we need to add Chris.

list4

Finally, we add Sue.

list5

The node class
The first class we need is one to create node objects. A node will have two pieces of information, the data and the pointer. When we create a node, we will always assign the pointer to None to begin with. Both the data and pointer need a get method, to retrieve the data, and a set method, to assign a new value. We also of course need a constructor method. Here is our node class.

node

The linked list class
Next, we need a class to make linked lists. This will only be used to hold a reference to the first node object in our list. We will provide a constructor method to hold this information in a variable called head. We will also provide a method we can call to test if the list is empty, and one to actually add a new node object to a list. Here is our linked list class:

linked list

Line 33 creates a new linked list object using the linkedList class. Line 23 sets the self.head variable to None to start with, signalling an empty list. the method is_empty will return True if the linked list is empty.

Adding items to the linked list
The add method needs a little explaining. We will add Mark first, then Zak, then Chris and finally Sue using:

myList.add ('Mark')
myList.add ('Zak')
myList.add ('Chris')
myList.add ('Sue')

a) We add 'Mark' by calling  myList.add('Mark')
b) 'Mark' is passed to item on line 28.
c) A new node object is created on line 29 called temp, using the data 'Mark'. Initially, Mark's pointer is set to None by the constructor.
d) We then use temp's setPointer method on line 30 to set temp's pointer to point to whatever is in self.head. At the moment, it is set to None, as 'Mark' is the first piece of data to be added to the list.
e) Finally, self.head is assigned to point at Mark's node on line 31.

After adding Mark, our linked list looks like this:

list2

a) We add 'Zak' by calling  myList.add('Zak')
b) 'Zak' is passed to item on line 28.
c) A new node object is created on line 29 called temp, using the data 'Zak'. Initially, Zak's pointer is set to None by the constructor.
d) We then use temp's setPointer method on line 30 to set temp's pointer to point to whatever is in self.head. Now, it is set to point to Mark's node.
e) Finally, self.head is assigned to point at Zak's node on line 31.

After adding Zak, our linked list looks like this:

list3

a) We add 'Chris' by calling  myList.add('Chris')
b) 'Chris' is passed to item on line 28.
c) A new node object is created on line 29 called temp, using the data 'Chris'. Initially, Chris' pointer is set to None by the constructor.
d) We then use temp's setPointer method on line 30 to set temp's pointer to point to whatever is in self.head. Now, it is set to point to Zak's node.
e) Finally, self.head is assigned to point at Chris' node on line 31.

After adding Chris, our linked list looks like this:

list4

a) We add 'Sue' by calling  myList.add('Sue')
b) 'Sue' is passed to item on line 28.
c) A new node object is created on line 29 called temp, using the data 'Sue'. Initially, Sue's pointer is set to None by the constructor.
d) We then use temp's setPointer method on line 30 to set temp's pointer to point to whatever is in self.head. Now, it is set to point to Chris' node.
e) Finally, self.head is assigned to point at Sue's node on line 31.

After adding Sue, our linked list looks like this:

list5

Our final program looks like this:

##Creates a linked list

class Node:
    def __init__(self,data):
        self.data = data
        self.pointer = None

    def getData(self):
        return self.data

    def getPointer(self):
        return self.pointer

    def setData(self,newData):
        self.data = newData

    def setPointer(self,newPointer):
        self.pointer = newPointer


class linkedList:
    def __init__(self):
        self.head = None

    def is_empty(self):
        return self.head == None

    def add(self,item):
        temp = Node(item)
        temp.setPointer(self.head)
        self.head = temp

myList = linkedList()

myList.add ('Mark')
myList.add ('Zak')
myList.add ('Chris')
myList.add ('Sue')

Use a visualiser
If you are struggling to see what is happening, use a Python visualiser such as www.pythontutor.com to help you. Copy and paste the code into the visualiser and step through it, one line at a time.

Back