A linked list is a linear data structure referred to as a collection of similar elements linked in a linear order. The basic unit in a linked list is a node. Node is constructed with a data part and a link part. Data part contains the value you wish to store for a node. Address part contains the address of next node in Python linked list.
You can think of linked list as a list of clues for a treasure hunt. Each clue will tell you where you have to go next in search of the treasure. In linked list the address part also called next, tells the program where to find the next node of the liked list.
This node structure of the linked list allows efficient memory management. Unlike an array, contiguous memory is not required to store the elements of a linked list. As and when you need to insert a new node in linked list you can do so by updating the links of nodes. Any node can be deleted by updating pointers again. This gives a dynamic nature to a Linked list.
In this post you will understand how to create a Python linked list using Python classes. So let’s begin.
Declaring Node Class
First we declare a Node class. Node objects will be created whenever a new node is to be added in the linked list.
class Node:
def __init__(self, data=None, link=None):
self.data=data
self.link=link
def __str__(self):
return str(self.data)
Declaring Linked List Class
The second class for this program is the LinkedList. In this class the start address is used to store the address of first node of the Python Linked List.
class LinearList:
def __init__(self, start=None):
self.start=start
Operations of Python Linked List
Display Node values of the Linked List
This is the traversal operation of linked list. In this method of LinkedList class, a pointer ptr is assigned the address start of first node. The function iterates through linked list using while loop until ptr becomes null indicating that the linked list is traversed to the end.
def printList(self):
ptr=self.start
while ptr:
print(ptr)
ptr=ptr.link
print()
Creating three nodes, linking them together and passing the address of first node while creating LinkedList object.
node1=Node('amy')
node2=Node('Bob')
node3=Node('Cathy')
node1.link=node2
node2.link=node3
ll=LinearList(node1)
print('Initially list elements')
ll.printList()
Add a Node at the Beginning
In this method of LinkedList a new node is assigned the value to be added in linked list at the beginning. New node’s link part is updated with start and start is updated with the address of the new node.
def addBegNode(self, value=None):
node=Node(value)
node.link=self.start
self.start=node
print('After inserting element at beginning')
ll.addBegNode('Alia')
ll.printList()
Add a Node at the End
In this method of LinkedList a new node is assigned the value to be updated at the end in the linked list. The linked list is traversed to reach the last node. In each iteration of while loop Save stores address of previous node and ptr is updated with address of next node. When this loop terminates new node’s link part is updated with None and the link part of save is updated with address of new node, thus adding it at the end of Python linked list.
def addEndNode(self, value=None):
ptr=self.start
while ptr:
save=ptr
ptr=ptr.link
node=Node(value)
save.link=node
node.link=None
print('After inserting element at end')
ll.addEndNode('Zoe')
ll.printList()
Add a Node Before a Given Node
ptr node is assigned start address. The linked list is traversed to find the node whose data part matches the value before which the new node is to be inserted. In each iteration of while loop save stores address of previous node and ptr is updated with address of next node. The link part of save is updated with address of new node and new node’s link part is updated with ptr thus adding it before the given node.
def addBeforeNode(self, value=None,bef=None):
ptr=self.start
while ptr:
save=ptr
ptr=ptr.link
if (ptr.data==bef):
break
node=Node(value)
save.link=node
node.link=ptr
def addAfterNode(s
print('After inserting element before an existing element')
ll.addBeforeNode('Yera','Zoe')
ll.printList()
Add a node after a given node
ptr node is assigned start address. The linked list is traversed to find the node whose data part matches the value after which the new node is to be inserted. If the given after value matches the first node’s data part while loop is skipped completely. Else in iteration of the loop ptr is updated with address of next node till the data part of ptr does not match the after value. New node’s link part is updated with link part of ptr and link part of ptr is updated with the address of the new node.
def addAfterNode(self, value=None,aft=None):
ptr=self.start
if(ptr.data!=aft):
while ptr:
ptr=ptr.link
if (ptr.data==aft):
break
node=Node(value)
node.link=ptr.link
ptr.link=node
print('After inserting element after an existing element')
ll.addAfterNode('Bill','Alia')
ll.printList()
Delete a Given Node
First the value of the node to be deleted in compared with value of first node. If does not match then ptr is assigned start address. The linked list is traversed to find the node whose data part matches the value to be deleted. In iteration of the loop save is updated with ptr and ptr is updated with address of next node till the data part of ptr does not match value to be deleted. When the node to be deleted is found, save’s link part is updated with link part of ptr thus deleting the given node.
def delNode(self, value=None):
if (self.start.data==value):
self.start=self.start.link
else:
ptr=self.start
while ptr:
save=ptr
ptr=ptr.link
if (ptr.data==value):
break
save.link=ptr.link
print('After deleting an element ')
ll.delNode('Cathy')
ll.printList()
Complete Program of Python Linked List
class Node:
def __init__(self, data=None, link=None):
self.data=data
self.link=link
def __str__(self):
return str(self.data)
class LinearList:
def __init__(self, start=None):
self.start=start
def printList(self):
ptr=self.start
while ptr:
print(ptr)
ptr=ptr.link
print()
def addBegNode(self, value=None):
node=Node(value)
node.link=self.start
self.start=node
def addEndNode(self, value=None):
ptr=self.start
while ptr:
save=ptr
ptr=ptr.link
node=Node(value)
save.link=node
node.link=None
def addBeforeNode(self, value=None,bef=None):
ptr=self.start
while ptr:
save=ptr
ptr=ptr.link
if (ptr.data==bef):
break
node=Node(value)
save.link=node
node.link=ptr
def addAfterNode(self, value=None,aft=None):
ptr=self.start
if(ptr.data!=aft):
while ptr:
ptr=ptr.link
if (ptr.data==aft):
break
node=Node(value)
node.link=ptr.link
ptr.link=node
def delNode(self, value=None):
if (self.start.data==value):
self.start=self.start.link
else:
ptr=self.start
while ptr:
save=ptr
ptr=ptr.link
if (ptr.data==value):
break
save.link=ptr.link
node1=Node('amy')
node2=Node('Bob')
node3=Node('Cathy')
node1.link=node2
node2.link=node3
ll=LinearList(node1)
print('Initially list elements')
ll.printList()
print('After inserting element at beginning')
ll.addBegNode('Alia')
ll.printList()
print('After inserting element at end')
ll.addEndNode('Zoe')
ll.printList()
print('After inserting element before an existing element')
ll.addBeforeNode('Yera','Zoe')
ll.printList()
print('After inserting element after an existing element')
ll.addAfterNode('Bill','Alia')
ll.printList()
print('After deleting an element ')
ll.delNode('Cathy')
ll.printList()
You can read the basics of a Linked List here
Be First to Comment