# 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.

![](variable.png)

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

![](test.png)

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**.

![](pointer.png)

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.

![](ll.png)

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.

![](ll2.png)

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

```python
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:

```python
# 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:

```python
# 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:

```python
# 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`](https://docs.python.org/3/library/collections.html#collections.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:

```python
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)$.