Linked lists

class Empty(Exception):
    pass

class SinglyLinkedList:

    class _Node:
        __slots__ = "element", "next"            # two fields, no per-object dict
        def __init__(self, element, nxt):
            self.element = element
            self.next = nxt

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

    def add_head(self, e):                       # O(1)
        self.head = self._Node(e, self.head)     # new node points to old head
        if self.size == 0:
            self.tail = self.head                # first node is also the last
        self.size += 1

    def add_tail(self, e):                       # O(1), thanks to the tail reference
        newest = self._Node(e, None)
        if self.size == 0:
            self.head = newest
        else:
            self.tail.next = newest              # link the old tail FIRST...
        self.tail = newest                       # ...then move tail
        self.size += 1

    def remove_head(self):                       # O(1)
        if self.size == 0:
            raise Empty("list is empty")
        e = self.head.element
        self.head = self.head.next               # old first node is now unreachable
        self.size -= 1
        if self.size == 0:
            self.tail = None
        return e

    def remove_tail(self):                       # O(n): must find the node before tail
        if self.size == 0:
            raise Empty("list is empty")
        if self.size == 1:
            return self.remove_head()
        walk = self.head
        while walk.next is not self.tail:
            walk = walk.next
        e = self.tail.element
        walk.next = None
        self.tail = walk
        self.size -= 1
        return e

    def find(self, e):                           # O(n)
        walk = self.head
        while walk is not None and walk.element != e:
            walk = walk.next
        return walk                              # the node, or None

    def delete(self, e):                         # O(n): delete first node holding e
        prev, walk = None, self.head
        while walk is not None and walk.element != e:
            prev, walk = walk, walk.next         # remember the node BEFORE walk
        if walk is None:
            return False
        if prev is None:
            self.head = walk.next                # deleting the head
        else:
            prev.next = walk.next                # link around walk
        if walk is self.tail:
            self.tail = prev
        self.size -= 1
        return True

    def __iter__(self):
        walk = self.head
        while walk is not None:
            yield walk.element
            walk = walk.next

L = SinglyLinkedList()
for code in ["MSP", "ATL", "BOS"]:
    L.add_tail(code)
L.add_head("LAX"); print(list(L))
L.add_tail("MIA"); print(list(L))
print(L.remove_head(), L.remove_tail(), list(L), "tail =", L.tail.element)
print(L.find("ATL").element, L.find("SFO"), L.delete("ATL"), list(L))

['LAX', 'MSP', 'ATL', 'BOS']
['LAX', 'MSP', 'ATL', 'BOS', 'MIA']
LAX MIA ['MSP', 'ATL', 'BOS'] tail = BOS
ATL None True ['MSP', 'BOS']

class CircularList:
    """Circularly linked list, kept by one reference: current (the 'last' node)."""

    class _Node:
        __slots__ = "element", "next"
        def __init__(self, element, nxt):
            self.element, self.next = element, nxt

    def __init__(self):
        self.current = None
        self.size = 0

    def add(self, e):                       # insert after current, become current
        newest = self._Node(e, None)
        if self.current is None:
            newest.next = newest            # a one-node circle points at itself
        else:
            newest.next = self.current.next
            self.current.next = newest
        self.current = newest
        self.size += 1

    def front(self):
        return self.current.next.element    # the node after 'last' is the 'first'

    def rotate(self):                       # O(1): one reference moves
        self.current = self.current.next

C = CircularList()
for app in ["editor", "browser", "music"]:
    C.add(app)
schedule = []
for turn in range(7):
    schedule.append(C.front())              # give this app its time slice
    C.rotate()                              # move on: no removal, no insertion
print(schedule)

['editor', 'browser', 'music', 'editor', 'browser', 'music', 'editor']

s = p.next
q = new node(X)
q.prev = p              # new node's own two links
q.next = s
s.prev = q              # then the neighbours' links
p.next = q

p.prev.next = p.next
p.next.prev = p.prev
# nothing in the list refers to p any more; return p.element

