linked_list

ソースコード

from titan_pylib.data_structures.list.linked_list import LinkedList

view on github

展開済みコード

  1# from titan_pylib.data_structures.list.linked_list import LinkedList
  2from typing import Generic, TypeVar, Optional, Iterator, Iterable
  3
  4T = TypeVar("T")
  5
  6
  7class LinkedList(Generic[T]):
  8    """双方向連結リストです。"""
  9
 10    ___slots__ = ("top", "tail", "it", "_len")
 11
 12    class LinkedListNode:
 13
 14        def __init__(self, key: T) -> None:
 15            self._key = key
 16            self._pre: Optional["LinkedList.LinkedListNode"] = None
 17            self._nxt: Optional["LinkedList.LinkedListNode"] = None
 18
 19        def key(self) -> T:
 20            return self._key
 21
 22        def set_key(self, key: T) -> None:
 23            self._key = key
 24
 25        def __add__(self, _inc: int):
 26            assert _inc == 1
 27            return self._nxt
 28
 29        def __iadd__(self, _inc: int):
 30            assert _inc == 1
 31            return self._nxt
 32
 33        def __sub__(self, _dec: int):
 34            assert _dec == 1
 35            return self._pre
 36
 37        def __isub__(self, _dec: int):
 38            assert _dec == 1
 39            return self._pre
 40
 41        def __str__(self):
 42            return f"LinkedList.LinkedListNode({self._key})"
 43
 44        __repr__ = __str__
 45
 46    def __init__(self, a: Iterable[T] = []):
 47        self.top: Optional[LinkedList.LinkedListNode] = None
 48        self.tail: Optional[LinkedList.LinkedListNode] = None
 49        self._len = 0
 50        for e in a:
 51            self.append(e)
 52
 53    def extend(self, other: "LinkedList") -> None:
 54        if self.top is None:
 55            self.top = other.top
 56        if other.tail is not None:
 57            self.tail = other.tail
 58
 59    def append(self, key: T) -> LinkedListNode:
 60        node = self.make_node(key)
 61        self.append_iter(node)
 62        return node
 63
 64    def append_iter(self, node: LinkedListNode) -> None:
 65        assert node._nxt is None
 66        self._len += 1
 67        if not self.top:
 68            self.top = node
 69        node._pre = self.tail
 70        if self.tail:
 71            self.tail._nxt = node
 72        self.tail = node
 73
 74    def appendleft(self, key: T) -> LinkedListNode:
 75        self._len += 1
 76        node = self.make_node(key)
 77        if not self.tail:
 78            self.tail = node
 79        node._nxt = self.top
 80        if self.top:
 81            self.top._pre = node
 82        self.top = node
 83        return node
 84
 85    def pop(self) -> T:
 86        self._len -= 1
 87        node = self.tail
 88        if node._pre:
 89            node._pre._nxt = node._nxt
 90        else:
 91            self.top = node._pre
 92        self.tail = node._pre
 93        return node.key()
 94
 95    def popleft(self) -> T:
 96        self._len -= 1
 97        node = self.top
 98        if node._nxt:
 99            node._nxt._pre = node._pre
100        else:
101            self.tail = node._nxt
102        self.top = node._nxt
103        return node.key()
104
105    def get_front_iter(self) -> Optional[LinkedListNode]:
106        return self.top
107
108    def get_back_iter(self) -> Optional[LinkedListNode]:
109        return self.tail
110
111    # pos -> new_node -> pos._nxt
112    def insert_iter_nxt(
113        self, pos_node: LinkedListNode, new_node: LinkedListNode
114    ) -> None:
115        self._len += 1
116        new_node._nxt = pos_node._nxt
117        new_node._pre = pos_node
118        if pos_node._nxt:
119            pos_node._nxt._pre = new_node
120        else:
121            self.tail = new_node
122        pos_node._nxt = new_node
123
124    # nxt._pre -> new -> nxt
125    def insert_iter_pre(
126        self, nxt_node: LinkedListNode, new_node: LinkedListNode
127    ) -> None:
128        self._len += 1
129        if nxt_node._pre:
130            nxt_node._pre._nxt = new_node
131        else:
132            self.top = new_node
133        new_node._pre = nxt_node._pre
134        new_node._nxt = nxt_node
135        nxt_node._pre = new_node
136
137    def remove_iter(self, node: LinkedListNode) -> None:
138        self._len -= 1
139        if node._pre:
140            node._pre._nxt = node._nxt
141        else:
142            self.top = node._nxt
143        if node._nxt:
144            node._nxt._pre = node._pre
145        else:
146            assert self.tail is node
147            self.tail = node._pre
148
149    def iter_node(self) -> LinkedListNode:
150        node = self.top
151        while node:
152            nxt = node._nxt
153            yield node
154            node = nxt
155
156    def iter_node_rev(self) -> LinkedListNode:
157        node = self.tail
158        while node:
159            pre = node._pre
160            yield node
161            node = pre
162
163    def __reversed__(self) -> Iterator[T]:
164        node = self.tail
165        while node:
166            pre = node._pre
167            yield node.key()
168            node = pre
169
170    def tolist(self) -> list[T]:
171        return [x for x in self]
172
173    def make_node(self, key: T) -> LinkedListNode:
174        return self.LinkedListNode(key)
175
176    def __iter__(self) -> Iterator[T]:
177        self.it = self.top
178        return self
179
180    def __len__(self):
181        return self._len
182
183    def __next__(self) -> T:
184        if self.it is None:
185            raise StopIteration
186        key = self.it.key()
187        self.it += 1
188        return key
189
190    def __str__(self):
191        return str(self.tolist())
192
193    def __repr__(self):
194        return f"{self.__class__.__name__}({self})"

仕様

class LinkedList(a: Iterable[T] = [])[source]

Bases: Generic[T]

双方向連結リストです。

class LinkedListNode(key: T)[source]

Bases: object

key() → T[source]
set_key(key: T) → None[source]
append(key: T) → LinkedListNode[source]
append_iter(node: LinkedListNode) → None[source]
appendleft(key: T) → LinkedListNode[source]
extend(other: LinkedList) → None[source]
get_back_iter() → LinkedListNode | None[source]
get_front_iter() → LinkedListNode | None[source]
insert_iter_nxt(pos_node: LinkedListNode, new_node: LinkedListNode) → None[source]
insert_iter_pre(nxt_node: LinkedListNode, new_node: LinkedListNode) → None[source]
iter_node() → LinkedListNode[source]
iter_node_rev() → LinkedListNode[source]
make_node(key: T) → LinkedListNode[source]
pop() → T[source]
popleft() → T[source]
remove_iter(node: LinkedListNode) → None[source]
tolist() → list[T][source]