Building a Linked List in Python with Examples
Tags: python, computerscience, languages, mailinglist
Published: 2021-01-17 18:26:18

---
title: Building a Linked List in Python with Examples
published: true
date: 2021-01-11 14:30:52 UTC
tags: Python,ComputerScience,Languages,MailingList
canonical_url: https://qvault.io/2021/01/11/building-a-linked-list-in-python-with-examples/
---

 ![writing a todo list](https://qvault.io/wp-content/uploads/2021/01/list.jpeg "list")

The post [Building a Linked List in Python with Examples](https://qvault.io/2021/01/11/building-a-linked-list-in-python-with-examples/) first appeared on [Qvault](https://qvault.io).

A linked list is a linear data structure where elements are not stored next to each other in memory. The elements in a linked list are linked using pointers or references. Linked lists are an ordered collection of objects, similar to a normal list. Linked lists stand apart from lists in how they store elements in memory. While regular lists (arrays or slices) use a contiguous memory block to store references to their data, linked lists store references (pointers) as part of each element.

![array vs linked list](https://qvault.io/wp-content/uploads/2021/01/difference-between-arrays-and-linked-list-1024x431.jpg "difference between arrays and linked list")<figcaption><a href="https://www.faceprep.in/data-structures/linked-list-vs-array/" target="_blank" aria-label="source (opens in a new tab)" rel="noreferrer noopener nofollow">source</a></figcaption>

A normal list is just a pointer to the first element in the list, and a specific item can be retrieved by providing a memory offset.

A linked list is also just a pointer to the first element in the list, but memory offsets won’t do us any good. We need to examine the first element’s `next` pointer to see where the next item is, then we can navigate to it. From there, we can find the next item and so on down the list.

## Python linked list example

### Node Class

First, we’ll build a `Node` class. The `LinkedList` class we eventually build will be a list of `Node`s.

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

    def set_next(self, node):
        self.next = node

    def  __repr__ (self):
        return self.val
```

Each node has a `val` data member (the information it stores) and a `next` data member. The `next` data member just points to the next `Node` in the list if there is one, otherwise it’s `None`

### Linked List Class Constructor

```
class LinkedList:
    def  __init__ (self):
        self.head = None
```

The constructor is easy – just initialize an empty `head` pointer. This indicates we now have an empty list.

### Iterating over the list

Let’s make it easy to iterate over each item in the list using python’s `for _ in _` syntax.

```
def  __iter__ (self):
        node = self.head
        while node is not None:
            yield node
            node = node.next
```

By implementing Python’s ` __iter__ ` method, we can now use iteration syntax. For example, `for item in linked_list:`.

## Adding to the list

Let’s create a way to add items to the tail of the list, the `add_to_tail` method. It takes a node as input, iterates over the entire list, then adds the given node to the end.

```
def add_to_tail(self, node):
        if self.head == None:
            self.head = node
            return
        for current_node in self:
            pass
        current_node.set_next(node)
```

### Removing from the list

There are other ways to remove items from the list, but for now, and as an example, let’s write a `remove from head` method.

```
def remove_from_head(self):
        if self.head == None:
            return None
        temp = self.head
        self.head = self.head.next
        return temp
```

`remove_from_head` removes and returns the first item from the list, assuming one exists.

### Printing the linked list

Last but not least, we can implement Python’s ` __repr__ ()` method so that we can call `print()` directly on a list and control what it printed. Here’s a representation I like:

```
def  __repr__ (self):
        nodes = []
        for node in self:
            nodes.append(node.val)
        return " -> ".join(nodes)
```

This method will print each node’s value in order, with arrows in between. For example, `hello -> this -> is -> my -> list`.

### Usage

```
linked_list = LinkedList()
linked_list.add_to_tail(Node('john'))
linked_list.add_to_tail(Node('sally'))
linked_list.add_to_tail(Node('jimmy'))
print("ll:", linked_list)
first = linked_list.remove_from_head()
print("removed:", first)
print("ll:", linked_list)
```

## Full Linked List Code Example

```
class LinkedList:
    def  __init__ (self):
        self.head = None

    def  __iter__ (self):
        node = self.head
        while node is not None:
            yield node
            node = node.next

    def  __repr__ (self):
        nodes = []
        for node in self:
            nodes.append(node.val)
        return " -> ".join(nodes)

    def add_to_tail(self, node):
        if self.head == None:
            self.head = node
            return
        for current_node in self:
            pass
        current_node.set_next(node)

    def remove_from_head(self):
        if self.head == None:
            return None
        temp = self.head
        self.head = self.head.next
        return temp

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

    def set_next(self, node):
        self.next = node

    def  __repr__ (self):
        return self.val

```

## Thanks For Reading!

Take [computer science courses on our new platform](https://app.qvault.io/)

Follow and hit us up on Twitter [@q\_vault](https://twitter.com/q_vault) if you have any questions or comments

[Subscribe](https://mailchi.mp/5c7f5c281bbe/qvault-newsletter-subscribe) to our Newsletter for more programming articles