Last active
January 11, 2021 16:35
-
-
Save fhpriamo/32d8c476aeef790562485f3d80f924f0 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
class LinkedList(): | |
"""A singly general purpose linked list implementation.""" | |
class _Node(): | |
"""A singly linked node.""" | |
def __init__(self, value, next=None): | |
self.next = next | |
self.value = value | |
@property | |
def has_next(self): | |
return this.next is None | |
def __repr__(self): | |
return f'({self.value} -> {self.next and self.next.value})' | |
def __str__(self): | |
return self.__repr__() | |
class _LinkedListIterator(): | |
"""An iterator for the singly linked list.""" | |
def __init__(self, linked_list): | |
self._linked_list = linked_list | |
self._current = None | |
def __iter__(self): | |
return self | |
def __next__(self): | |
if self._current is None: | |
self._current = self._linked_list._head | |
else: | |
self._current = self._current.next | |
if self._current is None: | |
raise StopIteration() | |
return self._current.value | |
def __init__(self, *initial_values): | |
self._head = None | |
self._tail = None | |
self._size = 0 | |
self._next = None | |
for e in reversed(initial_values): | |
self.prepend(e) | |
def __len__(self): | |
return self._size | |
@property | |
def is_empty(self): | |
"""Whether the list is empty or not.""" | |
return self._size == 0 | |
def prepend(self, e): | |
"""Links an element to the head of the list.""" | |
self._head = self._Node(e, self._head) | |
if self.is_empty: | |
self._tail = self._head | |
self._size += 1 | |
def append(self, e): | |
"""Links an element to the tail of the list.""" | |
new_node = self._Node(e) | |
if self.is_empty: | |
self._tail = new_node | |
self._head = self._tail | |
else: | |
self._tail.next = new_node | |
self._tail = self._tail.next | |
self._size += 1 | |
def map(self, fn): | |
"""Maps a function to all values in the list, returning a new list.""" | |
return LinkedList(*map(fn, self)) | |
def __iter__(self): | |
return self._LinkedListIterator(self) | |
def __repr__(self): | |
return f'LinkedList({self.__str__()})' | |
def __str__(self): | |
return ', '.join(map(repr, self)) | |
def __getitem__(self, index): | |
if self.is_empty or index >= self._size or index < 0: | |
raise IndexError(f'LinkedList(size={self._size}) has no index {index}') | |
self_iter = iter(self) | |
for _ in range(0, index + 1): | |
cur = next(self_iter) | |
return cur |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment