Source code for titan_pylib.data_structures.list.linked_list

  1from typing import Generic, TypeVar, Optional, Iterator, Iterable
  2
  3T = TypeVar("T")
  4
  5

[docs]
  6class LinkedList(Generic[T]):
  7    """双方向連結リストです。"""
  8
  9    ___slots__ = ("top", "tail", "it", "_len")
 10

[docs]
 11    class LinkedListNode:
 12
 13        def __init__(self, key: T) -> None:
 14            self._key = key
 15            self._pre: Optional["LinkedList.LinkedListNode"] = None
 16            self._nxt: Optional["LinkedList.LinkedListNode"] = None
 17

[docs]
 18        def key(self) -> T:
 19            return self._key

 20

[docs]
 21        def set_key(self, key: T) -> None:
 22            self._key = key

 23
 24        def __add__(self, _inc: int):
 25            assert _inc == 1
 26            return self._nxt
 27
 28        def __iadd__(self, _inc: int):
 29            assert _inc == 1
 30            return self._nxt
 31
 32        def __sub__(self, _dec: int):
 33            assert _dec == 1
 34            return self._pre
 35
 36        def __isub__(self, _dec: int):
 37            assert _dec == 1
 38            return self._pre
 39
 40        def __str__(self):
 41            return f"LinkedList.LinkedListNode({self._key})"
 42
 43        __repr__ = __str__

 44
 45    def __init__(self, a: Iterable[T] = []):
 46        self.top: Optional[LinkedList.LinkedListNode] = None
 47        self.tail: Optional[LinkedList.LinkedListNode] = None
 48        self._len = 0
 49        for e in a:
 50            self.append(e)
 51

[docs]
 52    def extend(self, other: "LinkedList") -> None:
 53        if self.top is None:
 54            self.top = other.top
 55        if other.tail is not None:
 56            self.tail = other.tail

 57

[docs]
 58    def append(self, key: T) -> LinkedListNode:
 59        node = self.make_node(key)
 60        self.append_iter(node)
 61        return node

 62

[docs]
 63    def append_iter(self, node: LinkedListNode) -> None:
 64        assert node._nxt is None
 65        self._len += 1
 66        if not self.top:
 67            self.top = node
 68        node._pre = self.tail
 69        if self.tail:
 70            self.tail._nxt = node
 71        self.tail = node

 72

[docs]
 73    def appendleft(self, key: T) -> LinkedListNode:
 74        self._len += 1
 75        node = self.make_node(key)
 76        if not self.tail:
 77            self.tail = node
 78        node._nxt = self.top
 79        if self.top:
 80            self.top._pre = node
 81        self.top = node
 82        return node

 83

[docs]
 84    def pop(self) -> T:
 85        self._len -= 1
 86        node = self.tail
 87        if node._pre:
 88            node._pre._nxt = node._nxt
 89        else:
 90            self.top = node._pre
 91        self.tail = node._pre
 92        return node.key()

 93

[docs]
 94    def popleft(self) -> T:
 95        self._len -= 1
 96        node = self.top
 97        if node._nxt:
 98            node._nxt._pre = node._pre
 99        else:
100            self.tail = node._nxt
101        self.top = node._nxt
102        return node.key()

103

[docs]
104    def get_front_iter(self) -> Optional[LinkedListNode]:
105        return self.top

106

[docs]
107    def get_back_iter(self) -> Optional[LinkedListNode]:
108        return self.tail

109
110    # pos -> new_node -> pos._nxt

[docs]
111    def insert_iter_nxt(
112        self, pos_node: LinkedListNode, new_node: LinkedListNode
113    ) -> None:
114        self._len += 1
115        new_node._nxt = pos_node._nxt
116        new_node._pre = pos_node
117        if pos_node._nxt:
118            pos_node._nxt._pre = new_node
119        else:
120            self.tail = new_node
121        pos_node._nxt = new_node

122
123    # nxt._pre -> new -> nxt

[docs]
124    def insert_iter_pre(
125        self, nxt_node: LinkedListNode, new_node: LinkedListNode
126    ) -> None:
127        self._len += 1
128        if nxt_node._pre:
129            nxt_node._pre._nxt = new_node
130        else:
131            self.top = new_node
132        new_node._pre = nxt_node._pre
133        new_node._nxt = nxt_node
134        nxt_node._pre = new_node

135

[docs]
136    def remove_iter(self, node: LinkedListNode) -> None:
137        self._len -= 1
138        if node._pre:
139            node._pre._nxt = node._nxt
140        else:
141            self.top = node._nxt
142        if node._nxt:
143            node._nxt._pre = node._pre
144        else:
145            assert self.tail is node
146            self.tail = node._pre

147

[docs]
148    def iter_node(self) -> LinkedListNode:
149        node = self.top
150        while node:
151            nxt = node._nxt
152            yield node
153            node = nxt

154

[docs]
155    def iter_node_rev(self) -> LinkedListNode:
156        node = self.tail
157        while node:
158            pre = node._pre
159            yield node
160            node = pre

161
162    def __reversed__(self) -> Iterator[T]:
163        node = self.tail
164        while node:
165            pre = node._pre
166            yield node.key()
167            node = pre
168

[docs]
169    def tolist(self) -> list[T]:
170        return [x for x in self]

171

[docs]
172    def make_node(self, key: T) -> LinkedListNode:
173        return self.LinkedListNode(key)

174
175    def __iter__(self) -> Iterator[T]:
176        self.it = self.top
177        return self
178
179    def __len__(self):
180        return self._len
181
182    def __next__(self) -> T:
183        if self.it is None:
184            raise StopIteration
185        key = self.it.key()
186        self.it += 1
187        return key
188
189    def __str__(self):
190        return str(self.tolist())
191
192    def __repr__(self):
193        return f"{self.__class__.__name__}({self})"