Linked List in Python

An easy way to understand linked list

Subscribe to our newsletter and never miss any upcoming articles

Listen to this article

In this blog, we will discuss about how to implement Linked List in Python. We will also discuss its properties, advantages, and disadvantages.

I chose Python as the primary language to implement the linked list data structure because of its readability and the ease in implementing data structures.

wordpress-hints-linked-list-cover-google.jpg What is linked list?

Linked list is a linear data structure as well as a dynamic data structure. It consists of nodes where each node contains a data field(to store some data values) and a reference to the next node in the list.

You can think each of it's node as a container with two chambers. In one of the chambers you have a value, it can be an Integer or a String, and in other chamber you have an address of the next container (Node). It's that simple.

Here’s an image of a linked list: linked-list.png

THEORY PART:

Why use linked lists?

Linked list is often compared to arrays. Whereas an array is a fixed size of sequence, a linked list can have its elements to be dynamically allocated. What are the advantages and disadvantages of these characteristics? Here are some major ones:

Advantages:

  • No wastage of memory: It only allocates the memory required for values to be stored or inserted because size of the linked list increase or decrease at run time. So, there is no need to pre-allocate the memory.

  • Implementation of stack and queue: Linear data structures like stack and queues are often easily implemented using a linked list.

  • Easy to insert and delete a node: Insertion and deletion node operations are easily implemented in a linked list.

Disadvantages:

  • Memory Usage: More memory is required to store elements in linked list as compared to array. Because in linked list each node contains a pointer and it requires extra memory for itself.

  • Linear look up time: When looking for a value in a linked list, you have to start from the beginning of chain, and check one element at a time for a value you’re looking for. For example, if we want to access a node at position n then we have to traverse all the nodes before it. So, time required to access a node is large.

  • Reverse Traversing: In linked list reverse traversing is really difficult. In case of doubly linked list its easier but extra memory is required for back pointer hence wastage of memory.

ENOUGH TALK, LET'S IMPLEMENT IT:

CREATE A NODE CLASS:

# this Node class we will use to create multiple nodes(containers)
# for our linked lists
class Node:
    def __init__(self, value=None, next=None):
        self.value = value # head is the node from which your are pointing towards next node
        self.next = next # next is the next node where pointer is pointing

CREATE A LINKED LIST CLASS:

class LinkedList:
    # we only need head for linked list which will act
    # as a starting element, all the other elements we will insert using Node class
    def __init__(self):
        self.head = None

METHOD TO INSERT AN ELEMENT:

 def insert(self, element):
    # create a new node and assign an element which we're
    # receiving as an argument, to the value of that Node
    # assign our current head as the next element of the newly created node
    node = Node(element, self.head)
    # and make newly created node as the new head of our linked list
    # this method will insert the elements from left
    self.head = node

In above method as soon as we get an element which we have to insert in our linked list, we will create a new Node from it then simply shift our current head and make newly created node as our new head. So, that means for our newly created head the previous head will be the next node. (read that again and try to visualize)

Before testing our insert() method we have to create a helper method which will print our linked list.

METHOD TO PRINT THE LINKED LIST:

def print(self):
    # store our head in 'itr' variable
    # self.head is an entire Node which has value as well as next.
    itr = self.head
    linked_list = ''  # initialize 'linked_list' variable as type str

    # until our self.head is not None this while loop will run
    while itr:
        # concatenate the itr.value (value of the Node) to the 'linked_list' variable
        linked_list += str(itr.value) + " --> "
        # assign itr as the next element
        itr = itr.next
        # if there is no next element, itr will become None
    print(linked_list)

Let's insert some elements and print our linked list

lst = LinkedList()

lst.insert(1)
lst.insert(2)
lst.insert(3)
lst.insert(4)

lst.print()

Output:

4 --> 3 --> 2 --> 1 -->

As we insert 1 first it becomes our head, then after inserting 2, it becomes our new head and 1 (the previous head) becomes it's next node. same for 3 and 4.

METHOD TO CALCULATE THE LENGTH OF THE LINKED LIST:

def length(self):
    # store our head in 'itr' variable
    # self.head is an entire Node which has value as well as next.
    itr = self.head
    count = 0  # set count to 0
    while itr:
        # we will travel through our linked list till
        # we reach at the end where itr == None
        count += 1  # increase the count until there is an element i.e. itr != None
        # assign itr as the next element
        itr = itr.next
        # as soon as itr becomes None return the total count
    return count

Let's insert some elements and print the length of our linked list

lst = LinkedList()

lst.insert(1)
lst.insert(2)
lst.insert(3)
lst.insert(4)

print(lst.length()) # this will print 4 as we've inserted 4 elements

METHOD TO INSERT AN ELEMENT AT THE END OF THE LINKED LIST:

def insert_at_end(self, element):
    # first check if there is any head present
    # if there is no head that means the linked list is empty
    if self.head is None:
        # as linked list is empty simply create a node with received element
        # and assign it as our new head
        node = Node(element, None)
        self.head = node
        return
        # if head is present that means our linked_list is not empty
    itr = self.head
    while itr.next:
        # until there is next node present don't insert the value
        itr = itr.next
    # after reaching to the last node start inserting the values
    # here the itr is the last node of the linked list, simply insert a new node next to it
    itr.next = Node(element, None)

Let's insert some elements at the end of our linked list and print it out:

lst = LinkedList()

lst.insert_at_end(1)
lst.insert_at_end(2)
lst.insert_at_end(3)
lst.insert_at_end(4)

lst.print()

Output:

1 --> 2 --> 3 --> 4 -->

While inserting 1, the linked list is empty. So, it will assign 1 as the head of our linked list. After inserting 2, the linked list already has 1 as it's head so, it will look for the next node, as there is no next node it will place 2 next to 1. Same for 3 and 4.

METHOD TO INSERT AN ELEMENT AT PERTICULAR INDEX:

def insert_at(self, index, element):
    # first check if there is any head present
    # if there is no head that means the linked list is empty
    if self.head is None:
        print("linked list is empty")
        return

    # use self.length() to calculate the length (OOP stuff)
    if index > (self.length()):
        # index is greater than index of the last element
        print("index is out of range")
        return

    itr = self.head
    count = 0
    while itr:
        # stop before the index where we want to insert an element
        if count == index - 1:
            # and add the element next to it
            # e.g. if we want to insert an element at index 3
            # we will stop at 2 and insert an element next to it so
            # automatically the element will be at index 3 it's that simple
            itr.next = Node(element, itr.next)
            # make the node which is already present in that index
            # as next node of the element that we are inserting
            break
        itr = itr.next
        count += 1

Let's insert an element at particular index and print the linked list:

lst = LinkedList()

lst.insert_at_end(1)
lst.insert_at_end(2)
lst.insert_at_end(3)
lst.insert_at_end(4)

lst.print()  # printing before replacement

lst.insert_at(3, 45)

lst.print()  # printing after insertion

Output:

# output before insertion
1 --> 2 --> 3 --> 4 --> 

# output after insertion
1 --> 2 --> 3 --> 45 --> 4 -->

We want to insert 45 at the index 3 so we will stop at index 2 and insert 45 next to the node present at index 2 so automatically our element will be placed at index 3 and at the same time we will make previously present element at index 3 as next node of newly inserted element. (read that again and try to visualize)

METHOD TO REPLACE AN ELEMENT AT PERTICULAR INDEX:

def replace_at(self, index, element):
    # first check if there is any head present
    # if there is no head that means the linked list is empty
    if self.head is None:
        print("linked list is empty")
        return

    # use self.length() to calculate the length (OOP stuff)
    if index > (self.length()-1):
        # index is greater than index of the last element
        print("index is out of range")
        return

    # if head is present that means our linked_list is not empty
    itr = self.head
    count = 0

    # until itr is not None we will travel through the linked list
    while itr:
        # if count value is equal to the index that we are looking for
        if count == index:
            # replace that Node's value with the element that we've received in an argument
            itr.value = element
            break
        itr = itr.next
        # while travelling we will keep increasing the count
        # until we don't get count matching to the index
        count += 1

Let's replace an element at particular index and print the linked list:

lst = LinkedList()

lst.insert_at_end(1)
lst.insert_at_end(2)
lst.insert_at_end(3)
lst.insert_at_end(4)

lst.print()  # printing before replacement

lst.replace_at(0, 9)
lst.replace_at(2, 45)

lst.print()  # printing after replacement

Output: (read the comments in code snippet for explanation)

# output before replacement
1 --> 2 --> 3 --> 4 -->

# output after replacement
9 --> 2 --> 45 --> 4 -->

METHOD TO REMOVE AN ELEMENT AT PERTICULAR INDEX:

def remove_at(self, index):
    # if the index is 0, simply remove the head
    if index == 0:
        # assign node present next to the head as new head
        # so automatically our current head will be gone
        self.head = self.head.next

    itr = self.head
    count = 0
    while itr:
        # stop before the index where we want to delete an element
        if count == index - 1:
            # e.g. if we want to delete an element at index 3 we,
            # will stop at index 2 and will replace index 3 item as index 4
            # so that means item at index 3 is deleted
            itr.next = itr.next.next
            break
        itr = itr.next
        count += 1

Let's remove/delete an element at particular index and print the linked list:

lst = LinkedList()

lst.insert_at_end(15)
lst.insert_at_end(25)
lst.insert_at_end(35)
lst.insert_at_end(45)

lst.print()  # printing before removal

lst.remove_at(1)

lst.print()  # printing after removal

Output:

# output before removal
15 --> 25 --> 35 --> 45 --> 

# output after removal
15 --> 35 --> 45 -->

We want to remove 25 which is present at the index 1 so we will stop at index 0 and replace 25 with an element present at the index 2. (read that again and try to visualize)

METHOD TO GET AN INDEX OF A PERTICULAR ELEMENT:

def index_of(self, data):
    itr = self.head
    index = ''
    count = 0
    while itr:
        # if the value of the node is equal to the data that is passed
        # assign index as the value of the count at that time
        if itr.value == data:
            index = count
            break
        itr = itr.next
        # keep increasing the count until we get the matching value
        count += 1
    return index

Let's test this method:

lst = LinkedList()

lst.insert_at_end(1)
lst.insert_at_end(2)
lst.insert_at_end(3)
lst.insert_at_end(4)

print("index of 3 -->", lst.index_of(3))

Output: (read the comments in code snippet for explanation)

index of 3 --> 2

METHOD TO REMOVE AN ELEMENT BY THE VALUE:

def remove_by_value(self, data):
    itr = self.head
    while itr:
        # we will keep going through the list until
        # we get value matching to the passed data
        if itr.value == data:
            # first calculate the index by self.index_of() method
            index = self.index_of(data)
            # call self.remove_at() method to remove that value (OOP stuff)
            self.remove_at(index)
            break
        itr = itr.next

Let's test this method:

lst = LinkedList()

lst.insert_at_end(1)
lst.insert_at_end(2)
lst.insert_at_end(3)
lst.insert_at_end(4)

lst.print()  # before removal

lst.remove_by_value(3)

lst.print()  # after removal

Output: (read the comments in code snippet for explanation)

# output before removal
1 --> 2 --> 3 --> 4 --> 

# output after removal
1 --> 2 --> 4 -->

METHOD TO GET A VALUE AT THE PARTICULAR INDEX:

def value_at(self, index):
    itr = self.head
    count = 0
    value = ''  # initialize the value var
    while itr:
        # keep traveling through linked list and once you find
        # count == index, store value of that node in value variable
        if count == index:
            value = itr.value
        count += 1
        itr = itr.next
    # return value variable
    return value

Let's test this method:

lst = LinkedList()

lst.insert_at_end(10)
lst.insert_at_end(20)
lst.insert_at_end(30)
lst.insert_at_end(40)
lst.insert_at_end(50)

lst.print()

print("Value at index 2 --->", lst.value_at(2))

Output: (read the comments in code snippet for explanation)

# output of lst.print()
10 --> 20 --> 30 --> 40 --> 50 --> 60 --> 70 --> 

# output of lst.value_at(2)
Value at index 2 ---> 30

ASSIGNMENT:

  • Add error handling in above method i.e. "Index our of range" and "List is empty" error messages.

METHOD TO REVERSE A LINKED LIST:

def reverse(self):
    j = 0
    lst = []
    for i in range(self.length()):
        # first we will append all the values in the 'lst' var
        lst.append(self.value_at(i))

    for i in range((self.length() - 1), -1, -1):
        # replace an element at the last index of our LINKED LIST
        # with an element at the 0th index of the 'lst' var and second last
        # element of the LINKED LIST with an element at the 1st index of the 'lst' var and so on...
        self.replace_at(i, lst[j])
        j += 1

Let's reverse our linked list

lst = LinkedList()

lst.insert_at_end(1)
lst.insert_at_end(2)
lst.insert_at_end(3)
lst.insert_at_end(4)
lst.insert_at_end(5)
lst.insert_at_end(6)
lst.insert_at_end(7)

lst.print()  # before reversal

lst.reverse()

lst.print()  # after reversal

We will first append all the elements of our linked list in lst list so the lst list will be [1, 2, 3, 4, 5, 6, 7] then we will replace 1 of our linked list with 7 of the lst var, similarly 2 of our linked list with 6 of the lst var, and so on...

Output:

# output before reversal
1 --> 2 --> 3 --> 4 --> 5 --> 6 --> 7 -->

# output after reversal 
7 --> 6 --> 5 --> 4 --> 3 --> 2 --> 1 -->

I hope you have learned something new! If you found this article useful, be sure to share, follow and support!

Thank you for reading!

If you face any problems in any of the above methods, you can go ahead and check out the code on my Github.

Also, make sure to subscribe to our newsletter on blog.learncodeonline.in and never miss any upcoming articles related to programming just like this one.

I hope this post will help you in your journey. Keep learning!

My LinkedIn and GitHub .

No Comments Yet