Linked List Implementation in Python

Written by Ashwin Joy in Python

In computer science, you can store a list of items in two ways, either at contiguous memory locations or at random memory locations. 

If you store items at contiguous memory locations, we can access all the items if we know the memory location of the first item. For example, arrays or lists use contiguous memory locations to store a list of items.

A linked list is a linear data structure in which the items get stored at random memory locations. Each memory location of a linked list is called a node. These nodes are linked together using pointers.

Since the items are at random locations, we need to store the address of the next item in the current node. Hence, each node contains two fields; a data value to store the data of the current node and a pointer that stores the address of the next node.

The last node of the linked list contains a pointer that points to NULL. The head is a pointer that keeps a reference to the first element of a linked list.

Here is a pictorial representation of a linked list. This linked list has three nodes with values A, B, and C.

linked list example
example of a linked list

Linked list achieves optimized utilization of space since the nodes can reside anywhere in the memory. Also, you don’t need to define the size of a linked list in advance as it allocates the memory dynamically. These are some advantages of using linked lists over arrays.

If you haven’t understood the working of linked lists clearly, check out the following video.

Linked List Implementation using Python

Let’s implement linked lists using the Python programming language. We can create a class called Node, and whenever we want to add a node to the linked list, we can create an object of this class. This class will have two attributes: data and next.

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

Now, let’s create a class called LinkedList. We can create an object of this class to create a linked list. This class will have one attribute called head, which can be used as a pointer.

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

Inserting nodes

Let’s create a linked list and insert some nodes into it using Python. You can do insert nodes at the beginning of the linked list, end of the linked list, or after a specific node. We will see the Python code for inserting nodes in all three ways.

Inserting at the beginning of a linked list

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

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

  def insertAtBeginning(self,new_value):
    new_node = Node(new_value)
    new_node.next = self.head
    self.head = new_node
    print("New node inserted with data",new_value)


lList = LinkedList()
lList.insertAtBeginning(5)
lList.insertAtBeginning(7)
linked list insert at the beginning

Inserting at the end of a linked list

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

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

  def insertAtEnd(self,new_value):
    new_node = Node(new_value)
    if self.head is None:
      self.head = new_node
      print("New node inserted with data",new_value)
      return  
    last_node = self.head
    while(last_node.next):
      last_node = last_node.next
    last_node.next = new_node
    print("New node inserted with data",new_value)


lList = LinkedList()
lList.insertAtEnd(2)
lList.insertAtEnd(4)
linked list insert at end

Inserting after a specific node

I have inserted a node using the insertAtBeginning method so that the previous node can’t be empty.

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

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

  def insertAtBeginning(self,new_value):
    new_node = Node(new_value)
    new_node.next = self.head
    self.head = new_node
    print("New node inserted with data",new_value)

  def insertAfter(self,prev_node,new_value):
    if prev_node == None:
      print("Previous node is empty")
    new_node = Node(new_value)
    new_node.next = prev_node.next
    prev_node.next = new_node
    print("New node inserted with data",new_value)


lList = LinkedList()

lList.insertAtBeginning(5)

lList.insertAfter(lList.head,8)
lList.insertAfter(lList.head,3)
linked list insert after a specific node

Traversing the linked list

In traversing, we visit each node of the linked list to perform some operation on it, for example, printing the data present in each node. Let’s see how we can print all the data values in the linked list.

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

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

  def insertAtBeginning(self,new_value):
    new_node = Node(new_value)
    new_node.next = self.head
    self.head = new_node
    print("New node inserted with data",new_value)

  def printLinkedList(self):
    temp = self.head
    while(temp):
      print(temp.data)
      temp = temp.next


lList = LinkedList()

lList.insertAtBeginning(5)
lList.insertAtBeginning(1)
lList.insertAtBeginning(9)

lList.printLinkedList()

Deleting a node from the linked list

Let’s see how we can delete a node from a linked list. This can be done in many ways. But we are not going to try all those different ways.

Here, we will simply create a method that accepts a value and delete the node that contains that value.

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

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

  def insertAtBeginning(self,new_value):
    new_node = Node(new_value)
    new_node.next = self.head
    self.head = new_node
    print("New node inserted with data",new_value)

  def printLinkedList(self):
    temp = self.head
    while(temp):
      print(temp.data)
      temp = temp.next

  def deleteNode(self,key):
    temp = self.head
    if(temp==None):
      print("Can't perform deletion")
      return
    while(temp != None):
      if(temp.data == key):
        break
      prev = temp
      temp = temp.next
    prev.next = temp.next
    temp = None
    print("1 node deleted with data",key)


