249 lines
7.6 KiB
Python
249 lines
7.6 KiB
Python
"""
|
|
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 |