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:
class node:
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:
class LinkedList:
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
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
-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
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
-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:
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")
-display
: In this function, we iterate through the list till the we come across the tail
node. The function is given below:
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
The complete code to demonstrate the functioning of the Singly Linked List is given below:
class Node:
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 Front\n2. Insert from Rear\n3. Delete\n4. Display\n5. Exit\nEnter 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:
class Node:
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:
class LinkedList:
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:
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
-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:
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
-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:
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("\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:
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
-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:
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
The complete code to demonstrate the functioning of the Doubly Linked List is given below:
class Node:
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 Front\n2. Insert from Rear\n3. Delete\n4. Display from Front\n5. Display from Rear\n6. Exit\nEnter 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")
Top comments (0)