単方向連結リストの実装

あー疲れたー。
プログラミング・アルゴリズムの勉強がてら、連結リストを試しに実装してみたが、色々引っかかって数時間があっという間に飛んでいってしまった。
だがまあ、こうやって苦労してこそ理解も深まるというもの。決して無駄ではなかったと思いたい。

言語選択の理由は特にないが、やっぱりスクリプト言語は余計な記述をしなくて済むので書くのも読むのも楽
- とはいっても、型の情報くらいは書きたい気もする。動的型付け言語だと突然宣言されていない型も不明な怪しげな変数が出てくるので、読んでたり書いてたりするときにこれなんだよってなることはある気がする
色々いわれる例のself, やっぱり（書くのが）面倒くさい。インスタンス変数を弄るときにselfを書くのはともかく、メソッドの第一引数にいちいちselfを書くのは気味が悪い。
- 書き忘れでエラーが出るとムキーとなる
- 書くのは面倒だがその分読みやすいのは確か
インスタンスを生成するときにnew演算子なりnewメソッドを使わないのが気持ち悪い。明示をよしとする言語でnew演算子がないのには、何か深い理由がありそうだが？
range関数も正直わかりにくいし好きじゃないなぁ
最初addやdelete_lastメソッドは個別に実装していたが、insertやdeleteで流用できることに気づく。if A return B で Aが満たされないならNoneが返るのでこれでよいのだ。

こうして苦労しながらコードを書いてみると、連結リストがシーケンシャルアクセスであるということが身にしみて理解できる。
Pythonのイテレータへの理解がまだあやふや。for文で呼び出したら、まず__iter__()を実行して、次にraise StopIteration()されるまで__next__()が実行されて順番に値が取り出される、ってことかな？

class MyList:
    def __init__(self, value = "Dummy"):
        self.value = value
        self.pointer = None
        self.size = 0 # list[0]="Dummy", list[1]~list[self.size]

    def getindex_cellobject(self, index): # index番目のセルオブジェクトを返す
        if index <= self.size:
            tmp = self
            for i in range(index):
                tmp = tmp.pointer
            return tmp

    def __getitem__(self, index): # index番目のセルオブジェクトに含まれる値をself[index]でアクセスできるようにする
        if index <= self.size:
            return self.getindex_cellobject(index).value

    def add(self, value): # リスト最後尾に追加
        return self.insert(self.size + 1, value)

    def delete_last(self): # 最後尾を削除
        return self.delete(self.size)

    def insert(self, index, value): # index番目に挿入
        if 1 <= index <= self.size + 1:
            leftcell  = self.getindex_cellobject(index - 1)
            rightcell = leftcell.pointer

            newcell = MyList(value)
            leftcell.pointer = newcell
            newcell.pointer = rightcell

            self.size += 1
        return self

    def delete(self, index): # index番目を削除
        if 1 <= index <= self.size:
            leftcell  = self.getindex_cellobject(index - 1)
            rightcell = leftcell.pointer.pointer
            leftcell.pointer = rightcell

            self.size -= 1
        return self

    def show(self, a, b): # list[a] ~ list[b]
        if 0 <= a <= b <= self.size:
            for i in range(a, b + 1):
                print(self[i])

    def showall(self):
        self.show(0, self.size)

    def addlist(self, anotherlist): # リストの結合
        if anotherlist.size > 0:
            lastcell = self.getindex_cellobject(self.size)
            lastcell.pointer = anotherlist.pointer
            self.size += anotherlist.size

    def __iter__(self):
        self.tmp = self
        return self

    def __next__(self):
        if self.tmp == None:
            raise StopIteration()
        result = self.tmp.value
        self.tmp = self.tmp.pointer
        return result


testList = MyList().add("aaa").add("bbb").add("ccc").insert(2, "2").delete_last().delete(1).add("LAST")
another = MyList().add(1).add(10).add(100)
testList.addlist(another)

for value in testList:
    print(value)

# 出力
# Dummy
# 2
# bbb
# LAST
# 1
# 10
# 100

@ゲー単走部

ローグライク雑記。変愚蛮怒、DCSSなど。

単方向連結リストの実装