A linked list is one of the basic data structures present in computer science. To represent a linked list we create a sequence of nodes or a chain of nodes. In the sequence of nodes, the first node is called the head of the Linked List and the last node is known as the tail. In the linked list every node has a pointer to the next node, which means each node contains a piece of extra information next representing the next node connected to it.
Singly Linked List[/caption] The above image is an example of a singly linked list, where each node is pointing to its next node, except for the Tail node. Apart from a singly linked list, there is also a data structure which is known as a doubly-linked list.
Doubly Linked List[/caption] In this doubly linked list, each node contains two pointers, one pointer to the next node and one pointer to the previous node. There are many cases where we use the linked list to solve real-world problems. Linked lists provide an alternative to the standard list or arrays present in Python.
- Linked list allow us to add and remove elements with linear time complexity.
- Managing items in a linked list are also very easy.
- In linked list insertion item in the middle of the list is cheap as compared to the list and array data structure.
Note: The linked list is an alternative to the static arrays, whereas in Python the list data structure is more a dynamic data structure, which is as efficient as a linked list. In this tutorial, we will learn the concept of the Linked List data structure and learn how to implement a custom Linked List in Python using class and objects.
Singly Linked List
A singly linked list is a sequential data structure, made of nodes. A node is a single block in the linked list structure that contains some data. We can also define a linked list as a sequential chain of nodes. Where the first node is known as the Head and the last node Tail .
In the singly linked list, each node contains a pointer to the next node, which connects one node to the next node in the linked list. Only the tail node does not point to any next node.
How to implement a singly linked list in Python?
Here are the steps to define or implement a singly linked list in Python
Step 1: Create a Node class
For the singly linked list, the node class can contain any type of data, but it must have a next pointer that can point to the next node. The initial value of the next node should be None because it is always expected to be the last node in the linked list.
#Node Class
class Node:
def __init__(self, data):
#node data
self.data = data
#pointer to the next node
self.next = None
The Node class can accept a data argument.
Step 2: Create a linked list class that will manage nodes by adding, deleting, and traversing through the nodes.
Whenever we create a linked list, it should have two information when initializing its object, the head node, and tail node information. But when we define a linked list, without any nodes in it the value of Head and Tail would be None .
class LinkedList:
def __init__(self):
#head pointing to the head node or the first node
self.head = None
#tail will point to the tail node or the last node
self.tail = None
#the total length of the LinkedList
self.length = 0
The
self.length
property is just for some extra information about the linked list. The
self.length
property defines the total length of the linkedlist.
Step 3: Define the methods in the LinkedList that will add a node at the end, insert a node in between, delete a node from the LinkedList and traverse node in the linked list.
Let’s start with the method that will add the node to the linked list.
Add Node in the Linked List.
# add node in the linked list(at the end)
def append(self, data):
#if there is no node in the linked list
#create a node
#for the first node
#the head and the tail would point to the same node
if not self.head:
new_node = Node(data) #create a node
self.head = new_node
self.tail = new_node
self.length += 1 #increase the length of linked list by 1
#if is a node in the linked list
#create a new node
#point the current tail node pointer to the new node
#set the new node as the tail node
else:
new_node = Node(data)
self.tail.next = new_node
self.tail = new_node
self.length += 1 #increase the length of the linked list by 1
In the above example, we have defined the append method in the LinkedList class to add a new node to the Linked List. In the first, if condition
if not self.head:
the statement is checking if the LinkedList already has some node or it's empty. If the LinkedList is empty then the value of
self.head
and
self.tail
would be None. And the node that is added to the linked list would be the first node and it will be the head and tail node for the LinkedList. In the else statement, the code is instructing that if the LinkedList already has one or more than one node, then create the new node, point the current tail node next pointer to the new node(because it is adding at the last), and set the value of tail to the new node because the LinkedList now have a new tail node.
Insert a Node in the Linked List
In the above section, we see how can we add a node at the end of the Linked List, now let’s write
insert(pos, data)
,
that can insert the new node in between the linked list.
#insert the new node in the between of the linked list
def insert(self, pos, data):
#insert the new node at the end of the list
#if the position is greater than the total length of the list
if pos>self.length:
self.append(data)
#if the pos is 1
# the new head
elif pos == 1:
new_node = Node(data)
new_node.next = self.head
self.head = new_node
self.length += 1 #increase value of length
#if the pos in between the linked list
else:
temp = self.head
#traverse to the position-1
#where we want to insert the new node
for i in range(1, pos-1):
temp= temp.next
#create a new node
new_node = Node(data)
#get the pointer that is pointing to the current node
#which is located at position pos
current = temp.next
#set the position-1 node next node to the newly created node
temp.next = new_node
#set the newly created next node value to the old node
new_node.next = current
self.length += 1 #increase the value of length
Delete a Node in the Linked List
To delete a node from the linked list, we will point the previous node of the Node to the next node of the node.
#the delete method to delete the node from the linked list
def delete(self, pos):
temp = self.head
#traverse to the position
#track the previous node
#track the current node with temp that you want to delete
for i in range(1, pos):
prev = temp
temp= temp.next
#if the node that to delete is the head node
if temp== self.head:
self.head = temp.next
#if the node that to delete is the tail node
elif temp==self.tail:
self.tail= prev
#if the node that to delete is between the linked list
else:
prev.next= temp.next
self.length -= 1 #decrease the length of the linkedlist by 1
Traverse through the linked list
To traverse through the linked list means to go through every linked list node and display them.
#display all the node data sequentially from head to tail
def traverse(self):
print("Head--->", end=" ")
temp = self.head
while temp:
print(temp.data, end=" ")
temp= temp.next
print("<----Tail")
Python program to implement singly list
Put all the code together and run
#Node Class
class Node:
def __init__(self, data):
#node data
self.data = data
#pointer to the next node
self.next = None
class LinkedList:
def __init__(self):
#head pointing to the head node or the first node
self.head = None
#tail will point to the tail node or the last node
self.tail = None
#the total length of the LinkedList
self.length = 0
# add node in the linked list(at the end)
def append(self, data):
#if there is no node in the linked list
#create a node
#for the first node
#the head and the tail would point to the same node
if not self.head:
new_node = Node(data) #create a node
self.head = new_node
self.tail = new_node
self.length += 1 #increase the length of linked list by 1
#if is a node in the linked list
#create a new node
#point the current tail node pointer to the new node
#set the new node as the tail node
else:
new_node = Node(data)
self.tail.next = new_node
self.tail = new_node
self.length += 1 #increase the length of the linked list by 1
#insert the new node in the between of the linked list
def insert(self, pos, data):
#insert the new node at the end of the list
#if the position is greater than the total length of the list
if pos>self.length:
self.append(data)
#if the pos is 1
# the new head
elif pos == 1:
new_node = Node(data)
new_node.next = self.head
self.head = new_node
self.length += 1 #increase value of length
#if the pos in between the linked list
else:
temp = self.head
#traverse to the position-1
#where we want to insert the new node
for i in range(1, pos-1):
temp= temp.next
#create a new node
new_node = Node(data)
#get the pointer that is pointing to the current node
#which is located at position pos
current = temp.next
#set the position-1 node next node to the newly created node
temp.next = new_node
#set the newly created next node value to the old node
new_node.next = current
self.length += 1 #increase the value of length
#the delete method to delete the node from the linked list
def delete(self, pos):
temp = self.head
#traverse to the position
#track the previous node
#track the current node with temp that you want to delete
for i in range(1, pos):
prev = temp
temp= temp.next
#if the node that to delete is the head node
if temp== self.head:
self.head = temp.next
#if the node that to delete is the tail node
elif temp==self.tail:
self.tail= prev
#if the node that to delete is between the linked list
else:
prev.next= temp.next
self.length -= 1 #decrease the length of the linkedlist by 1
#display all the node data sequentially from head to tail
def traverse(self):
print("Head--->", end=" ")
temp = self.head
while temp:
print(temp.data, end=" ")
temp= temp.next
print("<----Tail")
l = LinkedList()
l.append('a') #a
l.append('b') # a b
l.append('c') # a b c
l.insert(2, 20) # a 20 b c
l.append('d') #a 20 b c d
l.delete(2) # a b c d
l.insert(100, 'e') # a b c d e
l.traverse()
Output
Head---> a b c d e <----Tail
Doubly Linked List
The doubly linked list is similar to the singly linked list, the only difference is, the doubly linked list node contains two pointers
prev
and the
next
. The prev pointer points to the previous node and the next pointer points to the next node in the linked list. In the case of a doubly-linked list the head node’s
prev
points to None and the next points to the next node and the tail node’s prev points to the second last node, and the next points to None.
Doubly Linked list Implementation in Python
Step 1: Create a Node class
Both singly and doubly linked lists are a sequential chain of nodes. And similar to the singly linked list we have to create a Node class for the doubly linked list.
#Node Class for doubly linked list
class Node:
def __init__(self, data):
#node data
self.data = data
#pointer to the next node
self.next = None
#pointer to the previous node
self.prev = None
The node of the doubly linked list contains two pointers self.next and self.prev, that points to the next and previous node.
Step 2: Define the linked list class
After defining the Node class let’s define the LinkedList class for the doubly linked list, which will contain methods and properties to manage the linked list.
class LinkedList:
def __init__(self):
#head pointing to the head node or the first node
self.head = None
#tail will point to the tail node or the last node
self.tail = None
#the total length of the LinkedList
self.length = 0
Step 3: Define the operations of a doubly-linked list as LinkedList Methods
Let’s start with append method that will add the node at the end of the linked list.
def append(self, data):
#if there is no node in the linked list
if not self.head:
#create a new node
new_node = Node(data)
#set the head and tail to the new node
self.head = new_node
self.tail = new_node
#if there is one or more than one node in the linked list
else:
#create a new node
new_node = Node(data)
#set the new node to the next of the current tail node
self.tail.next = new_node
#set the current tail node as previous node of the new node
new_node.prev = self.tail
#set the new node as the tail node
self.tail = new_node
self.length+=1 #increase the length of the linked list by 1
In the append method, we set 2 conditions in the.
- The first condition is set for the linked list if there is no node in the linked list.
- And the second condition is set if there is one or more than one node in the linked list. And we want to add the new node at the end of the list.
Insert Method
In the insert method, we will define the insert new node in the doubly linked list. To insert a new node we need set select a position where the node is needed to insert.
#method to insert new node at a specific position pos
def insert(self, pos, data):
#if to insert the new node at the head.
if pos ==1:
new_node = Node(data)
new_node.next= self.head
self.head.prev = new_node
self.head = new_node
#to insert the new node at the end of the linked list
elif pos>self.length:
self.append(data)
#To insert the new node between the linked list
else:
temp = self.head
#go to the position of the nodes
for i in range(1, pos):
temp = temp.next
#create a new node
new_node = Node(data)
#set the new node next and prev pointers
new_node.next = temp
new_node.prev = temp.prev
#point the previous node next to the new node
temp.prev.next = new_node
#set the next node previous pointer to the new node
temp.prev = new_node
self.length +=1 #increase the length of the linked list by 1
Delete Method
We can also delete the node from a doubly linked list. To delete a node we just need to manipulate the targeted node's previous and next nodes.
#method to delete node from the specific position pos
def delete(self, pos):
#to delete the head node
if pos==1:
self.head = self.head.next
self.head.prev = None
#to delete the tail node
elif pos >= self.length:
self.tail = self.tail.prev
self.tail.next = None
#to delete the node in betweeen the linked list
else:
temp= self.head
for i in range(1, pos):
temp= temp.next
temp.prev.next = temp.next
temp.next.prev= temp.prev
self.length-=1 #decrease the length of the linked list by 1
Traverse method
As the Doubly linked list has two pointers next and prev, we can traverse a doubly linked list from head to tail and tail to head.
#display all the node data sequentially from head to tail
def traverse(self):
print("Head--->", end=" ")
temp = self.head
while temp:
print(temp.data, end=" ")
temp= temp.next
print("<----Tail")
#display all the node data sequentially from tail to head
def trackback(self):
print("Tail--->", end=" ")
temp = self.tail
while temp:
print(temp.data, end=" ")
temp= temp.prev
print("<----Head")
Python Doubly linked list program with append, insert, delete and traverse methods
Now put all the code together and execute.
#Node Class for doubly linked list
class Node:
def __init__(self, data):
#node data
self.data = data
#pointer to the next node
self.next = None
#pointer to the previous node
self.prev = None
class LinkedList:
def __init__(self):
#head pointing to the head node or the first node
self.head = None
#tail will point to the tail node or the last node
self.tail = None
#the total length of the LinkedList
self.length = 0
def append(self, data):
#if there is no node in the linked list
if not self.head:
#create a new node
new_node = Node(data)
#set the head and tail to the new node
self.head = new_node
self.tail = new_node
#if there is one or more than one node in the linked list
else:
#create a new node
new_node = Node(data)
#set the new node to the next of the current tail node
self.tail.next = new_node
#set the current tail node as previous node of the new node
new_node.prev = self.tail
#set the new node as the tail node
self.tail = new_node
self.length+=1 #increase the length of the linked list by 1
#method to insert new node at a specific position pos
def insert(self, pos, data):
#if to insert the new node at the head.
if pos ==1:
new_node = Node(data)
new_node.next= self.head
self.head.prev = new_node
self.head = new_node
#to insert the new node at the end of the linked list
elif pos>self.length:
self.append(data)
#To insert the new node between the linked list
else:
temp = self.head
#go to the position of the nodes
for i in range(1, pos):
temp = temp.next
#create a new node
new_node = Node(data)
#set the new node next and prev pointers
new_node.next = temp
new_node.prev = temp.prev
#point the previous node next to the new node
temp.prev.next = new_node
#set the next node previous pointer to the new node
temp.prev = new_node
self.length +=1 #increase the length of the linked list by 1
#method to delete node from the specific position pos
def delete(self, pos):
#to delete the head node
if pos==1:
self.head = self.head.next
self.head.prev = None
#to delete the tail node
elif pos >= self.length:
self.tail = self.tail.prev
self.tail.next = None
#to delete the node in betweeen the linked list
else:
temp= self.head
for i in range(1, pos):
temp= temp.next
temp.prev.next = temp.next
temp.next.prev= temp.prev
self.length-=1 #decrease the length of the linked list by 1
#display all the node data sequentially from head to tail
def traverse(self):
print("Head--->", end=" ")
temp = self.head
while temp:
print(temp.data, end=" ")
temp= temp.next
print("<----Tail")
#display all the node data sequentially from tail to head
def trackback(self):
print("Tail--->", end=" ")
temp = self.tail
while temp:
print(temp.data, end=" ")
temp= temp.prev
print("<----Head")
l = LinkedList()
l.append('a') #a
l.append('b') # a b
l.append('c') # a b c
l.append('d') #a b c d
l.insert(45, 'e') #a b c d e
l.insert(1, 'Z') #Z a b c d e
l.insert(4, 'D') # Z a b c D d e
l.delete(4) # Z a b c d e
l.append('f') # Z a b c d e f
l.delete(6) # Z a b c d f
l.traverse()
print("\n\n")
l.trackback()
Output
Head---> Z a b c d f <----Tail
Tail---> f d c b a Z <----Head
Conclusion
In this Python tutorial, we learned what is singly and doubly linked list in Python and how to implement them. In a singly linked list, every node has a next pointer variable that points to the next node, which makes the singly linked list a unidirectional sequential data structure. On the other hand, the doubly linked list’s nodes have two pointer variables next and prev( previous), which point to the next and previous nodes.
People are also reading:
- Python Class Method with examples
- Python Class Variables
- Replace Item in Python List
- Python List Methods
- Python List Files in a Director y
- Remove Duplicates from a Python List
- Python Instance Method
- Python Instance Variables
- Timestamp in Python
- Python Regex Replace Pattern in a string using re.sub()
Leave a Comment on this Post