Simple implementations of various linked list data structures in Python.

linked_list.py

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!

stack.py

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)