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
| class LinkedList(object): | |
| """Simple implementation of a linked list.""" | |
| head = None | |
| class Node(object): | |
| """Represents an individual node in a LinkedList""" | |
| def __init__(self, data, next): | |
| self.data = data | |
| self.next = next | |
| 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.data) + " -> " | |
| current_node = current_node.next | |
| out += "None" | |
| return out | |
| @classmethod | |
| def _find_predecessor(cls, node, data): | |
| """Find the predecessor of a node containing some data.""" | |
| if node.next is None: | |
| return None | |
| elif node.next.data == data: | |
| return node | |
| else: | |
| return cls._find_predecessor(node.next, data) | |
| def insert(self, data): | |
| """O(1) insertion of some data into the LinkedList.""" | |
| if self.head is None: | |
| self.head = self.Node(data, None) | |
| else: | |
| self.head = self.Node(data, self.head) | |
| def delete(self, data): | |
| """O(n) removal of some data from the LinkedList.""" | |
| if data == self.head.data: | |
| deleted_node = self.head | |
| self.head = deleted_node.next | |
| else: | |
| predecessor = self._find_predecessor(self.head, data) | |
| if predecessor is not None: | |
| deleted_node = predecessor.next | |
| predecessor.next = deleted_node.next | |
| 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