Linked Lists in Python

A linked list is a data structure that shows how the nodes are connected in a sequence. Like stacks and queues, the memory of the linked list is not sequential. To overcome this, each node in the linked list contains two parts, a data part and an address part which holds the address of the next node. The main advantage of this data structure over stacks and queues is that the insertion/removal operations are easier and there is no need to pre-allocate memory.

We need to write a class for creating nodes to work on linked lists.

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

Now that we have created the node, let’s start building all the functionalities that can be done on the LinkedList. All the methods that are described henceforth must be present inside the LinkedList class defined below.

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

Let’s create a function to insert elements at the beginning of the linked list.

def insert_at_beginning(self, data):
    self.head = data

After adding elements at the beginning, we must also create a function to insert elements at the end. In this function we check if the list is empty, if not we traverse the whole list and then add the element at the last, else we set the new node as the head of the list.

def insert_at_end(self, data):
    if self.head is None:
      self.head = Node(data, self.head)
    else:
      itr = self.head
      while itr.Next:
        itr = itr.Next
      itr.Next = Node(data, None)

If the user sends multiple nodes as input, we convert the whole list of elements into a new linked list by adding each element to the end using the insert_at_end function.

def convert_list_to_linkedlist(self, data_list):
    self.head = None
    for value in data_list:
      self.insert_at_end(value)

Let us now define a function that counts the number of nodes present in the LinkedList by traversing the whole list of elements.

def get_length(self):
    count = 0
    itr = self.head
    while itr.Next:
      count += 1
      itr = itr.Next
    return count

We have seen how to insert elements at the beginning and the tail end. Let us now write a method that inserts elements in the middle. This is very easy in linked lists as the previous node address is changed to the new node and the address of the new node is set to the next node. For example, if node ’n’ needs to be added between node ‘a’ and node ‘b’ then, the address of node ‘a’ is changed to the address of node ’n’ while the address of node ’n’ is changed to address of node ‘b’.

def insert_at_location(self, data, index):
    if index < 0 or index > self.get_length():
      raise Exception('Invalid index')
    if index == 0:
      self.insert_at_beginning(data)
    elif index == self.get_length():
      self.insert_at_end(data)
    else:
      itr = self.head
      count = 0
      while count < index - 1:
        itr = itr.Next
        count += 1
      itr.Next = Node(data, itr.Next)

After inserting the element based on location, let us insert the element after a particular value. This method works the same way as method insert_at_location but the only difference is that it checks for data of the node than the address of the node.

def insert_after_value(self, after_value, value):
    if self.head is None:
      raise Exception('Empty list')
    itr = self.head
    while itr:
      if itr.data == after_value:
        prev.Next = itr.Next
        return
      prev = itr
      itr = itr.Next
    print('Element not in list')

We are done with the insertion operations on the LinkedList and now we will start implementing the remove methods. First, let us implement the remove_at_location method which removes elements at a particular location. The elements are traversed one after the other to find the index. After the index is found, the address of the previous node is changed to the address of the next node of the index. As we can see, the element is not deleted completely but instead the address is never referenced.

def remove_at_location(self, index):
    if self.head is None:
      raise Exception('Empty list')
    if index == 0:
      self.head = self.head.Next
      return
    else:
      count = 0
      itr = self.head
      while count < index - 1:
        itr = itr.Next
        count += 1
      itr.Next = itr.Next.Next

The other way to remove elements other than the index is by actually accessing the data itself. The below method searches for the data in the linked list and removes the first element found.

def remove_by_value(self, value):
    if self.head is None:
      raise Exception('Empty list')
    itr = self.head
    while itr:
      if itr.data = value:
        prev.Next = itr.Next
        return
      prev = itr
      itr = itr.Next
    print('Element not in list')

We are done with implementing all the functionalities that can be performed on a linked list. Let us now write our last method to print the linked list in a readable manner.

def print(self):
    if self.head is None:
      print('List is empty')
      return
    itr = self.head
    while itr:
      print(itr.data, end = '-->')
      itr = itr.Next

And, congratulations we have successfully implemented a linked list. Now let us call all the above methods from the main method to show the working.

if __name__ == '__main__':
  ll = LinkedList()
  ll.insert_at_beginning(10)
  ll.insert_at_beginning(5)
  ll.insert_at_end(20)
  ll.insert_at_location(2, 15)
  ll.insert_after_value(20, 25)
  ll.print()
  print('Number of nodes in Linked List: ', ll.get_length())
  ll.remove_at_location(2)
  ll.remove_by_value(25)
  ll.print()
  print('Number of nodes in Linked List: ', ll.get_length())
  ll.convert_list_to_values(['Apple', 'Mango', 'Banana', 'Kiwi'])
  ll.print()

Thank you for reading and hope you learned how to implement a linked list in Python. To access the whole program, click here.