파이썬으로 배우기 데이터 구조 입문 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 구현입니다.
그렇지만, 상당히 비효율적이네요.

예를 들어, 맨 뒤의 데이터를 얻기 위해 처음부터 모든 것을 추적합니다.
데이터에 액세스하기 위해서 전부터 액세스하는 것은, 후반의 데이터에 액세스 할 때에 비효율이 되어 버립니다.
이를 해결하는 것이 양방향 목록입니다.

(다음 번이 있으면) 이것을 양방향 리스트로 개조해 보고 싶습니다.
오늘은 여기까지 합시다. 그게 좋다.