class _DoublyLinkedBase:
    """Doubly linked list with header and trailer sentinels."""

    class _Node:
        __slots__ = "element", "prev", "next"
        def __init__(self, element, prev, nxt):
            self.element, self.prev, self.next = element, prev, nxt

    def __init__(self):
        self._header = self._Node(None, None, None)    # sentinels hold no element
        self._trailer = self._Node(None, None, None)
        self._header.next = self._trailer
        self._trailer.prev = self._header
        self._size = 0

    def __len__(self):
        return self._size

    def is_empty(self):
        return self._size == 0

    def _insert_between(self, e, predecessor, successor):     # O(1)
        newest = self._Node(e, predecessor, successor)       # new node's two links
        predecessor.next = newest                            # neighbours' two links
        successor.prev = newest
        self._size += 1
        return newest

    def _delete_node(self, node):                            # O(1)
        predecessor, successor = node.prev, node.next
        predecessor.next = successor                         # link around node
        successor.prev = predecessor
        self._size -= 1
        element = node.element
        node.prev = node.next = node.element = None          # mark node as dead
        return element

class LinkedDeque(_DoublyLinkedBase):
    def first(self):
        if self.is_empty(): raise IndexError("deque is empty")
        return self._header.next.element
    def last(self):
        if self.is_empty(): raise IndexError("deque is empty")
        return self._trailer.prev.element
    def add_first(self, e):
        self._insert_between(e, self._header, self._header.next)
    def add_last(self, e):
        self._insert_between(e, self._trailer.prev, self._trailer)
    def delete_first(self):
        if self.is_empty(): raise IndexError("deque is empty")
        return self._delete_node(self._header.next)
    def delete_last(self):
        if self.is_empty(): raise IndexError("deque is empty")
        return self._delete_node(self._trailer.prev)

D = LinkedDeque()
D.add_last(5); D.add_first(3); D.add_first(7)
print(D.first(), D.last(), len(D))
print(D.delete_last(), D.delete_first(), D.first(), len(D))

7 5 3
5 7 3 1

class PositionalList(_DoublyLinkedBase):

    class Position:
        """A marker for one element's location. Users never see nodes."""
        __slots__ = "_container", "_node"
        def __init__(self, container, node):
            self._container, self._node = container, node
        def element(self):
            return self._node.element
        def __eq__(self, other):                  # same node = same position
            return type(other) is type(self) and other._node is self._node
        def __ne__(self, other):
            return not (self == other)

    def _validate(self, p):                       # position -> node, with checks
        if not isinstance(p, self.Position):
            raise TypeError("p must be a proper Position type")
        if p._container is not self:
            raise ValueError("p does not belong to this container")
        if p._node.next is None:                  # _delete_node cleared it
            raise ValueError("p is no longer valid")
        return p._node

    def _make_position(self, node):               # node -> position (never a sentinel)
        if node is self._header or node is self._trailer:
            return None
        return self.Position(self, node)

    # accessors
    def first(self):     return self._make_position(self._header.next)
    def last(self):      return self._make_position(self._trailer.prev)
    def before(self, p): return self._make_position(self._validate(p).prev)
    def after(self, p):  return self._make_position(self._validate(p).next)
    def __iter__(self):
        cursor = self.first()
        while cursor is not None:
            yield cursor.element()
            cursor = self.after(cursor)

    # updates (all O(1))
    def _insert_between(self, e, predecessor, successor):
        return self._make_position(super()._insert_between(e, predecessor, successor))
    def add_first(self, e):     return self._insert_between(e, self._header, self._header.next)
    def add_last(self, e):      return self._insert_between(e, self._trailer.prev, self._trailer)
    def add_before(self, p, e):
        node = self._validate(p)
        return self._insert_between(e, node.prev, node)
    def add_after(self, p, e):
        node = self._validate(p)
        return self._insert_between(e, node, node.next)
    def delete(self, p):
        return self._delete_node(self._validate(p))
    def replace(self, p, e):
        node = self._validate(p)
        old = node.element
        node.element = e
        return old

L = PositionalList()
p = L.add_last(8);         print("add_last(8)      ", list(L))
print("first() == p     ", L.first() == p)
q = L.add_after(p, 5);     print("add_after(p, 5)  ", list(L))
print("before(q) == p   ", L.before(q) == p)
r = L.add_before(q, 3);    print("add_before(q, 3) ", list(L))
print("r.element()      ", r.element())
print("after(p) == r    ", L.after(p) == r)
print("before(p)        ", L.before(p))
s = L.add_first(9);        print("add_first(9)     ", list(L))
print("delete(last())   ", L.delete(L.last()), list(L))
print("replace(p, 7)    ", L.replace(p, 7), list(L))
try:
    L.after(q)                                    # q was deleted above
except ValueError as err:
    print("after(q)          ValueError:", err)

