Linked List Implementation 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 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.
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)
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)
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()
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()
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()
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.