[データ構造] Pythonでの連結リスト

連結リストを Python で実装します。

ノードのクラス

連結リストのそれぞれのノードは、自身のデータと、次のノードを指すリンクを持ちます。

class Node(object):

    def __init__(self, data):
        self.data = data
        self.next_node = None

連結リストのクラス

連結リストは、先頭のノードと要素数を初期値として持ちます。先頭のノードはNone 、要素数は0として初期化します。

class Node(object):

    def __init__(self, data):
        self.data = data
        self.next_node = None

# 追加
class LinkedList(object):
    
    def __init__(self):
        self.head = None
        self.length = 0

先頭へのノードの挿入

特殊メソッド__len__を使い、先頭へノードの挿入を行うメソッドを定義します。

先頭ノードが存在しない場合は挿入するノードを先頭ノードにします。既に存在する場合はポインタの付け替えを行います。

class Node(object):

    def __init__(self, data):
        self.data = data
        self.next_node = None


class LinkedList(object):
    
    def __init__(self):
        self.head = None
        self.length = 0
    
    # 追加
    # O(1)
    def insert_first(self, data):

        new_node = Node(data)
        self.length += 1

        if not self.head:
            self.head = new_node
        else:
            new_node.next_node = self.head
            self.head = new_node

要素の出力

__str__メソッドを使い、print()で要素を出力できるようにします。

Pythonの特殊メソッド一覧を備忘録としてまとめてみた。

 class Node(object):

    def __init__(self, data):
        self.data = data
        self.next_node = None


class LinkedList(object):
    
    def __init__(self):
        self.head = None
        self.length = 0
    
    # O(1)
    def insert_first(self, data):

        new_node = Node(data)
        self.length += 1

        if not self.head:
            self.head = new_node
        else:
            new_node.next_node = self.head
            self.head = new_node
    # 追加
    # O(N)
    def __str__(self):
        elems = ''
        current_node = self.head
        while current_node:
            if current_node.next_node is None:
                elems += str(current_node.data)
            else:
                elems += str(current_node.data) + ', '
            current_node = current_node.next_node
        return '[' + elems +']'


if __name__ == '__main__':
    linked_list = LinkedList()
    # []
    print(linked_list)
    linked_list.insert_first(1)
    # [1]
    print(linked_list)
    linked_list.insert_first(2)
    # [2, 1]
    print(linked_list)
    linked_list.insert_first(3)
    # [3, 2, 1]
    print(linked_list)

要素数の取得

__len__ メソッドを使い、連結リストの要素数を取得するlen()で取得できるようにします。

class Node(object):

    def __init__(self, data):
        self.data = data
        self.next_node = None


class LinkedList(object):
    
    def __init__(self):
        self.head = None
        self.length = 0
    
    # O(1)
    def insert_first(self, data):

        new_node = Node(data)
        self.length += 1

        if not self.head:
            self.head = new_node
        else:
            new_node.next_node = self.head
            self.head = new_node

    # O(N)
    def __str__(self):
        elems = ''
        current_node = self.head
        while current_node:
            if current_node.next_node is None:
                elems += str(current_node.data)
            else:
                elems += str(current_node.data) + ', '
            current_node = current_node.next_node
        return '[' + elems +']'

    # 追加
    # O(1)
    def __len__(self):
        return self.length


if __name__ == '__main__':
    linked_list = LinkedList()
    # 0
    print(len(linked_list))
    linked_list.insert_first(1)
    # 1
    print(len(linked_list))
    linked_list.insert_first(2)
    # 2
    print(len(linked_list))
    linked_list.insert_first(3)
    # 3
    print(len(linked_list))

ここで、もしself.length を使わずに要素数を取得する方法を考えると、以下のように書けます。

この場合、同じ結果にはなりますが、要素数を取得するたびに、\( O (N) \) の計算量になります。

class Node(object):

    def __init__(self, data):
        self.data = data
        self.next_node = None


class LinkedList(object):
    
    def __init__(self):
        self.head = None
        # self.length = 0
    
    # O(1)
    def insert_first(self, data):

        new_node = Node(data)
        # self.length += 1

        if not self.head:
            self.head = new_node
        else:
            new_node.next_node = self.head
            self.head = new_node

    # O(N)
    def __str__(self):
        elems = ''
        current_node = self.head
        while current_node:
            if current_node.next_node is None:
                elems += str(current_node.data)
            else:
                elems += str(current_node.data) + ', '
            current_node = current_node.next_node
        return '[' + elems +']'

    # # O(1)
    # def __len__(self):
    #     return self.length

    # 追加
    # O(N)
    def __len__(self):
        node = self.head
        size = 0
        while node is not None:
            size += 1
            node = node.next_node
        return size


