対数時間ランダムアクセス/挿入/削除可能リスト (UnrolledLinkedList)
(DataStructure/List/UnrolledLinkedList.py)

• View this file on GitHub
• Last update: 2022-07-31 03:52:21+09:00

概要

要素のランダムアクセスを、挿入、削除を行えるリスト。

使い方

UnrolledLinkedList()
空のリストを作成する。計算量 $O(1)$。それぞれのノードに含めることができる最大の要素数を $L(=4096)$ とする。

• __getitem__(i: int) -> int
  $i$ 番目の要素を返す。計算量 $O(N/L)$

• __setitem__(i: int, val: int) -> None
  $i$ 番目の要素に val を代入する。計算量 $O(N/L)$

• __len__() -> int
  リストの長さを返す。計算量 $O(1)$

• insert(i: int, val: int) -> None
  $i$ 番目の位置に val を挿入する。計算量 $O(N/L + L)$

• delete(i: int) -> None
  $i$ 番目の要素を削除する。計算量 $O(N/L + L)$

• dump() -> List[int]
  リストの要素を列挙した結果を返す。計算量 $O(N)$

参考

Unrolled linked list - Wikipedia

Verified with

• TestCase/AOJ/ITP2_1_C.UnrolledLinkedList.test.py

Code

class ULLNode:
    MAX_SIZE = 4096

    def __init__(self):
        self.next = None
        self.list = []

    def is_full(self):
        return len(self.list) == self.MAX_SIZE


class UnrolledLinkedList:
    def __init__(self):
        self.size = 0
        self.root = ULLNode()

    def __getitem__(self, i):
        nd, i = self._find_node(i)
        return nd.list[i]

    def __setitem__(self, i, val):
        nd, i = self._find_node(i)
        nd.list[i] = val

    def __len__(self):
        return self.size

    def _find_node(self, i):
        nd = self.root
        while i >= len(nd.list):
            i -= len(nd.list)
            nd = nd.next
        return nd, i

    def insert(self, i, val):
        nd, i = self._find_node(i - 1)
        nd.list.insert(i + 1, val)
        self.size += 1
        if nd.is_full():
            new = ULLNode()
            new.next = nd.next
            nd.next = new
            nd.list, new.list = nd.list[:len(nd.list) // 2], nd.list[len(nd.list) // 2:]

    def delete(self, i):
        nd, i = self._find_node(i)
        del nd.list[i]
        self.size -= 1

    def dump(self):
        res = []
        nd = self.root
        while nd is not None:
            for val in nd.list:
                res.append(val)
            nd = nd.next
        return res

Traceback (most recent call last):
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/documentation/build.py", line 71, in _render_source_code_stat
    bundled_code = language.bundle(stat.path, basedir=basedir, options={'include_paths': [basedir]}).decode()
                   ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
  File "/opt/hostedtoolcache/Python/3.12.4/x64/lib/python3.12/site-packages/onlinejudge_verify/languages/python.py", line 96, in bundle
    raise NotImplementedError
NotImplementedError

Back to top page