Created
January 7, 2022 12:32
-
-
Save artrey/0b52b3fca18f47905c9232929a28b636 to your computer and use it in GitHub Desktop.
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
from __future__ import annotations | |
import typing | |
from typing import Generic, TypeVar | |
T = TypeVar("T") | |
class LinkedListError(Exception): | |
pass | |
class EmptyLinkedList(LinkedListError): | |
pass | |
class LinkedListNode(Generic[T]): | |
def __init__(self, data: T = None, prev_node: LinkedListNode = None, next_node: LinkedListNode = None): | |
self.data = data | |
self.prev = prev_node | |
self.next = next_node | |
if prev_node: | |
prev_node.next = self | |
if next_node: | |
next_node.prev = self | |
class LinkedList(Generic[T]): | |
def __init__(self): | |
self.head: LinkedListNode[T] = LinkedListNode() | |
self.tail: LinkedListNode[T] = LinkedListNode(None, self.head, None) | |
self._size = 0 | |
@property | |
def empty(self) -> bool: | |
return self._size == 0 | |
def __len__(self) -> int: | |
return self._size | |
def push_front(self, data: T) -> LinkedListNode[T]: | |
node = LinkedListNode(data, self.head, self.head.next) | |
self._size += 1 | |
return node | |
def push_back(self, data: T) -> LinkedListNode[T]: | |
node = LinkedListNode(data, self.tail.prev, self.tail) | |
self._size += 1 | |
return node | |
def _remove_after(self, node: LinkedListNode[T]) -> LinkedListNode[T]: | |
self._size -= 1 | |
target = node.next | |
node.next = target.next | |
target.next.prev = node | |
return target | |
def pop_front(self) -> T: | |
if self.empty: | |
raise EmptyLinkedList() | |
return self._remove_after(self.head).data | |
def pop_back(self) -> T: | |
if self.empty: | |
raise EmptyLinkedList() | |
return self._remove_after(self.tail.prev.prev).data | |
def __iter__(self) -> T: | |
current = self.head.next | |
while current is not self.tail: | |
yield current.data | |
current = current.next | |
def __str__(self) -> str: | |
return "[" + ", ".join(map(str, self)) + "]" | |
def __repr__(self) -> str: | |
return str(self) | |
def clear(self) -> None: | |
self.head: LinkedListNode[T] = LinkedListNode() | |
self.tail: LinkedListNode[T] = LinkedListNode(None, None, self.head) | |
self._size = 0 | |
def remove_if(self, predicate: typing.Callable[[T], bool]) -> int: | |
removed = 0 | |
current = self.head.next | |
while current is not self.tail: | |
if predicate(current.data): | |
current = current.next | |
self._remove_after(current.prev.prev) | |
removed += 1 | |
else: | |
current = current.next | |
return removed | |
if __name__ == '__main__': | |
data = LinkedList() | |
data.push_back(10) | |
data.push_back(20) | |
data.push_back(30) | |
print(data) | |
print(data.pop_front() + 20) | |
data.push_front(30) | |
print(data) | |
print(sorted(data)) | |
data.remove_if(lambda x: x == 30) | |
print(data) |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment