Help us understand the problem. What is going on with this article?

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

TL;DR

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

まずはLinkedListを作ってみる

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

data structure.png

このように、それぞれの要素が次への参照とデータを持っています。
これを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の実装です。
ですけど、結構非効率的ですね。

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

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

Why not register and get more from Qiita?
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
Comments
No comments
Sign up for free and join this conversation.
If you already have a Qiita account
Why do not you register as a user and use Qiita more conveniently?
You need to log in to use this function. Qiita can be used more conveniently after logging in.
You seem to be reading articles frequently this month. Qiita can be used more conveniently after logging in.
  1. We will deliver articles that match you
    By following users and tags, you can catch up information on technical fields that you are interested in as a whole
  2. you can read useful information later efficiently
    By "stocking" the articles you like, you can search right away
ユーザーは見つかりませんでした