Building Linked Lists

To begin our study of linked lists in Python, let's start with the algorithm for constructing a linked list from scratch.

A linked list string

To guide our study of linked lists, we will work with a string that is represented as a linked list of characters. Each node will contain a single character, and the linked list as a whole represents a string:

In Python, strings are implemented using arrays of characters. However, using a linked list representation of a string will allow us to learn the basics of manipulating linked data structures with a familiar data type.

The linked list as a whole will be represented using an LLString object. Each individual node of the list will be represented using a Node object. We can define Node to be a class nested within the LLString class:

class LLString:
    class Node:
        def __init__(self, val, next):
            self.val = val
            self.next = next

    def __init__(self):
        self.head = None

The LLString constructor simply initializes the head of the linked list to None. In order to actually add some nodes to the linked list, let's write a new method in this class.

Adding a node to a linked list

Watch the video below to see how to add a node to the beginning of a linked list:

Appending a node to a linked list

What if we wanted to add a node to the end of the list? We have two options:

1. Starting at self.head, iterate all the way to the end of the list and add a node.
2. Maintain a reference to the end of the list (the tail), so that we can quickly add a new node.

We will see how to iterate down a linked list to do (1) in the next lesson. For now, let's focus on (2). To start, we will need to create self.tail in the LLString constructor, and also make sure that the prepend() function sets it when the first node is added to the list:

class LLString:
    class Node:
        def __init__(self, val, next):
            self.val = val
            self.next = next

    def __init__(self):
        self.head = None
        self.tail = None

    def prepend(self, new_val):
        new_node = LLString.Node(new_val, self.head)
        self.head = new_node
        if self.tail is None:
            self.tail = new_node

Now that we have self.tail, watch the video below to see how to add a node to the end of a linked list:

Converting a string to a linked list

To make our work with LLString easier, let's update the constructor so that it converts a Python string to an LLList. To do so, we can make use of our new append() method:

def __init__(self, s):
    self.head = None
    self.tail = None

    for char in s:
        self.append(char)

With this, we can create new linked lists with a single call:

str1 = LLString('hello')

Putting it all together, here's our current version of the LLString class:

class LLString:
    class Node:
        def __init__(self, val, next):
            self.val = val
            self.next = next

    def __init__(self, s):
        self.head = None
        self.tail = None

        for char in s:
            self.append(char)

    def prepend(self, new_val):
        new_node = LLString.Node(new_val, self.head)
        self.head = new_node

        if self.tail is None:
            self.tail = new_node

    def append(self, new_val):
        new_node = LLString.Node(new_val, None)

        if self.tail is not None:
            self.tail.next = new_node
        self.tail = new_node

        if self.head is None:
            self.head = new_node