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 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 | |
| _tail = 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 | |
| def _find_predecessor(self, 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. | |
| """ | |
| predecessor = None | |
| current_node = self._head | |
| while current_node.next is not None: | |
| if current_node.next.value == value: | |
| predecessor = current_node | |
| break | |
| else: | |
| current_node = current_node.next | |
| return predecessor | |
| def prepend(self, value): | |
| """ | |
| O(1) insertion of data onto the head of the LinkedList. | |
| Notes | |
| ----- | |
| Inserting a new value into the LinkedList 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) | |
| self._tail = self._head | |
| else: | |
| self._head = self.Node(value, self._head) | |
| self._length += 1 # SIDE EFFECT! | |
| def append(self, value): | |
| """ | |
| O(1) insertion of data onto the tail of 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._tail is None: | |
| self._tail = self.Node(value, None) | |
| self._head = self._tail | |
| else: | |
| new_node = self.Node(value, None) | |
| self._tail.next = new_node | |
| self._tail = new_node | |
| self._length += 1 # SIDE EFFECT! | |
| def remove(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: | |
| self.remove_head() | |
| else: | |
| predecessor = self._find_predecessor(value) | |
| if predecessor is not None: | |
| deleted_node = predecessor.next | |
| predecessor.next = deleted_node.next | |
| self._length -= 1 # SIDE EFFECT! | |
| else: | |
| raise ValueError("Item is not in the LinkedList!") | |
| def remove_head(self): | |
| """O(1) removal of the head of a LinkedList.""" | |
| if self._head is not None: | |
| self._head = self._head.next | |
| self._length -= 1 # SIDE EFFECT! | |
| def remove_tail(self): | |
| """O(n) removal of the tail of a LinkedList.""" | |
| if self._tail is not None: | |
| predecessor = self._find_predecessor(self._tail.value) | |
| predecessor.next = None | |
| self._tail = predecessor | |
| self._length -= 1 # SIDE EFFECT! |
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
| import linked_list | |
| class Stack(object): | |
| """Simple implementation of a LIFO container using a LinkedList.""" | |
| _linked_list = linked_list.LinkedList() | |
| def peek(self): | |
| """Return the value from the top of the Stack.""" | |
| return self._linked_list[0] | |
| def pop(self): | |
| """O(1) Removal (and return) of the value from the top of the Stack.""" | |
| value = self.peek() | |
| self._linked_list.remove_head() | |
| return value | |
| def push(self, value): | |
| """O(1) insertion of data onto the top of the Stack.""" | |
| self._linked_list.prepend(value) | |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment