# Everything About Linked List Data Structure in Python: Intermediate Guide

**PyShark**, and kindly contributed to python-bloggers]. (You can report issue about the content on this page here)

Want to share your content on python-bloggers? click here.

In this article we will focus on a complete walk through of a Python linked list data structure.

**Table of Contents**

- What is a linked list
- How to create a linked list in Python
- How to traverse a linked list in Python
- How to insert a node at the end of a linked list in Python
- How to insert a node at the beginning of a linked list in Python
- How to insert a node after a given node of a linked list in Python
- How to search a node in a linked list in Python
- How to delete a node from a linked list in Python

## What is a linked list

A linked list is a data structure that consists of nodes, where each nodes contains two fields:

- Value
- Pointer (reference link) to the next node

It is a collection of nodes which make a sequence using the pointers, where the first node of the linked list is called the **head node**, and the **last node** has a reference link to NULL.

## How to create a linked list in Python

We already know that a linked list is a sequence made from nodes.

The first step to creating a linked list is to create a structure of a node (as its own class).

When initialized, a node should take some data to use as the value, as well as have a default pointer to next node set to None, which will be changed as we add more nodes together to form a sequence.

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

To test the code, let’s create a node that will have a value equal to 5, and print out the value and the pointer to next node:

first_node = Node(5) print(first_node.data) print(first_node.next_node)

And you should get:

5 None

As we expected, the values stored is *5* and reference link to next node is *None*.

Let’s go ahead and create a few more individual nodes:

second_node = Node(7) third_node = Node(15)

At this point we have three nodes which are not connected to each other: **first_node**, **second_node**, **third_node**.

The next step is to create a structure for a linked list (as its own class).

When initialized, a linked list should only have the head node set to NULL, in order to start an empty linked list:

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

To start adding nodes to a linked list we want the **first_node** we created to be the **head node** of the linked list:

llist = LinkedList() llist.head = first_node

This will create a linked list with one node (which will be the **head node**).

Recall that each node has a reference link set to NULL. In order to create a sequence of nodes, we will set each reference link to point to the next node:

llist.head.next_node = second_node second_node.next_node = third_node

And now we have successfully created a linked list with three nodes which should look like this:

In this section we have been adding nodes to the linked list rather manual than programmatically. In the next sections we will explore to to insert nodes at the end, and the beginning, and at a specific position of the linked list.

## How to traverse a linked list in Python

In the previous section we created the linked list **llist** and now we would like to traverse the linked list and print out values of each node.

Recall that the initial construction of linked list is given by:

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

A singly linked list can only be traversed in forward direction.

The logic is fairly simple: we will start at the **head node**, print its current value, and move to the next node (given that the reference link is not NULL).

We will continue moving to the next node as long as the node has data in it.

In this section we will implement a method **print_llist()** for traversing a linked list and printing values of each node for the **LinkedList()** class.

def print_llist(self): current_node = self.head while current_node is not None: print(current_node.data) current_node = current_node.next_node

It will be added as a method of the **LinkedList()** class:

class Node: def __init__(self, data): self.data = data self.next_node = None class LinkedList: def __init__(self): self.head = None def print_llist(self): current_node = self.head while current_node is not None: print(current_node.data) current_node = current_node.next_node

Let’s test create the same list as in the previous section and print out the values of each node:

llist = LinkedList() llist.head = first_node llist.head.next_node = second_node second_node.next_node = third_node llist.print_llist()

And you should get:

5 7 15

## How to insert a node at the end of a linked list in Python

In the one of the previous sections we showed an example of how to create a linked list in Python.

The approach we used was rather manual then programmatic because we had to manually link the nodes together and add reference links to the next node.

In this section we will implement a method **insert_at_end()** for inserting nodes at the end of a linked list (basically appending new nodes) for the **LinkedList()** class.

Let’s reuse the linked list we have built in the previous section:

class Node: def __init__(self, data): self.data = data self.next_node = None class LinkedList: def __init__(self): self.head = None def print_llist(self): current_node = self.head while current_node is not None: print(current_node.data) current_node = current_node.next_node

In order to add nodes at the end of the linked list in Python, we should follow a logic that is similar to traversing the linked list in Python.

We start at the **head node**:

- if the
**head node**exists, then we move to the next node - if the
**head node**is NULL, then the node we want to add becomes the**head node**

Assuming that the **head node** exists, we move to the next node (given that the reference link is not NULL).

We will continue moving to the next node as long as the reference link is pointing to another node that has a value and it’s not the **last node** (with reference link NULL).

Once we reach the **last node**, we will insert the new node right after it, and have its reference link as NULL.

In this section we will implement a method **insert_at_end()** for inserting nodes at the end of a linked list for the **LinkedList()** class.

def insert_at_end(self, data): new_node = Node(data) if self.head is None: self.head = new_node return last_node = self.head while last_node.next_node is not None: last_node = last_node.next_node last_node.next_node = new_node

