Linked Lists

By now, you hopefully have some understanding of how memory works. Python, however, tries to hide memory management details as much as possible, so it’s understandable if the concepts aren’t perfectly clear. We also need to be careful with terminology, as Python sometimes uses standard terms in non-standard ways.

Python is built on top of a lower-level programming language called C. Every line of Python is interpreted into C code, which is then run. Why do this? C is very fast, but is slow to program in. Python is much slower (due in part to imperfectly-optimized translation to C), but is much faster and easier for the programmer. What this means is that we need to understand a bit about how languages like C work to understand all the things Python is hiding from you.

Normally, when you create a variable, the system allocates a small chunk of memory for it.

It’s also possible to allocate a large, contiguous block of memory that can hold many items. This is called an array.

The way we access elements in a Python list is similar to how one accesses elements in an array. (This is because Python’s list type is implemented as fancy ideas on top of C arrays, creating what’s called a dynamic array. We’ll learn later about all these fancy tricks.)

A key concept is that every piece of memory has an address—a number that describes its location. We can store the address of one variable inside another. A variable that stores an address is called a pointer.

Pointers allow us to construct many powerful data structures.

However, there is another way to create a list: a Linked List.

A linked list is built from a simple object called a Node. A Node has two properties:

1. data: The value stored in the node.

2. next: A pointer to the next Node in the sequence.

To form a list, we link these nodes together. We keep a head pointer to the first node, and the next pointer of the final node is set to None to signify the end of the list.

The basic code for a Node and a LinkedList class looks like this:

class Node:
    """A single node in a linked list."""
    def __init__(self, data=None):
        self.data = data
        self.next = None

class LinkedList:
    """A linked list structure."""
    def __init__(self):
        self.head = None

A linked list can do everything an array list can (insert, overwrite, access elements in order, etc.), but the performance characteristics are different.

Consider inserting an element at the front of the list. In a linked list, this is a simple, three-step process:

# Inside the LinkedList class
def insert_at_front(self, data):
    new_node = Node(data)
    new_node.next = self.head
    self.head = new_node

This operation is always three steps, regardless of the list size, making it a constant time or \(O(1)\) operation. In an array list, however, inserting at the front requires shifting every existing element one position to the right. If there are n elements, this takes n steps, making it a linear time or \(O(n)\) operation. This performance difference is significant.

On the other hand, consider what is necessary to access the \(i\)th element of a linked list. You must start at the front, and iterate along until you get to that element. That’s \(O(n)\). With arrays, accessing an arbitrary element is \(O(1)\). For example, here is code to print the data of every element of a Linked List:

# Inside the LinkedList class
def access(self):
  temp = self.head
  while temp is not None:
    print(temp.data)
    temp=temp.next

and here’s to print the \(i\)th element:

# Inside the LinkedList class
def access(self,index):
  temp = self.head
  for i in range(index):
    temp=temp.next
  return temp.data

Finishing touches

In most “complete” linked list implementations (like Python’s deque), there are a couple more elements to make things a little easier:

• Node classes have both next and prev pointers. The prev points at the Node that precedes this Node. prev of the head is None. This is easily implemented with no runtime penalty to any function.

• Linked lists have not only a head pointer, but also a tail pointer which points at the last Node in a linked list (and, like head, is None if the linked list is empty). This point, along with the one above it, makes it so that the front and back of the linked list are equally accessible, and you can iterate in either direction. The linked list is perfectly symmetric. This is also easily implemented with no runtime penalty.

• An additional field is added to store the number of nodes in the linked list. It starts at 0, and every time a Node is added, the length is incremented. Every time a Node is removed, the length is decremented. Now, when a user wants the len() of the list, rather than being an \(O(n)\) count of Nodes (see why?), it’s merely a check on that stored value, which is \(O(1)\).

As an example, here’s the beginning of an implementation of this:

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

class LinkedList:
    def __init__(self):
        self.head = None
        self.tail = None
        self.length = 0

    def add_to_front(self, data):
        new_head = Node(data)
        if self.head is None:
            self.tail = new_head
            self.head = new_head
        else:
            new_head.next = self.head
            self.head.prev = new_head
            self.head = new_head
        self.length += 1

    def __len__(self): #this is the function called when you do len(my_ll)
        return self.length #O(1), because we can just return this value

Final runtimes

These runtimes are not to be memorized, they are to be understood - we’ll have too many runtimes to just memorize, it’s important we be able to think them through.

• Accessing the first or last Node, adding a Node to the front or back, or removing a Node from the front or back are all \(O(1)\).

• Accessing an arbitrary node is \(O(n)\).