linked_lists.py

# Linked lists are data structures made of chained elements connected either with one or with two others.

from collections import namedtuple

# Singly linked list node (immutable)
_Node = namedtuple('Node', ['value', 'next'])

# or mutable


class Node(object):

    def __init__(self, value, next=None):
        self.value = value
        self.next = next

# Doubly linked list node


class DLNode(object):

    def __init__(self, value, prev=None, next=None):
        self.value = value
        self.prev = prev
        self.next = next

# Singly linked list


class SinglyLinkedList(object):

    def __init__(self):
        self.head = None
        self.tail = None

    def add(self, value):
        if not self.head:
            self.head = Node(value)
            self.tail = self.head
        else:
            self.tail.next = Node(value)
            self.tail = self.tail.next

    def remove(self, value):
        p1 = self.head
        p2 = self.head.next
        if not p2 and p1.value == value:
            self.head = None
            return
        while p2:
            if p2.value == value:
                if p2.next:
                    p1.next = p2.next
                else:
                    p1.next = None
                return
            p1 = p2
            p2 = p2.next

# LL is circular if the tail node is connected to the head node.


class DoublyLinkedListWithASentinel(object):

    def __init__(self):
        self.S = DLNode(None)

    def add(self, value):
        node = DLNode(value, self.S.prev, self.S)
        if not self.S.next:
            self.S.next = node
            self.S.prev = node
            node.prev = self.S
        else:
            self.S.prev.next = node
            self.S.prev = node

    def remove(self, value):
        p1 = self.S.next
        while p1 and p1.value is not None:
            if p1.value == value:
                if p1.next:
                    p1.prev.next = p1.next
                    p1.next.prev = p1.prev
                else:
                    p1.prev.next = None
                return
            p1 = p1.next