It will be added as a method of the **LinkedList()** class:

class Node: def __init__(self, data): self.data = data self.next_node = None class LinkedList: def __init__(self): self.head = None def insert_at_end(self, data): new_node = Node(data) if self.head is None: self.head = new_node return last_node = self.head while last_node.next_node is not None: last_node = last_node.next_node last_node.next_node = new_node def print_llist(self): current_node = self.head while current_node is not None: print(current_node.data) current_node = current_node.next_node

Now let’s try to create the same list as in the second section of this tutorial and see if we get the same results:

llist = LinkedList() llist.insert_at_end(5) llist.insert_at_end(7) llist.insert_at_end(15) llist.print_llist()

And you should get:

5 7 15

which is exactly the same as when we created the linked list manually.

Using the **insert_at_end()** method we can add more nodes at the end of a linked list in Python.

## How to insert a node at the beginning of a linked list in Python

In the previous section we implemented a method to insert nodes at the end of a linked list.

But what if we need to add a node in the beginning of a linked list? That’s what we are going to cover in this section!

Inserting a node in the beginning of a linked list is much simpler from the logic and code perspective.

The very first node of a linked list is a **head node**, and if we need to insert a node before it, we should simply have a node that has a reference link to the **head node** (of course, if there are no nodes in the linked list, then the new node becomes the **head node**).

In this section we will implement a method **insert_at_beginning()** for inserting nodes at the beginning of a linked list for the **LinkedList()** class.

def insert_at_beginning(self, data): new_node = Node(data) if self.head is None: self.head = new_node return new_node.next_node = self.head self.head = new_node

It will be added as a method of the **LinkedList()** class:

class Node: def __init__(self, data): self.data = data self.next_node = None class LinkedList: def __init__(self): self.head = None def insert_at_end(self, data): new_node = Node(data) if self.head is None: self.head = new_node return last_node = self.head while last_node.next_node is not None: last_node = last_node.next_node last_node.next_node = new_node def insert_at_beginning(self, data): new_node = Node(data) if self.head is None: self.head = new_node return new_node.next_node = self.head self.head = new_node def print_llist(self): current_node = self.head while current_node is not None: print(current_node.data) current_node = current_node.next_node

Now let’s create the same list as in the previous section of this tutorial and and add a node with value “9” at the beginning of the linked list:

llist = LinkedList() llist.insert_at_end(5) llist.insert_at_end(7) llist.insert_at_end(15) llist.insert_at_beginning(9) llist.print_llist()

And you should get:

9 5 7 15

Using the **insert_at_beginning()** method we can add more nodes at the beginning of a linked list in Python.

## How to insert a node after a given node of a linked list in Python

So far in this tutorial we discussed how to add elements at the beginning and at the end of a linked list in Python.

In this section we will explore how to add elements after a given node of a linked list in Python.

When inserting a node after a given node, the first step is to find the **previous node** in the linked list.

In order to find the **previous node**, we will traverse the linked list from its **head node**, all the way until we find the **previous node**.

Once we find the **previous node**, we will change the reference link of a **new node** from NULL to the reference link of the **previous node**, and then we will change the reference link of the **previous node** to the **new node**.

In this section we will implement a method **insert_after_node()** for inserting nodes after a given node of a linked list for the **LinkedList()** class.

def insert_after_node(self, data, previous_node): new_node = Node(data) current_node = self.head while current_node.data != previous_node: current_node = current_node.next_node new_node.next_node = current_node.next_node currentnode.next_node = new_node

It will be added as a method of the **LinkedList()** class:

class Node: def __init__(self, data): self.data = data self.next_node = None class LinkedList: def __init__(self): self.head = None def insert_at_end(self, data): new_node = Node(data) if self.head is None: self.head = new_node return last_node = self.head while last_node.next_node is not None: last_node = last_node.next_node last_node.next_node = new_node def insert_at_beginning(self, data): new_node = Node(data) if self.head is None: self.head = newnode return new_node.next_node = self.head self.head = new_node def insert_after_node(self, data, previous_node): new_node = Node(data) current_node = self.head while current_node.data != previous_node: current_node = current_node.next_node new_node.next_node = current_node.next_node current_node.next_node = new_node def print_llist(self): current_node = self.head while current_node is not None: print(current_node.data) current_node = current_node.next_node

Now let’s create the same list as in the previous section of this tutorial and add a node with value “10” after the node with value “7” the linked list:

llist = LinkedList() llist.insert_at_end(5) llist.insert_at_end(7) llist.insert_at_end(15) llist.insert_at_beginning(9) llist.insert_after_node(10,7) llist.print_llist()

And you should get:

9 5 7 10 15

Using the **insert_after_node()** method we can add a node after a given node of a linked list in Python.

## How to search a node in a linked list in Python