add_last(8)       [8]
first() == p      True
add_after(p, 5)   [8, 5]
before(q) == p    True
add_before(q, 3)  [8, 3, 5]
r.element()       3
after(p) == r     True
before(p)         None
add_first(9)      [9, 8, 3, 5]
delete(last())    5 [9, 8, 3]
replace(p, 7)     8 [9, 7, 3]
after(q)          ValueError: p is no longer valid

def insertion_sort(L):
    """Sort a PositionalList of comparable elements into nondecreasing order."""
    if len(L) > 1:
        marker = L.first()                   # end of the sorted prefix
        while marker != L.last():
            pivot = L.after(marker)          # next element to place
            value = pivot.element()
            if value > marker.element():     # already in the right place
                marker = pivot               # the sorted prefix grows by one
            else:
                walk = marker                # walk left to find the spot
                while walk != L.first() and L.before(walk).element() > value:
                    walk = L.before(walk)
                L.delete(pivot)
                L.add_before(walk, value)    # O(1) re-link, no shifting

L = PositionalList()
for x in [15, 22, 25, 29, 36, 23, 53, 11, 42]:
    L.add_last(x)
insertion_sort(L)
print(list(L))

[11, 15, 22, 23, 25, 29, 36, 42, 53]

class FavoritesList:
    """Elements kept in a PositionalList sorted by access count, highest first."""

    class _Item:
        __slots__ = "_value", "_count"
        def __init__(self, e):
            self._value, self._count = e, 0

    def __init__(self):
        self._data = PositionalList()

    def _find_position(self, e):                  # O(n) linear search
        walk = self._data.first()
        while walk is not None and walk.element()._value != e:
            walk = self._data.after(walk)
        return walk

    def _move_up(self, p):                        # restore the sorted order
        if p != self._data.first():
            cnt = p.element()._count
            walk = self._data.before(p)
            if cnt > walk.element()._count:       # out of order: walk backwards
                while (walk != self._data.first() and
                       cnt > self._data.before(walk).element()._count):
                    walk = self._data.before(walk)
                self._data.add_before(walk, self._data.delete(p))

    def access(self, e):
        p = self._find_position(e)
        if p is None:
            p = self._data.add_last(self._Item(e))   # new elements start at the end
        p.element()._count += 1
        self._move_up(p)

    def remove(self, e):
        p = self._find_position(e)
        if p is not None:
            self._data.delete(p)

    def top(self, k):                             # O(k): the first k are the answer
        walk = self._data.first()
        for _ in range(k):
            item = walk.element()
            yield item._value, item._count
            walk = self._data.after(walk)

class FavoritesListMTF(FavoritesList):
    """Same ADT, ordered by recency: every access moves the element to the front."""

    def _move_up(self, p):                        # O(1)
        if p != self._data.first():
            self._data.add_first(self._data.delete(p))

    def top(self, k):                             # O(kn): order no longer helps
        temp = PositionalList()
        for item in self._data:                   # copy every item: O(n)
            temp.add_last(item)
        for _ in range(k):                        # k times: find and remove the max
            high = temp.first()
            walk = temp.after(high)
            while walk is not None:
                if walk.element()._count > high.element()._count:
                    high = walk
                walk = temp.after(walk)
            yield high.element()._value, high.element()._count
            temp.delete(high)

# FavoritesList     keeps items sorted by access count (highest first).
# FavoritesListMTF  moves each accessed item to the front instead.
# Both count .steps = how many nodes their searches walk past.

for n in [10, 20, 40, 80]:
    A, B = FavoritesList(), FavoritesListMTF()
    for e in range(1, n + 1):        # element 1 accessed n times, then element 2 ...
        for _ in range(n):
            A.access(e)
            B.access(e)
    print(f"n = {n:2}   sorted list: {A.steps:7,} steps   move-to-front: {B.steps:5,} steps")

F = FavoritesListMTF()
for site in "ACABACAAB":
    F.access(site)
F.access("D")
print("list order (most recent first):", [item._value for item in F._data])
print("top(2):", list(F.top(2)))

n = 10   sorted list:     450 steps   move-to-front:    45 steps
n = 20   sorted list:   3,800 steps   move-to-front:   190 steps
n = 40   sorted list:  31,200 steps   move-to-front:   780 steps
n = 80   sorted list: 252,800 steps   move-to-front: 3,160 steps
list order (most recent first): ['D', 'B', 'A', 'C']
top(2): [('A', 5), ('B', 2)]