lList = LinkedList()

lList.insertAtBeginning(5)
lList.insertAtBeginning(1)
lList.insertAtBeginning(9)

lList.deleteNode(1)

lList.printLinkedList()
linked list deletion

Reversing a linked list

Let’s see the Python code to reverse a linked list.

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

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

  def insertAtBeginning(self,new_value):
    new_node = Node(new_value)
    new_node.next = self.head
    self.head = new_node
    print("New node inserted with data",new_value)

  def printLinkedList(self):
    temp = self.head
    while(temp):
      print(temp.data)
      temp = temp.next

  def reverseLinkedList(self):
    prev = None
    curr = self.head
    while(curr is not None):
      next = curr.next
      curr.next = prev
      prev = curr
      curr = next
    self.head = prev
    print("LinkedList reversed")


lList = LinkedList()

lList.insertAtBeginning(5)
lList.insertAtBeginning(1)
lList.insertAtBeginning(9)

lList.printLinkedList()

lList.reverseLinkedList()

lList.printLinkedList()
reverse a linked list

Deleting a linked list

Now let’s try to write a method that deletes the entire linked list when it gets called.

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

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

  def insertAtBeginning(self,new_value):
    new_node = Node(new_value)
    new_node.next = self.head
    self.head = new_node
    print("New node inserted with data",new_value)
  
  def deleteLinkedList(self):
    curr = self.head
    while curr:
      temp = curr.next
      del curr.data
      curr = temp
    print("LinkedList deleted")


lList = LinkedList()

lList.insertAtBeginning(5)
lList.insertAtBeginning(1)
lList.insertAtBeginning(9)

lList.deleteLinkedList()
delete a linked list

Circular LinkedlLists

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

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

  def push(self,new_value):
    new_node = Node(new_value)
    temp = self.head
    new_node.next = self.head

    if self.head is not None:
      while(temp.next != self.head):
        temp = temp.next
      temp.next = new_node
    else:
      new_node.next = new_node
    self.head = new_node
    print("New node pushed")

  def countNodes(self):
    temp = self.head
    count = 0
    count = count + 1
    while(temp.next != self.head):
      count = count + 1
      temp = temp.next
    print("Count of nodes:",count)
  
  # method to convert a regular linkedlist into circular linkedlist
  def toCircular(self,head):
    start = head
    while(head.next is not None):
      head = head.next
    head.next = start
    return start


  def printCLinkedList(self):
    temp = self.head
    if self.head is not None:
      while(True):
        print(temp.data)
        temp = temp.next
        if(temp == self.head):
          break


cList = CircularLinkedList()
cList.push(5)
cList.push(7)
cList.printCLinkedList()
cList.countNodes()

Doubly Linked Lists

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

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

  def push(self,new_value):
    new_node = Node(new_value)
    new_node.next = self.head
    if self.head is not None:
      self.head.prev = new_node
    self.head = new_node
    print("1 node pushed.")

  def insertAfter(self,prev_node,new_data):
    if prev_node is None:
      print("Prev node can't be None")
      return
    new_node = Node(new_data)
    new_node.next = prev_node.next
    prev_node.next = new_node

    if new_node.next is not None:
      new_node.next.prev = new_node
    print("1 node inserted.")

  def insertAtLast(self,new_value):
    new_node = Node(new_value)
    new_node.next = None
    if self.head is None:
      new_node.prev = None
      self.head = new_node
      return
    last_node = self.head
    while(last_node.next is not None):
      last_node = last_node.next
    last_node.next = new_node
    new_node.prev = last_node
    print("1 node inserted at the end.")

  def printNodes(self):
    curr = self.head
    while(curr is not None):
      print(curr.data)
      curr = curr.next

  def deleteNode(self,key):
    if self.head is None or key is None:
      print("Deletion unsuccessful.")
      return
    

dList = DoublyLinkedList()
dList.push(5)
dList.push(6)
dList.insertAfter(dList.head,9)
dList.insertAtLast(3)
dList.printNodes()

I hope this article was helpful to you. Check out my articles on queue and stack data structures in Python.

You can do the LinkedIn concepts visualization here: https://linked-list-visualizer.vercel.app/app

Ashwin Joy

I'm the face behind Pythonista Planet. I learned my first programming language back in 2015. Ever since then, I've been learning programming and immersing myself in technology. On this site, I share everything that I've learned about computer programming.

Leave a Reply

Your email address will not be published. Required fields are marked *

Recent Posts