We already know how to create a linked list, and let’s say we created a linked list in Python.

Now we would like to search a node in this linked list to check whether it exists.

The logic is fairly simple: we will start at the **head node** and start moving to the next node (node after node and given that the reference link is not NULL).

We will compare the values of each node with the value we are searching, and print “Node found” as soon as the node is found, or print “Node not found” if we traversed the linked list and didn’t find the value we are searching.

In this section we will implement a method **search_node()** for searching a node in the linked list for the **LinkedList()** class.

def search_node(self, data): current_node = self.head while current_node is not None: if current_node.data == data: print('Node found') return current_node = current_node.next_node print('Node not found')

It will be added as a method of the **LinkedList()** class:

class Node: def __init__(self, data): self.data = data self.next_node = None class LinkedList: def __init__(self): self.head = None def insert_at_end(self, data): new_node = Node(data) if self.head is None: self.head = new_node return last_node = self.head while last_node.next_node is not None: last_node = last_node.next_node last_node.next_node = new_node def insert_at_beginning(self, data): new_node = Node(data) if self.head is None: self.head = newnode return new_node.next_node = self.head self.head = new_node def insert_after_node(self, data, previous_node): new_node = Node(data) current_node = self.head while current_node.data != previous_node: current_node = current_node.next_node new_node.next_node = current_node.next_node current_node.next_node = new_node def search_node(self, data): current_node = self.head while current_node is not None: if current_node.data == data: print('Node found') return current_node = current_node.next_node print('Node not found') def print_llist(self): current_node = self.head while current_node is not None: print(current_node.data) current_node = current_node.next_node

Now let’s create the same list as in the previous section of this tutorial and search for the node with value “15”:

llist = LinkedList() llist.insert_at_end(5) llist.insert_at_end(7) llist.insert_at_end(15) llist.insert_at_beginning(9) llist.insert_after_node(10,7) llist.search_node(15)

And you should get:

Node found

Using the **search_node()** method we can search a node in a linked list in Python.

## How to delete a node from a linked list in Python

We already know how to search a node in a linked list in Python.

Now we would like to delete a node from a linked list in Python.

As you can imagine, the process will be similar to traversing a linked list and searching for a given node in a linked list.

The logic is fairly simple: we will start at the **head node** and check whether it’s the node we would like to remove:

- If yes, then we will repoint the
**head node**to the next node. - If no, then we will use it as current node, and check whether we want to remove the next node (the process continues node after node until we find the node to delete from a linked list).

In this section we will implement a method **delete_node()** for searching a node in the linked list for the **LinkedList()** class (this method assumes you are trying to delete a node that exists in a linked list).

def delete_node(self, data): current_node = self.head if self.head.data == data: self.head = current_node.next_node return while current_node.next_node.data != data: current_node = current_node.next_node current_node.next_node = current_node.next_node.next_node

It will be added as a method of the **LinkedList()** class:

class Node: def __init__(self, data): self.data = data self.next_node = None class LinkedList: def __init__(self): self.head = None def insert_at_end(self, data): new_node = Node(data) if self.head is None: self.head = new_node return last_node = self.head while last_node.next_node is not None: last_node = last_node.next_node last_node.next_node = new_node def insert_at_beginning(self, data): new_node = Node(data) if self.head is None: self.head = newnode return new_node.next_node = self.head self.head = new_node def insert_after_node(self, data, previous_node): new_node = Node(data) current_node = self.head while current_node.data != previous_node: current_node = current_node.next_node new_node.next_node = current_node.next_node current_node.next_node = new_node def search_node(self, data): current_node = self.head while current_node is not None: if current_node.data == data: print('Node found') return current_node = current_node.next_node print('Node not found') def delete_node(self, data): current_node = self.head if self.head.data == data: self.head = current_node.next_node return while current_node.next_node.data != data: current_node = current_node.next_node current_node.next_node = current_node.next_node.next_node def print_llist(self): current_node = self.head while current_node is not None: print(current_node.data) current_node = current_node.next_node

Now let’s create the same list as in the previous section of this tutorial and delete the node with value “5”:

llist = LinkedList() llist.insert_at_end(5) llist.insert_at_end(7) llist.insert_at_end(15) llist.insert_at_beginning(9) llist.insert_after_node(10,7) llist.delete_node(5) llist.print_llist()

And you should get:

9 7 10 15

Using the **delete_node()** method we can delete a node from a linked list in Python.

## Conclusion

This article is an introductory walkthrough for linked list data structure in Python and its functionality which is important to learn as they are used in many areas of programming and in machine learning.

Feel free to leave comments below if you have any questions or have suggestions for some edits and check out more of my Data Structures articles.

The post Everything About Linked List Data Structure in Python: Intermediate Guide appeared first on PyShark.

**leave a comment**for the author, please follow the link and comment on their blog:

**PyShark**.

Want to share your content on python-bloggers? click here.