Pythonで学ぶ データ構造入門 List編

TL;DR

データ構造の基本であるList(LinkedList)やHashMap、Queue、Dequeを自分で実装して理解を深めようという趣旨でやっていきます。

まずはLinkedListを作ってみる

LinkedListとは、リストの各々の要素に次の要素への参照をつけておくことで一連のデータを表現できるデータ構造です。

このように、それぞれの要素が次への参照とデータを持っています。
これをPythonで実装してみます。
まずはそれぞれの要素のクラスです。

```python:要素
class Element:
"""
Element(data, next)

LinkedListのそれぞれの要素のクラス。
dataはこの要素が表すデータ。
nextはこの次の要素の参照。
"""
def __init__(self, data, next=None):
    self.data = data
    self.next = next

次にリスト本体を実装してみます。

```python:LinkedList
class LinkedList:
    def __init__(self):
        self.first = None

    @property
    def is_empty(self):
        return self.first is None

    def append(self, data):
        if self.is_empty:
            self.first = Element(data)
            return
        nxt = self.first
        while nxt.next is not None:
            nxt = nxt.next
        nxt.next = Element(data)

    def pop(self):
        if self.is_empty:
            raise ValueError

        nxt = self.first
        while nxt.next is not None:
            nxt = nxt.next

        # 最後の要素のデータを一時変数に退避
        last = nxt.next.data
        # 最後の要素への参照を消す
        nxt.next = None
        return last

    def remove(self, idx):
        # 最初ならself.firstを変更
        if idx == 0:
            f = self.first
            self.first = f.next
            return f.data

        size = len(self)
        if idx >= size or idx < 0:
            raise IndexError(idx)
        if self.is_empty:
            raise ValueError

        # 最後ならpop
        if idx == size - 1:
            return self.pop()

        nxt = self.first
        for _ in range(idx - 1):
            nxt = nxt.next
        rem = nxt.next
        nxt.next = rem.next
        return rem.data

    def insert(self, idx, data):
        # 最初ならself.firstを変更
        if idx == 0:
            self.first = Element(data, self.first)
            return

        size = len(self)
        if idx > size or idx < 0:
            raise IndexError(idx)

        # 最後+1ならappend
        if idx == size:
            self.append(data)
            return

        nxt = self.first
        for _ in range(idx):
            nxt = nxt.next
        nxt.next = Element(data, nxt.next)

    def __iter__(self):
        nxt = self.first
        while nxt.next is not None:
            yield nxt.data
            nxt = nxt.next

    def __len__(self):
        if self.is_empty:
            return 0
        nxt = self.first
        ret = 1
        while nxt.next is not None:
            nxt = nxt.next
            ret += 1
        return ret

    def __getitem__(self, idx):
        if idx >= len(self) or idx < 0:
            raise IndexError(idx)
        if self.is_empty:
            raise ValueError
        nxt = self.first
        for _ in range(idx):
            nxt = nxt.next
        return nxt.data

    def __setitem__(self, idx, val):
        if idx >= len(self) or idx < 0:
            raise IndexError(idx)
        if self.is_empty:
            raise ValueError
        nxt = self.first
        for _ in range(idx):
            nxt = nxt.next
        nxt.data = val

こんな感じですね。
これが一番単純なLinkedListの実装です。
ですけど、結構非効率的ですね。

例えば、一番後ろのデータを取得するために最初から全部辿っています。
データにアクセスするためにすべて前からアクセスするのでは、後半のデータにアクセスする際に非効率になってしまいます。
これを解決するのが双方向リストというものです。

(次回があれば)これを双方向リストに改造してみたいと思います。
今日のところはここまでにしましょう。それがいい。