Skip to content

Instantly share code, notes, and snippets.

@Julian-Nash
Last active December 22, 2020 14:39
Show Gist options
  • Save Julian-Nash/47457e3d6b650f5edaddf87f4cf9e694 to your computer and use it in GitHub Desktop.
Save Julian-Nash/47457e3d6b650f5edaddf87f4cf9e694 to your computer and use it in GitHub Desktop.
Doubly Linked List. Python implementation
from typing import Optional, Union
class DoublyLinkedListNode:
def __init__(self, value: Optional = None, prev: Optional = None, next: Optional = None):
self.value = value
self.prev = prev
self.next = next
def __repr__(self):
return f"DoublyLinkedListNode(value={self.value})"
class DoublyLinkedList:
def __init__(self):
self._head: Union[DoublyLinkedListNode, None] = None
self._tail: Union[DoublyLinkedListNode, None] = None
self._count: int = 0
def __len__(self) -> int:
return self._count
@property
def head(self) -> Union[DoublyLinkedListNode, None]:
""" Returns the head node of the list """
return self._head
@property
def tail(self) -> Union[DoublyLinkedListNode, None]:
""" Returns the tail node of the list """
return self._tail
def __iter__(self):
""" Returns an iterator, yielding the list node values """
current = self.head
while current:
yield current.value
current = current.next
def __reversed__(self):
""" Returns an iterator, yielding the list node values in reverse order """
current = self.tail
while current:
yield current.value
current = current.prev
def prepend(self, val) -> None:
""" Prepend a value to the start of the list. """
node = DoublyLinkedListNode(value=val, prev=None, next=self.head)
if self.head:
self._head.prev = node
self._head = node
if not self.tail:
self._tail = self.head
self._count += 1
def append(self, val) -> None:
""" Append a value to the tail of the list. """
if not self.tail:
self.prepend(val)
else:
node = DoublyLinkedListNode(value=val, prev=self.tail)
self._tail.next = node
self._tail = node
self._count += 1
def find(self, val) -> Union[DoublyLinkedListNode, None]:
""" Finds and returns the value from the list. """
current = self.head
while current:
if current.value == val:
return current
current = current.next
return None
def contains(self, val) -> bool:
""" Returns True if the value is in the list, else False. """
return self.find(val) is not None
def remove(self, val) -> bool:
""" Removes a value from the list. Returns True if the value
was found and removed from the list, otherwise False
"""
node = self.find(val)
if not node:
return False
prev = node.prev
next = node.next
if not prev:
self._head = next
if self.head:
self._head.prev = None
else:
prev.next = next
if not next:
self._tail = prev
if self.tail:
self._tail.next = None
else:
next.prev = prev
self._count -= 1
return True
if __name__ == "__main__":
my_list: DoublyLinkedList = DoublyLinkedList()
for i in range(1, 6):
my_list.append(i)
c3 = my_list.contains(3)
c9 = my_list.contains(9)
rm = my_list.remove(2)
c2 = my_list.contains(2)
my_list.prepend(99)
h99 = my_list.head.value == 99
l = len(my_list) == 5
for i in my_list:
print(i)
for i in reversed(my_list):
print(i)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment