Created
October 3, 2023 00:21
-
-
Save Basemera/1bc22038484a4ceb1791954546faf457 to your computer and use it in GitHub Desktop.
Python implementation for a doubly linkedlist
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
class Node: | |
def __init__(self, data) -> None: | |
self.data = data | |
self.next = None | |
self.previous = None | |
class DoublyLinkedList: | |
def __init__(self) -> None: | |
self.head = None | |
self.tail = None | |
def __iter__(self): | |
node = self.head | |
while node is not None: | |
yield node | |
node = node.next | |
def __repr__(self) -> str: | |
nodes = [] | |
for node in self: | |
nodes.append(node.data) | |
return " -> ".join(str(x) for x in nodes) | |
def isEmpty(self): | |
return not self.head | |
def __len__(self): | |
nodes = [] | |
l = 0 | |
if not self.isEmpty(): | |
for node in self: | |
l += 1 | |
return l | |
# create DLL | |
def createDLL(self, node_value): | |
node = Node(node_value) | |
node.next = None | |
node.previous = None | |
self.head = node | |
self.tail = node | |
def insert_node(self, node_value, location): | |
if self.head is None: | |
print("Node cannot be inserted") | |
else: | |
new_node = Node(node_value) | |
if location == 0: | |
new_node.next = self.head | |
new_node.previous = None | |
self.head = new_node | |
new_node.next.previous = new_node | |
elif location == len(self): | |
new_node.next = None | |
new_node.previous = self.tail | |
self.tail = new_node | |
new_node.previous.next = new_node | |
else: | |
if location > len(self): | |
raise IndexError("index out of range") | |
temp_node: Node = self.head | |
index = 0 | |
while index < location - 1: | |
temp_node = temp_node.next | |
index += 1 | |
temp_node_next = temp_node.next | |
new_node.previous = temp_node | |
temp_node.next = new_node | |
new_node.next = temp_node_next | |
temp_node_next.previous = new_node | |
return self | |
def traverse_dll(self, reverse = False): | |
if self.isEmpty(): | |
return "Empty dll nothing to traverse" | |
current_node = self.head if not reverse else self.tail | |
while current_node: | |
print(current_node.data, "->") | |
if reverse: | |
current_node = current_node.previous | |
else: | |
current_node = current_node.next | |
def search(self, node_value): | |
if self.isEmpty(): | |
return "dll is empty" | |
temp_node = self.head | |
while temp_node: | |
if temp_node.data == node_value: | |
return f"node value {node_value} exists in dll" | |
temp_node = temp_node.next | |
return f"node value {node_value} does not exist in dll" | |
def pop_first_node(self): | |
if self.isEmpty(): | |
return "dll is empty" | |
if self.head == self.tail: | |
self.head = None | |
self.tail = None | |
return "dll is now empty" | |
self.head = self.head.next | |
self.head.previous = None | |
return f"head is now set at {self.head.data}" | |
def pop_last_node(self): | |
if self.isEmpty(): | |
return "dll is empty" | |
if self.head == self.tail: | |
self.head = None | |
self.tail = None | |
return "dll is now empty" | |
self.tail = self.tail.previous | |
self.tail.next = None | |
return f"tail is now set at {self.tail.data}" | |
def remove_node_by_value(self, node_value): | |
if self.isEmpty(): | |
return "dll is empty" | |
temp_node = self.head | |
while temp_node: | |
if temp_node.data == node_value: | |
prev_node: Node = temp_node.previous | |
next_node: Node = temp_node.next | |
prev_node.next = next_node | |
next_node.previous = prev_node | |
return f"node with value {node_value} has been removed from dll" | |
temp_node = temp_node.next | |
return "Node not found" | |
def pop_node_by_index(self, location): | |
if self.isEmpty(): | |
return "dll is empty" | |
current_node = self.head | |
index = 0 | |
while index < location - 1: # we start counting at index 0 | |
current_node = current_node.next | |
index += 1 | |
current_node.next = current_node.next.next | |
current_node.next.previous = current_node | |
return "The node has been successfully deleted" | |
def delete_entire_dll(self): | |
if self.isEmpty(): | |
return "dll is empty" | |
current_node = self.head | |
while current_node: | |
current_node.previous = None | |
current_node = current_node.next | |
self.head = None | |
self.tail = None | |
return "dll is now empty" |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment