Python(連結リスト)

Pythonは標準でlistが使えるので、わざわざC++言語のstd::listのようなものを作成して使う場面は少ないらしいが、自作でコンテナクラスを作成して活用できるようにしました。

class LinkedList:
    def __init__(self, x, tail):
        self.__head = x
        if isinstance(tail,LinkedList) or tail is None:
            self.__tail = tail
        else:
            raise ValueError(f'{tail}は連結できません')

    @property
    def head(self): ## 頭部を返す
        return self.__head

    @property
    def tail(self): ##　尾部を返す
        return self.__tail

    @head.setter
    def head(self,value):
        self.__head = value

    @tail.setter
    def tail(self,value):
        if isinstance(value,LinkedList) or value is None:
            self.__tail = value
        else:
            raise ValueError(f'{value}は連結できません')

    def __iter__(self): ## 再帰構造を辿るイテレータ(ジェネレータ)を生成
        def generator():
            obj = self
            while obj:
                yield obj.__head
                obj = obj.__tail
        return generator()

    def __next__(self):
        if self.__tail is None:
            raise StopIteration
        result = self.__head
        tmp = self.__tail
        self.__head = tmp.head
        self.__tail = tmp.tail
        return result

    def __repr__(self): ## データ表現の文字列を生成
        return f'LinkedList({repr(self.__head)},{repr(self.__tail)})'

    def __str__(self): ## 表示用の文字列を生成
        return '(' + ' -> '.join(map(str,self)) + ')'

class Stack:
    def __init__(self):
        self._stack = []

    def push(self,x):
        self._stack.append(x)

    def pop(self):
        try:
            tmp = self._stack.pop()
            return tmp
        except IndexError:
            print("スタックが空です\n")

    def clear(self):
        self._stack.clear()

    def depth(self):
        return len(self._stack)

def make_LinkedList(*xs):
    n=len(xs)
    if n == 0:
        raise ValueError("引数に1つ以上の要素を入れてください")
    tmp_s = Stack()
    for s in xs:
        tmp_s.push(s)    
    tmp_l = Stack()
    while tmp_s.depth() > 0:
        if tmp_l.depth() == 1:
            tmp_l.push(LinkedList(tmp_s.pop(),tmp_l.pop()))
        else:
            tmp_l.push(LinkedList(tmp_s.pop(),None))
    return tmp_l.pop()

Pythonでは、C++のようにオーバーロードができないので、コンストラクタでは、自身のクラスに格納するデータ（head）と連結リスト（tail）を引数としてインスタンスを生成するようにし、make_LinkedList(*xs)メソッドで可変引数から連結リストを作成できるようにしました。

@property

ゲッターを定義する場合のデコレータで、この後に関数定義を行うことで値を取得できるようにしています。

＠ゲッター名.setter

セッターを定義する場合のデコレータで、この後に関数定義を行うことで値を設定できるようにしています。

def __iter__(self)

Iterableとして振舞うことができるようにする特殊メソッドで、内部でジェネレータを返すようにすることでforループで値を取得したり、可変引数として値を取得したりできるようにしています。

def __next__(self)

Iteratorとして振舞うことができるようにする特殊メソッドで、next()メソッドで自身を次の要素にシフトすることができます。

IterableとIterator

IterableとIteratorは違うもので、集合的に見ると、IteratorはIterableを内包するもので、next()メソッドで値を取得できます。
Iterableはiter()メソッドによってIteratorに変換することができます。range(10),[1,2,3]はIterableですが、そのままではnext()メソッドを利用できないのでIteratorではありません。

hasattr([1,2,3],"__iter__")

自身の属性を確認するメソッドで真偽値（TrueかFalse）を返すメソッドです。__iter__と__next__をチェックすることでIterableかIteratorかを確認することができます。

make_LinkedList(*xs)

スタック構造に要素を積み、末尾から連結リストのインスタンスを作成してつなげることで、可変引数から連結リストを作成できるようにしました。

Stackを利用しないmake_LinkedList(*xs)

スタックのインスタンスを生成して末尾から連結リストを作成しなくても、頭から更新していく方法がこちら

def make_LinkedList(*xs):
    n=len(xs)
    if n == 0:
        raise ValueError("引数に1つ以上の要素を入れてください")
    pre,result = None,None
    for s in xs:
        tmp = LinkedList(s,None)
        if pre:            
            pre.tail = tmp            
        else:
            result = tmp
        pre = tmp
    return result

resultの更新が最初だけなのにちゃんと連結したものが返ってきますが、最初はなぜ可能なのかが理解できませんでした（汗）
PythonではC言語のようにポインタがないので、この挙動が理解できなかったのですが、クラスのインスタンスを最初にresultとpreの両方に入れたことでアドレスが共有され、末尾のtailのアドレスも同様に同じアドレスを参照していたため、resultを最初に生成するだけで末尾がどんどん更新されていくようになっています。
ただ、pythonではC言語のように静的にアドレスを確保しているのではなく、処理のたびに違うアドレスを利用しているみたいです。

以下、検証用のコードと結果

def make_LinkedList(*xs):
    n=len(xs)
    if n == 0:
        raise ValueError("引数に1つ以上の要素を入れてください")
    pre,result = None,None
    for s in xs:
        tmp = LinkedList(s,None)
        if pre:            
            pre.tail = tmp            
        else:
            result = tmp
        pre = tmp
        print("result:",id(result))
        print("result.tail:",id(result.tail))
        print("pre:",id(pre))
        print("pre.tail:",id(pre.tail))
    return result

