Python Linked List
Linked List
Linked lists non-contiguous linear data structure which is made up of nodes and used to store value and a pointer pointing to the next node. It is linked with each other through a pointer.
Linked lists are often used over arrays because of several reasons. The length of a linked list can vary concerning the need of the user. It is dynamically sized, unlike the array. We can increase or decrease its size as we need. In a linked list, we can insert elements very easily.
Every element of a linked list is known as a node, and each node contains two parts:
Data: It contains the data value in the node.
Next: It contains the pointer pointing to the next node.
There is also a concept of a head pointer, which points to the first node. In simple words, we can say that a linked list consists of a collection of nodes.
Advantages of using a linked list
- It is dynamically sized, which mean increasing or decreasing its size as per our need.
- Operations like insertion and deletion are very easy in a linked list.
Disadvantages of using a linked list
- Linked list doesn’t allow random access, so we can’t access any element randomly in a linked list. We have to traverse all elements before we reach any specific element.
- Linked list requires extra memory as compared to an array. It requires extra memory for the pointers stored along with the data value.
- Linked lists are not cache-friendly.
Syntax of creating a node
class Node:
# Function to initialize the node object
def __init__ (self, data_val):
self.data = data_val # assign the data
self.next = None # set the next value as Null
Empty Linked List
An empty linked list is a linked list where the head pointer points to None.
Syntax of creating an empty linked list
class linkedList:
def __init__(self):
self.head=None
Creating a linked list
A linked list can be created by creating an object for the node and a class to use that object. Then we pass the appropriate values to the object node and start adding the nodes. Given below is an example of creating a single linked list with four data values.
In the below code, we are creating a linked list of four nodes.
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class LinkedList:
def __init__(self):
self.headval = None
node1 = LinkedList()
node1.headval = Node("January")
e2 = Node("Feburary")
e3 = Node("March")
e4 = Node("April")
# Link first Node to second node
node1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3
# Link third Node to fourth node
e3.nextval = e4
Explanation:
In the above code, we have created an object node and then a class to use that object node. In the node class Node. We store the value and the next pointer. In the other class LinkedList(), we will create a linked list. After that, we will call the class and store the value.
Traversing a Linked List
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class LinkedList:
def __init__(self):
self.headval = None
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
node1 = LinkedList()
node1.headval = Node("January")
e2 = Node("Feburary")
e3 = Node("March")
e4 = Node("April")
# Link first Node to second node
node1.headval.nextval = e2
# Link second Node to third node
e2.nextval = e3
# Link third Node to fourth node
e3.nextval = e4
node1.listprint()
Output:
January
February
March
April
Explanation:
In the above code, we have created the linked list and added the four values in four nodes. Then we will add another block of code to print the values. We have defined a function name listprint( ) and will print all the value using the while loop.
Insertion at the beginning
Inserting an element at the beginning of a linked list is very easy because in this you can just create a new node and add the next pointer to the first node. In this, we don’t have to traverse the entire linked list. Hence, we can insert a new node at the beginning of a linked list in just O(1) complexity.
Example:
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class LinkedList:
def __init__(self):
self.headval = None
# Print the linked list
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
def AtBegining(self,newdata):
NewNode = Node(newdata)
# Update the new nodes next val to existing node
NewNode.nextval = self.headval
self.headval = NewNode
node1 = LinkedList()
node1.headval = Node("July")
n2 = Node("August")
n3 = Node("September")
node1.headval.nextval = n2
n2.nextval = n3
node1.AtBegining("June")
node1.listprint()
Output:
June
July
August
Septemberer
Explanation:
In the above code, we have added another block of code for inserting the elements at the beginning of the linked list. We have used a function AtBeginning( ) to add the element at the start.
Insertion at the end
Inserting an element at the end of a single linked list can be done in a O(n) complexity. In this, we traverse the entire linked list, and then at the end, we add a new node by pointing the next value of the last node to the new node.
Example:
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class LinkedList:
def __init__(self):
self.headval = None
# Function to add newnode
def AtEnd(self, newdata):
NewNode = Node(newdata)
if self.headval is None:
self.headval = NewNode
return
laste = self.headval
while(laste.nextval):
laste = laste.nextval
laste.nextval=NewNode
# Print the linked list
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
node1 = LinkedList()
node1.headval = Node("June")
e2 = Node("July")
e3 = Node("August")
node1.headval.nextval = e2
e2.nextval = e3
node1.AtEnd("September")
node1.listprint()
Output
June
July
August
September
Explanation:
In the above code, firstly we have created a linked list and then we have used another function AtEnd( ) to add another element at the end.
Insertion in between two nodes
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class LinkedList:
def __init__(self):
self.headval = None
# Function to add newnode
def Inbetween(self,middle_node,newdata):
if middle_node is None:
print("The mentioned node is absent")
return
NewNode = Node(newdata)
NewNode.nextval = middle_node.nextval
middle_node.nextval = NewNode
# Print the linked list
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
node1 = LinkedList()
node1.headval = Node("June")
e2 = Node("July")
e3 = Node("August")
node1.headval.nextval = e2
e2.nextval = e3
node1.Inbetween(node1.headval.nextval,"August")
node1.listprint()
Output
June
July
August
September
Deleting a node
class Node:
class Node:
def __init__(self, dataval=None):
self.dataval = dataval
self.nextval = None
class LinkedList:
def __init__(self):
self.headval = None
def Atbegining(self, data_in):
NewNode = Node(data_in)
NewNode.next = self.head
self.head = NewNode
# Function to remove node
def RemoveNode(self, Removekey):
HeadVal = self.head
if (HeadVal is not None):
if (HeadVal.data == Removekey):
self.head = HeadVal.next
HeadVal = None
return
while (HeadVal is not None):
if HeadVal.data == Removekey:
break
prev = HeadVal
HeadVal = HeadVal.next
if (HeadVal == None):
return
prev.next = HeadVal.next
HeadVal = None
# Print the linked list
def listprint(self):
printval = self.headval
while printval is not None:
print (printval.dataval)
printval = printval.nextval
node1 = LinkedList()
node1.headval = Node("June")
n2 = Node("July")
n3 = Node("August")
node1.headval.nextval = n2
n2.nextval = n3
node1.RemoveNode("June")
node1.Listprint()
Output:
July
August