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

TL;DR

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

まずはLinkedListを作ってみる

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

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

要素

class Element:
    """
    Element(data, next)

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

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

LinkedList

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

    def append(self, data):
        if not self:
            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 not self:
            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 not self:
            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.first is None:
            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 not self:
            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 not self:
            raise ValueError
        nxt = self.first
        for _ in range(idx):
            nxt = nxt.next
        nxt.data = val

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

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

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