Last active
March 7, 2016 07:19
-
-
Save davidrpugh/67686542d49fa6f00cd5 to your computer and use it in GitHub Desktop.
Simple implementations of various linked list data structures in Python.
This file contains hidden or 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 collections.abc import Sequence | |
| class LinkedList(Sequence): | |
| """Simple implementation of a linked list.""" | |
| _length = 0 | |
| head = None | |
| class Node(object): | |
| """Represents an individual node in a LinkedList""" | |
| def __init__(self, value, next): | |
| self.value = value | |
| self.next = next | |
| def __getitem__(self, key): | |
| """O(n) access to data item given its key (or index).""" | |
| if key >= self._length: | |
| raise IndexError("Index out of bounds.") | |
| else: | |
| current_node = self.head | |
| for i in range(key): | |
| current_node = current_node.next | |
| return current_node.value | |
| def __len__(self): | |
| """ | |
| O(1) access to the length of the LinkedList. | |
| Notes | |
| ----- | |
| Access to the length of the LinkedList is O(1) because we increment the | |
| value of the private_length attribute on every insertion and decrement | |
| the value of _length on every deletion. | |
| """ | |
| return self._length | |
| def __str__(self): | |
| """Human readable string representation of a LinkedList""" | |
| out = "" | |
| current_node = self.head | |
| while current_node is not None: | |
| out += str(current_node.value) + " -> " | |
| current_node = current_node.next | |
| out += "None" | |
| return out | |
| @classmethod | |
| def _find_predecessor(cls, node, value): | |
| """ | |
| O(n) traversal of the LinkedList to find the predecessor of the node | |
| containing a particular value of data. | |
| Notes | |
| ----- | |
| Finding the predecessor node is the burdensome part of removing data | |
| from a LinkedList. | |
| """ | |
| if node.next is None: | |
| return None | |
| elif node.next.value == value: | |
| return node | |
| else: | |
| return cls._find_predecessor(node.next, value) | |
| def insert(self, value): | |
| """ | |
| O(1) insertion of some data into the LinkedList. | |
| Notes | |
| ----- | |
| Inserting a new value into the linked list increments the private | |
| _length property. This side effect allows us to compute the length of a | |
| linked list is O(1). | |
| """ | |
| if self.head is None: | |
| self.head = self.Node(value, None) | |
| else: | |
| self.head = self.Node(value, self.head) | |
| self._length += 1 # SIDE EFFECT! | |
| def delete(self, value): | |
| """ | |
| O(n) removal of some data from the LinkedList. | |
| Notes | |
| ----- | |
| Removing an existing value from the linked list decrements the private | |
| _length property. This side effect allows us to compute the length of a | |
| linked list is O(1). | |
| """ | |
| if value == self.head.value: | |
| deleted_node = self.head | |
| self.head = deleted_node.next | |
| self._length -= 1 # SIDE EFFECT! | |
| else: | |
| predecessor = self._find_predecessor(self.head, value) | |
| if predecessor is not None: | |
| deleted_node = predecessor.next | |
| predecessor.next = deleted_node.next | |
| self._length -= 1 # SIDE EFFECT! | |
| else: | |
| raise ValueError("Data item is not in the LinkedList!") |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment