Skip to content

Instantly share code, notes, and snippets.

@Basemera
Created October 3, 2023 00:21
Show Gist options
  • Save Basemera/1bc22038484a4ceb1791954546faf457 to your computer and use it in GitHub Desktop.
Save Basemera/1bc22038484a4ceb1791954546faf457 to your computer and use it in GitHub Desktop.
Python implementation for a doubly linkedlist
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