What are Linked Lists?
A Linked List is can be considered as a linear store of data but may not be in contiguous memory location, ie, or at random memory locations. Linked Lists enables dynamic storage of values. You can image in a Linked List to be a series of nodes that contains a value called data and a pointer next that can be considered as a linker to the next node.
For each linked list, two nodes are taken as reference points:
-head: Which is used to reference the first node of the Linked List.
-Tail: Which is used to reference the last node of the Linked List.
There are two types of Linked Lists:
-Singly Linked List
-Doubly Linked List
Singly Linked List
In this type of list, for each node in the list, there are two values that are stored: data which is the value to be stored and next a pointer that points to the next node. In this type, the next of the tail node will be None or Null as it will not point to any location as it’s the last node in the list. To create a node, we create a class node that can be used to create an object that contains the data and next as shown below:
def __init__(self, data):
self.data = data
self.next = None
We now create a LinkedList class in which the nodes are stored. When we create an object of the class, we want the head and tail nodes to be automatically created we modify the __init__() to be as follows:
def __init__(self):
self.head = Node(None)
self.tail = Node(None)
self.head.next = self.tail
The Operations that can be performed are: Insert from front, Insert from rear, Delete, Display.
-insert_from_front: In this function, we read the value to be stored, then we create a node object and pass the values as a parameter to the constructor of the node class. We then point this new_node to the next of the head and then make the next of the head to point to the new_node. The function to demonstrate this is shown below
data = int(input(“nEnter Value to be inserted“))
new_node = Node(data)
new_node.next = self.head.next
self.head.next = new_node
-insert_from_rear: In this function, we read the value to be stored, then we create a node object and pass the values as a parameter to the constructor of the node class. We then iterate through the List from the head till we reach a ndoe that points to the tail node and then we make the current_node to point to the new_node and finally we make the new_node to point to the tail. The function to demonstrate this is shown below
data = int(input(“nEnter Value to be inserted“))
new_node = Node(data)
current_node = self.head
while current_node.next != self.tail:
current_node = current_node.next
current_node.next = new_node
new_node.next = self.tail
-delete: In this function, we iterate through the list till the node whose next points to a node that contains the value to be deleted is found. Next, we make the next of the current node point to the next of the node it’s pointing to. The function that demonstrates this function is shown below:
data = int(input(“nEnter value to be deleted“))
current_node = self.head
while current_node.next != self.tail:
if current_node.next.data == data:
current_node.next = current_node.next.next
print(“nNode deleted“)
break
current_node = current_node.next
print(“nNo such value found“)
-display: In this function, we iterate through the list till the we come across the tail node. The function is given below:
current_node = self.head.next
while current_node != self.tail:
print(f“Value at current node: {current_node.data}“)
current_node = current_node.next
The complete code to demonstrate the functioning of the Singly Linked List is given below:
def __init__(self, data):
self.data = data
self.next = None
class LinkedList:
def __init__(self):
self.head = Node(None)
self.tail = Node(None)
self.head.next = self.tail
def display(self):
current_node = self.head.next
while current_node != self.tail:
print(f“Value at current node: {current_node.data}“)
current_node = current_node.next
def insert_from_front(self):
data = int(input(“nEnter Value to be inserted“))
new_node = Node(data)
new_node.next = self.head.next
self.head.next = new_node
def insert_from_rear(self):
data = int(input(“nEnter Value to be inserted“))
new_node = Node(data)
current_node = self.head
while current_node.next != self.tail:
current_node = current_node.next
current_node.next = new_node
new_node.next = self.tail
def delete(self):
data = int(input(“nEnter value to be deleted“))
current_node = self.head
while current_node.next != self.tail:
if current_node.next.data == data:
current_node.next = current_node.next.next
print(“nNode deleted“)
break
current_node = current_node.next
print(“nNo such value found“)
choice = 0
linked_list = LinkedList()
while choice != 5:
print(“n************LINKED LIST************“)
print(“n1. Insert from Frontn2. Insert from Rearn3. Deleten4. Displayn5. ExitnEnter choice:“)
choice = int(input())
if choice == 1:
linked_list.insert_from_front()
elif choice == 2:
linked_list.insert_from_rear()
elif choice == 3:
linked_list.delete()
elif choice == 4:
linked_list.display()
elif choice == 5:
break
else:
print(“nInvalid choice“)
Doubly Linked List
In this type of list, for each node in the list, there are three values that are stored: data which is the value to be stored, next which is a pointer to the next node of the Linked List and a prev which is a pointer to the previous node of the list. In this type, the prev of the head will be None or Null as it’s the first node in the list and there’s no node before it. Similarly the next of the tail node will be Null or None as it’s the last node in the list.
To create a node, we create a class node that can be used to create an object that contains the data, next, and prev as shown below:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
We now create a LinkedList class in which the nodes are stored. When we create an object of the class, we want the head and tail nodes to be automatically created we modify the __init__() to be as follows:
def __init__(self):
self.head = Node(None)
self.tail = Node(None)
self.head.next = self.tail
self.tail.prev = self.head
The Operations that can be performed are: Insert from front, Insert from rear, Delete, Display from Front, Display from Rear.
-insert_from_front: In this function, we create a node for the value to be inserted. We make the next of the new_node point to the next of the head and the prev of the new_node point to the head and finally we make the prev of the node after the head point to the new_node and we make the next of the head point to the new_node. The function is given below:
data = int(input(“nEnter Value to be inserted“))
new_node = Node(data)
new_node.next = self.head.next
new_node.prev = self.head
self.head.next.prev = new_node
self.head.next = new_node
-insert_from_rear: In this function, we create a node for the value to be inserted. We make the next of the new_node point to the tail, and the prev of the new_node point to the prev of the tail and finally we make the next of the node previous to the tail to point to the new_node and we then make the prev of the tail point to the new_node. The function is given below:
data = int(input(“nEnter Value to be inserted“))
new_node = Node(data)
new_node.next = self.tail
new_node.prev = self.tail.prev
self.tail.prev.next = new_node
self.tail.prev = new_node
-delete: In this function, we iterate through the list from the node after the head. If the data is found in a node, the next of the node previous to the node to be deleted, will be pointed to the next of the current_node and the prev of the node of the next of the current_node will point to the prev of the current_node. The function is given below:
data = int(input(“nEnter value to be deleted“))
current_node = self.head.next
while current_node != self.tail:
if current_node.data == data:
current_node.prev.next = current_node.next
current_node.next.prev = current_node.prev
print(“nNode deleted“)
break
current_node = current_node.next
else:
print(“nNo such value found“)
-display_from_rear: In this, we iterate from the penultimate node till the head, using the prev of each node. The function is given below:
current_node = self.tail.prev
while current_node != self.head:
print(f“Value at current node: {current_node.data}“)
current_node = current_node.prev
-display_from_front: In this, we iterate from the node in-front of the head till the the tail node, using the next of each node. The function is given below:
current_node = self.head.next
while current_node != self.tail:
print(f“Value at current node: {current_node.data}“)
current_node = current_node.next
The complete code to demonstrate the functioning of the Doubly Linked List is given below:
def __init__(self, data):
self.data = data
self.next = None
self.prev = None
class LinkedList:
def __init__(self):
self.head = Node(None)
self.tail = Node(None)
self.head.next = self.tail
self.tail.prev = self.head
def display_from_front(self):
current_node = self.head.next
while current_node != self.tail:
print(f“Value at current node: {current_node.data}“)
current_node = current_node.next
def display_from_rear(self):
current_node = self.tail.prev
while current_node != self.head:
print(f“Value at current node: {current_node.data}“)
current_node = current_node.prev
def insert_from_front(self):
data = int(input(“nEnter Value to be inserted“))
new_node = Node(data)
new_node.next = self.head.next
new_node.prev = self.head
self.head.next.prev = new_node
self.head.next = new_node
def insert_from_rear(self):
data = int(input(“nEnter Value to be inserted“))
new_node = Node(data)
new_node.next = self.tail
new_node.prev = self.tail.prev
self.tail.prev.next = new_node
self.tail.prev = new_node
def delete(self):
data = int(input(“nEnter value to be deleted“))
current_node = self.head.next
while current_node != self.tail:
if current_node.data == data:
current_node.prev.next = current_node.next
current_node.next.prev = current_node.prev
print(“nNode deleted“)
break
current_node = current_node.next
else:
print(“nInvalid Value“)
choice = 0
linked_list = LinkedList()
while choice != 6:
print(“n************LINKED LIST************“)
print(“n1. Insert from Frontn2. Insert from Rearn3. Deleten4. Display from Frontn5. Display from Rearn6. ExitnEnter choice:“)
choice = int(input())
if choice == 1:
linked_list.insert_from_front()
elif choice == 2:
linked_list.insert_from_rear()
elif choice == 3:
linked_list.delete()
elif choice == 4:
linked_list.display_from_front()
elif choice == 5:
linked_list.display_from_rear()
elif choice == 6:
break
else:
print(“nInvalid choice“)