if __name__ == '__main__':
    linked_list = LinkedList()
    # 0
    print(len(linked_list))
    linked_list.insert_first(1)
    # 1
    print(len(linked_list))
    linked_list.insert_first(2)
    # 2
    print(len(linked_list))
    linked_list.insert_first(3)
    # 3
    print(len(linked_list))

最後へノードを挿入

連結リストの一番最後にノードを挿入します。

リスト内にノードが存在しない場合は、先頭へノードを挿入する場合に該当するので、そちらのメソッドを使います。

それ以外の場合は、一番最後のノードまで移動し、ポインタの付け替えを行います。

class Node(object):

    def __init__(self, data):
        self.data = data
        self.next_node = None


class LinkedList(object):
    
    def __init__(self):
        self.head = None
        self.length = 0
    
    # O(1)
    def insert_first(self, data):

        new_node = Node(data)
        self.length += 1

        if not self.head:
            self.head = new_node
        else:
            new_node.next_node = self.head
            self.head = new_node

    # O(N)
    def __str__(self):
        elems = ''
        current_node = self.head
        while current_node:
            if current_node.next_node is None:
                elems += str(current_node.data)
            else:
                elems += str(current_node.data) + ', '
            current_node = current_node.next_node
        return '[' + elems +']'

    # O(1)
    def __len__(self):
        return self.length
    
    # 追加
    # O(N)
    def insert_last(self, data):

        if self.head is None:
            self.insert_first(data)
        else:
            new_node = Node(data)
            self.length += 1
            current_node = self.head

            while current_node.next_node is not None:
                current_node = current_node.next_node
            
            current_node.next_node = new_node
    

if __name__ == '__main__':
    linked_list = LinkedList()
    # []
    print(linked_list)
    linked_list.insert_last(1)
    # [1]
    print(linked_list)
    linked_list.insert_last(2)
    # [1, 2]
    print(linked_list)
    # [1, 2, 3]
    linked_list.insert_last(3)
    print(linked_list)

ノードの削除

ノードの削除を行います。

該当するノードが見つかるまで、先頭からリストをたどっていきます。

該当するノードが見つかったら、ポインタの付け替えを行います。

class Node(object):

    def __init__(self, data):
        self.data = data
        self.next_node = None


class LinkedList(object):
    
    def __init__(self):
        self.head = None
        self.length = 0
    
    # O(1)
    def insert_first(self, data):

        new_node = Node(data)
        self.length += 1

        if not self.head:
            self.head = new_node
        else:
            new_node.next_node = self.head
            self.head = new_node

    # O(N)
    def __str__(self):
        elems = ''
        current_node = self.head
        while current_node:
            if current_node.next_node is None:
                elems += str(current_node.data)
            else:
                elems += str(current_node.data) + ', '
            current_node = current_node.next_node
        return '[' + elems +']'

    # O(1)
    def __len__(self):
        return self.length
    
    # O(N)
    def insert_last(self, data):

        if self.head is None:
            self.insert_first(data)
        else:
            new_node = Node(data)
            self.length += 1
            current_node = self.head

            while current_node.next_node is not None:
                current_node = current_node.next_node
            
            current_node.next_node = new_node

    # 追加
    # O(N)
    def remove(self, data):

        if self.head is None:
            print('リストは空です。')
            return

        current_node = self.head
        previous_node = None

        while current_node.data != data:
            if current_node.next_node is None:
                print('削除に該当するデータがありません。')
                return 
            previous_node = current_node
            current_node = current_node.next_node
        
        # 削除ノードが先頭
        if previous_node is None:
            self.head = current_node.next_node
            self.length -= 1
        else:
            previous_node.next_node = current_node.next_node
            self.length -= 1
    

if __name__ == '__main__':
    linked_list = LinkedList()
    
    # リストは空です。
    linked_list.remove(1)

    linked_list.insert_last(1)
    linked_list.insert_last(2)
    linked_list.insert_last(3)
    
    # [1, 2, 3]
    print(linked_list)
    
    # 削除に該当するデータがありません。
    linked_list.remove(4)

    linked_list.remove(1)
    # [2, 3]
    print(linked_list)

    linked_list.insert_first(1)
    linked_list.remove(3)
    # [1, 2]
    print(linked_list)

    linked_list.insert_last(3)
    linked_list.remove(2)
    # [1, 3]
    print(linked_list)