pythonでの参照アドレスについて詳しくはこちら
https://snowtree-injune.com/2018/08/31/variable2/

こちらの元ネタはこちら
連結リスト (再帰的データ構造)

＜2019/11/20追記＞

畳み込みでのmake(xs)

functoolsモジュールをインポートし、reduceメソッドで左畳み込み処理を行うことができます。この方法でiterableから連結リストを作成する関数make(xs)を作成しました。

import functools as ft

def set_tail(self,value):
        if isinstance(value,LinkedList) or value is None:
            self.__tail = value
        else:
            raise ValueError(f'{value}は連結できません')

def make(iterable):
    return ft.reduce(lambda a,b:(b.set_tail(a),b)[1],
                     reversed([*(LinkedList(x,None) for x in iterable)]))

※makeメソッドはmake_LinkedList(*xs)メソッドと同様の機能をもったものです。
※ラムダ式に処理を渡すために、セッターとしてset_tail(self,value)メソッドを定義しています。

ラムダ式での処理は隣接する要素のtailに前の要素をセットし、更新された要素を返すようにしています。
逆順にしたリストを後ろから連結することで目的とする連結リストが得られます。

ラムダ式部分が分かりにくいので、内部関数を定義して同様の処理を行ったものが以下になります。

def make(iterable):
    def set(a,b):
        b.set_tail(a)
        return b
    return ft.reduce(set,reversed([*(LinkedList(x,None) for x in iterable)]))

畳み込み関数

リストの隣同士の要素に対して演算を行い、結果として一つの値を得るようなもの。

functools.reduce( func, iterable [, 初期値] )

初期値が省略された場合, リストの最初の要素が取り出され, 初期値となる。初期値が省略され、さらにリストが空だったときは、TypeErrorが投げられる。
初期値があるがリストが空、あるいは初期値が省略されてリストの要素がただ一つのときは、その値がreduce()の計算結果となる。

畳み込み関数のような高階関数について詳しくはこちら
Python3で高階関数 (map/filter/product, 畳み込み関数)

＜2019/11/21追記＞

多項式計算時間を要するmake(xs)

アルゴリズムの計算時間と入力サイズとの関係について、もっとも広く使われている漸近記法でビッグオー記法があります。

詳しくはこちらをチェック
[初心者向け] プログラムの計算量を求める方法

def make_LinkedList(*xs):
    n=len(xs)
    if n == 0:
        raise ValueError("引数に1つ以上の要素を入れてください")
    pre,result = None,None
    for s in xs:
        tmp = LinkedList(s,None)
        if pre:            
            pre.tail = tmp            
        else:
            result = tmp
        pre = tmp
    return result

このプログラムでは引数の要素数に応じて計算時間が必要なので、O(n)で表す線形計算時間に属します。
リストや列を扱うアルゴリズムの計算煩雑性はたいていO(n)です。

では、以下のプログラムの場合は？

def make(iterable):
    def fetch_tail(obj):
        """末尾の項を探索しセットする関数"""
        while True:
            if obj.tail is None:
                return obj
            obj = obj.tail
    result = None
    for x in iterable:
        tmp = LinkedList(x,None)
        if result is None:
            result = tmp
        else:
            fetch_tail(result).tail = tmp
    return result

内部関数では登録したresultの最後尾の要素を探索して返し、それに引数の要素をセットするという手法なので、O(n^2)で表す多項式計算時間に属します。

同じ結果でも、アルゴリズムによって計算量が異なるので、できるだけ計算量の少ない手法でプログラミングを行う癖を付けたいですね。

＜2019/11/18追記＞

def __repr__(self): ## データ表現の文字列を生成
        return f'LinkedList({repr(self.__head)},{repr(self.__tail)})'

の部分ですが、この形ではrepr(self.__tail)が再帰処理で自身を読み込んでいるため、要素が多いとメモリが足りなくなります。

そこで、再帰を使わない形で処理するように変更したパターンを3つ紹介します。

その1：頭からループ処理で文字列を結合する

def __repr__(self): ## データ表現の文字列を生成      
        tmp="LinkedList("
        result=""
        count=0
        for i in map(str,self):
            result += tmp+i+","
            count+=1
        return result + "None"+")"*count

その2：頭から内包表記で文字列を結合する

def __repr__(self): ## データ表現の文字列を生成      
        tmp="LinkedList("
        ele = [x for x in map(str,self)]
        result = tmp + "{0}None".format(tmp.join(x+"," for x in ele))
        return result + ")" * len(ele)

どちらも後ろの　）を付ける為に不恰好なプログラムに･･･

その3：末尾からループ処理で更新した要素を表示する

def __repr__(self): ## データ表現の文字列を生成
        result=None
        for x in reversed([*self]):
            result=f"LinkedList({repr(x)},{result})"
        return result

ポイントはresultにNoneを入れておき、自身を可変リストに変換した上でreversedメソッドで反転させ、resultを更新しつつ再代入を繰り返すことで末尾から文字列を構築していることです。

上記3つの方法はどれもメモリ不足でエラーが表示される問題を解決することができます。

Pythonではfunctoolsモジュールのreduceメソッドで左たたみ込み処理を行うことができます。
今回は末尾からの処理なので、そのまま利用はできませんが、右たたみ込み処理を利用する関数を定義すると問題を解決する手法に使うことができます。