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.
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 = NoneNow, 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 = NoneInserting 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)
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.
