python

コーディングテストに出てくる単方向リストの実装【Python】

 

pythonで複数のデータを格納するコードを書く際には、組み込まれているlistを使えばいい話ですが、
データ構造の知識を問われる場合に使います。

そもそも単方向リストは連結リストの一種で、各要素は次の要素へ参照ができます。
最後はnullを用いて終端を表します。

実装方法

ノードのクラスを作り、データとアドレス参照を設定します。

class Node: 
    def __init__(self, data): 
        self.data = data  # Assign data 
        self.next = None  # Initialize next as null

次に、単方向リストのクラスを作ります。

ノードのインスタンスを作成し、headがNoneの時には空のheadにnew_nodeを設定します。

headがNone以外の時にはリンクを辿って、最後の一つのnew_nodeを設定する。

最後にtempがNoneでない場合(head or temp.nextがNoneでない場合)にdataを出力します。
temp.nextのみを見るのは、リンクの末尾に指定された値を持つノードを追加するためです。

class LinkedList:

    def __init__(self):  
        self.head = None

    def append(self, new_data): 
       new_node = Node(new_data) 

       if self.head is None: 
            self.head = new_node 
            return　
 
       last = self.head 
       while last.next: 
           last = last.next
 
       last.next =  new_node 


    def printList(self): 
        temp = self.head 
        while temp: 
            print(temp.data) 
            temp = temp.next

ノードを追加した後に、処理を追加したいのであればdataを読み取って処理を行うコードを追加すれば可能です。

RELATED POST