Skip to content

Instantly share code, notes, and snippets.

@Diapolo10
Last active December 5, 2023 19:26
Show Gist options
  • Save Diapolo10/97ce654b3916a8dc140fbf7564cf0dc4 to your computer and use it in GitHub Desktop.
Save Diapolo10/97ce654b3916a8dc140fbf7564cf0dc4 to your computer and use it in GitHub Desktop.
[Python] Linked List
from __future__ import annotations
from collections.abc import Callable
from typing import Any
class Node:
def __init__(self, value: object):
self.value = value
self.next_node: Node | None = None
def __repr__(self) -> str:
return f"{self.__class__.__name__}({self.value = })"
class LinkedList:
def __init__(self, head: Node | None = None):
self.head = head
self.tail = head
self.length = 0
if head is not None:
current_head = head
while current_head.next_node is not None:
self.length += 1
current_head = current_head.next_node
self.tail = current_head
def __bool__(self) -> bool:
return len(self) != 0
def __iter__(self):
return LinkedListIterator(self)
def __len__(self) -> int:
return self.length
def __str__(self) -> str:
values = ', '.join(map(lambda n: str(n.value), self))
return f"{self.__class__.__name__}([{values}])"
def append(self, value: Node | object) -> None:
if not isinstance(value, Node):
value = Node(value)
if self.tail is not None:
self.tail.next_node = value
self.tail = self.tail.next_node
else:
self.head = value
self.tail = self.head
self.length += 1
def clear(self) -> None:
if not self:
return
list_iter = iter(self)
current_node = next(list_iter)
for next_node in list_iter:
del current_node
current_node = next_node
del current_node
self.head = None
self.tail = None
self.length = 0
def copy(self) -> LinkedList:
new_list = LinkedList()
for node in self:
new_list.append(node)
return new_list
def count(self, value: object) -> int:
return sum(
node.value == value
for node in self
)
def extend(self, other: LinkedList) -> None:
for node in other:
self.append(node)
def index(self, value: object) -> int:
for idx, node in enumerate(self):
if node.value == value:
return idx
raise ValueError("Value not found")
def insert(self, index: int, value: object) -> None:
if index > len(self):
raise IndexError("Index not in list")
if index == 0:
next_node = self.head
self.head = Node(value)
self.head.next_node = next_node
else:
for idx, node in enumerate(self):
if idx == index-1:
next_node = node.next_node
node.next_node = Node(value)
node.next_node.next_node = next_node
self.length += 1
def pop(self, index: int | None = None):
if index is None:
self.tail = None
index = len(self)-1
for idx, node in enumerate(self):
if idx == index-1:
temp = node.next_node
node.next_node = None
self.length -= 1
return temp
def remove(self, value: object) -> None:
if not self:
raise ValueError("Value not found")
list_iter = iter(self)
current_node = next(list_iter)
for next_node in list_iter:
if next_node.value == value:
current_node.next_node = next_node.next_node
current_node = next_node
self.length -= 1
def reverse(self) -> None:
nodes = [node for node in self]
self.clear()
print(nodes)
while nodes:
self.append(nodes.pop().value)
def sort(self, key: Callable[[Node], Any] | None = None) -> None:
nodes = [node for node in self]
nodes.sort(key)
self.clear()
for node in nodes:
self.append(node)
class LinkedListIterator:
def __init__(self, linked_list: LinkedList):
self.node = linked_list.head
def __iter__(self):
return self
def __next__(self):
if self.node is None:
raise StopIteration
node = self.node
self.node = self.node.next_node
return node
if __name__ == '__main__':
nums = LinkedList()
for num in range(10):
nums.append(num)
print(nums) # LinkedList([0, 1, 2, 3, 4, 5, 6, 7, 8, 9])
print(len(nums)) # 10
nums.pop()
print(nums) # LinkedList([0, 1, 2, 3, 4, 5, 6, 7, 8])
print(len(nums)) # 9
nums.pop()
print(nums) # LinkedList([0, 1, 2, 3, 4, 5, 6, 7])
print(len(nums)) # 8
nums.clear()
print(nums) # LinkedList([])
print(len(nums)) # 0
for num in range(1000, 1010):
nums.append(num)
print(nums) # LinkedList([1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009])
print(len(nums)) # 10
nums.remove(1004)
print(nums) # LinkedList([1000, 1001, 1002, 1003, 1005, 1006, 1007, 1008, 1009])
print(len(nums)) # 9
nums.insert(4, 1004)
print(nums) # LinkedList([1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009])
print(len(nums)) # 10
print(nums.count(1008)) # 1
print(nums.count(25565)) # 0
copied = nums.copy()
nums.reverse()
print(nums) # LinkedList([1009, 1008, 1007, 1006, 1005, 1004, 1003, 1002, 1001, 1000])
print(len(nums)) # 10
print(copied) # LinkedList([1000, 1001, 1002, 1003, 1004, 1005, 1006, 1007, 1008, 1009])
print(len(copied)) # 10
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment