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)