""" Module for singly and doubly linked list implementations with nodes storing 2D point data. Classes: -------- Node: Represents a node in a linked list, storing an index and a tuple of (x, y) coordinates. Attributes: index (int): The index of the node. data (tuple): Tuple containing x and y integer coordinates. prev (Node): Reference to the previous node (for doubly linked lists). next (Node): Reference to the next node. LinkedList: Singly linked list implementation for storing 2D points. Methods: __init__(x: int, y: int): Initializes the list with a starting point. append(x: int, y: int): Appends a new node with (x, y) at the end. insert(index: int, x: int, y: int): Inserts a new node at the specified index. delete(index: int): Deletes the node at the specified index. to_list(): Returns a list of all (x, y) tuples in the list. display_forward(): Prints the list from head to tail. DoublyLinkedList: Doubly linked list implementation for storing 2D points. Methods: __init__(): Initializes an empty doubly linked list. append(x: int, y: int): Appends a new node with (x, y) at the end. insert(index: int, x: int, y: int): Inserts a new node at the specified index. delete(x: int, y: int): Deletes the first node with the specified (x, y) data. reverse(): Reverses the order of the list in place. find(data: tuple): Returns the index of the node with the specified data, or -1 if not found. to_list(): Returns a list of all (x, y) tuples in the list. display_forward(): Prints the list from head to tail. display_backward(): Prints the list from tail to head. """ class Node: def __init__(self, index, x:int, y:int): self.index = index self.data = (x, y) # Data as points or tuples of integral x-y coordinates self.prev = None self.next = None class LinkedList: def __init__(self, x:int, y: int): self.data = (x, y) self.head = None def append(self, x:int, y:int): new_node = Node(None, x, y) if not self.head: self.head = new_node return current = self.head while current.next: current = current.next current.next = new_node def insert(self, index, x: int, y:int): new_node = Node(index, x, y) if not self.head or index == 0: new_node.next = self.head if self.head: self.head.prev = new_node self.head = new_node return current = self.head prev = None curr_index = 0 while current and curr_index < index: prev = current current = current.next curr_index += 1 new_node.next = current if current: current.prev = new_node prev.next = new_node new_node.prev = prev def delete(self, index: int): if not self.head: print("List is empty.") return current = self.head curr_index = 0 # Deleting the head node if index == 0: self.head = current.next if self.head: self.head.prev = None return # Traverse to the node at the given index while current and curr_index < index: current = current.next curr_index += 1 if not current: print("Index out of bounds.") return # Re-link the previous and next nodes if current.prev: current.prev.next = current.next if current.next: current.next.prev = current.prev def to_list(self): result = [] current = self.head while current: result.append(current.data) current = current.next return result def display_forward(self): current = self.head while current: print(current.data, end=" -> ") current = current.next print("None") class DoublyLinkedList: def __init__(self): self.head = None def append(self, x, y): new_node = Node(None, x, y) if not self.head: self.head = new_node return current = self.head while current.next: current = current.next current.next = new_node new_node.prev = current def insert(self, index, x, y): new_node = Node(None, x, y) if index == 0: new_node.next = self.head if self.head: self.head.prev = new_node self.head = new_node return current = self.head for _ in range(index - 1): if not current: raise IndexError("Index out of bounds") current = current.next if not current: raise IndexError("Index out of bounds") new_node.next = current.next new_node.prev = current if current.next: current.next.prev = new_node current.next = new_node def delete(self, x, y): current = self.head while current: if current.data == (x, y): if current.prev: current.prev.next = current.next else: self.head = current.next if current.next: current.next.prev = current.prev return current = current.next raise ValueError(f"{(x, y)} not found in list") def reverse(self): current = self.head prev_node = None while current: next_node = current.next current.next = prev_node current.prev = next_node prev_node = current current = next_node self.head = prev_node def find(self, data): current = self.head index = 0 while current: if current.data == data: return index current = current.next index += 1 return -1 def to_list(self): result = [] current = self.head while current: result.append(current.data) current = current.next return result def display_forward(self): current = self.head while current: print(current.data, end=" ⇄ ") current = current.next print("None") def display_backward(self): current = self.head if not current: print("None") return while current.next: current = current.next while current: print(current.data, end=" ⇄ ") current = current.prev print("None") ll = LinkedList(0, 0) ll.append(0, 10) ll.append(10, 20) ll.append(20, 30) ll.append(30, 40) ll.insert(1, 11, 15) ll.insert(2, 16, 20) ll.delete(1) ll.display_forward() dll = DoublyLinkedList() dll.append(10, 6) dll.append(20, 5) dll.append(30, 3) dll.insert(1, 15, 10) # Insert 15 at index 1 dll.delete(20, 5) # Remove node with value 20 dll.reverse() # Reverse the list print("Index of 15:", dll.find(15)) dll.append(50, 8) print(dll.to_list()) # Output: [30, 15, 10, 50] dll.display_forward() # Output: 30 ⇄ 15 ⇄ 10 ⇄ None dll.display_backward() # Output: 10 ⇄ 15 ⇄ 30 ⇄ None