6.1 Introduction to Linked Lists#

We have seen that Python lists are an array-based implementation of the list ADT and that they have some drawbacks: inserting and deleting items in a list can require shifting many elements in the program’s memory. For example, we saw that inserting and deleting at the front of a built-in list takes time proportional to the length of the list, because every item in the list needs to be shifted by one spot.

This week, we’re going to study a completely different implementation of the List ADT that will attempt to address this efficiency shortcoming. To do so, we’ll use a new data structure called the linked list. Our goal will be to create a new Python class that behaves exactly the same as the built-in list class, changing only what goes on in the private implementation of the class. This will mean that, ultimately, code such as this:

for i in range(n):
    nums.append(i)
print(nums)

will work whether nums is a Python list or an instance of the class we are going to write. We’ll even learn how to make list indexing such as nums[3] = 'spider' work on instances of our class!

A LinkedList class#

The second class we’ll use in our implementation is a LinkedList class, which will represent the list itself. This class is the one we want client code to use, and in it we’ll implement methods that obey the same interface as the built-in list class.

Our first version of the class has a very primitive initializer that always creates an empty list.

class LinkedList:
    """A linked list implementation of the List ADT.

    Private Attributes:
    - _first: The first node in this linked list, or None if this list is empty.
    """
    _first: _Node | None

    def __init__(self) -> None:
        """Initialize an empty linked list.
        """
        self._first = None

Linked list diagrams#

Because each element of a linked list is wrapped in a _Node object, complete memory model diagrams of linked lists are quite a bit larger than those corresponding to Python’s array-based lists. For example, the following is a diagram showing a linked list named linky with four elements, in order 109, 68, 71, 3.

Linked list memory model diagram.

While memory model diagrams are always a useful tool for understanding subtle memory errors—which certainly come up with linked lists!—they can be overkill if you want a quick and dirty linked list diagram. So below we show two stripped down versions of the memory model diagram, which remove all of the “boilerplate” type and attribute names. The first one keeps the “item” references as arrows to separate memory objects, while the second goes a step further in simplification by writing the numbers directly in the node boxes.

Linked list abstract diagrams.