A linked list is a fairly simple data structure, which is not natively supported by Python, because at first glance the standard Python list seems more powerful. However, for certain problems, linked lists are a more effective solution. This chapter explains how linked lists can be implemented, and how they are useful. An extra benefit is that explaining how linked lists work, will help understanding the next chapters on trees and graphs.

Referencing objects

Objects may reference other objects. You implement this by creating an object and assigning it to an attribute of another object. For instance, below I create a class Die, which you can roll, and a class DiceCup, which contains a four-sided and six-sided die, which you can use to roll the two dice.

from random import randint

class Die:
    def __init__( self, sides ):
        self.sides = sides
    def roll( self ):
        return randint( 1, self.sides )
    
class DiceCup:
    def __init__( self ):
        self.foursider = Die( 4 )
        self.sixsider = Die( 6 )
    def roll( self ):
        return self.foursider.roll() + self.sixsider.roll()
    
dicecup = DiceCup()
print( dicecup.roll() )

As you can see, the class DiceCup has two attributes, foursider and sixsider, for which it creates two instances of the class Die which it assigns to them. The question is: how are these two dice stored in an instance of DiceCup? The answer is: they are “references”, or “pointers”. What does that mean? It means that the two Die objects exist somewhere in the computer’s memory, and the DiceCup object contains the memory addresses of these two objects.

So, if I would make a change to one of these Die objects, for instance change the number of sides, that affects the results of the roll() method of the DiceCup object; however, it would not affect the memory addresses that reside inside the DiceCup object.

We say that the DiceCup object “links” to two Die objects.

References and values

If you are wondering which data types are stored as references and which as values: the answer is that all data types are stored as references (at least in Python 3). However, if an object has an attribute that is of an immutable data type, then even if it got its value by assigning a variable to it, its value will not change if you change the value of the assigned variable. I can imagine that this sounds confusing, so here is an example, whereby the DiceCup class has, besides two dice, also a capacity which is an integer.

from random import randint

class Die:
    def __init__( self, sides ):
        self.sides = sides
    def roll( self ):
        return randint( 1, self.sides )
    
class DiceCup:
    def __init__( self ):
        self.foursider = Die( 4 )
        self.sixsider = Die( 6 )
        self.capacity = 0
    def roll( self ):
        return self.foursider.roll() + self.sixsider.roll()
    
dicecup = DiceCup()
capacity = 12
dicecup.capacity = capacity
newdie = Die( 100 )
dicecup.foursider = newdie

capacity = 5
newdie.sides = 5
print( dicecup.capacity )
print( dicecup.foursider.sides )

The last four lines of the code above change the value of the variable capacity which was assigned to dicecup.capacity, and the value of newdie.sides, whereby newdie was assigned to dicecup.foursider. The printing in the last two lines shows that the capacity of dicecup has not changed, but the number of sides of the foursider attribute has. This is because capacity is an integer and integers are immutable, while newdie is an instance of the class Die, which is mutable. In principle all instances of classes that are defined by the programmer are mutable.

Linking objects

Linking objects to each other allows the creation of networks of interlinking objects, which can be used to represent the data structures which underlie numerous problems. One of the simplest is the single-linked list, which will be discussed next.