連結リスト内のすべての要素の出現回数を求めるPythonプログラム

連結リスト（リンクリスト）内の各要素が何回出現するかを調べたい場合、要素を連結リストに追加するメソッド、要素を表示するメソッド、そして全要素の出現回数をカウントするメソッドを定義します。

以下にその実装例を示します。

サンプルコード

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList_structure:
    def __init__(self):
        self.head = None
        self.last_node = None

    def add_vals(self, data):
        if self.last_node is None:
            self.head = Node(data)
            self.last_node = self.head
        else:
            self.last_node.next = Node(data)
            self.last_node = self.last_node.next

    def print_it(self):
        curr = self.head
        while curr:
            print(curr.data)
            curr = curr.next

    def count_elem(self, key):
        curr = self.head
        count_val = 0
        while curr:
            if curr.data == key:
                count_val = count_val + 1
            curr = curr.next
        return count_val

my_instance = LinkedList_structure()
my_list = [56, 78, 98, 12, 34, 55, 0]
for elem in my_list:
    my_instance.add_vals(elem)
print('The linked list is : ')
my_instance.print_it()

key_val = int(input('Enter the data item '))
count_val = my_instance.count_elem(key_val)
print('{0} occurs {1} time(s) in the list.'.format(key_val, count_val))

実行結果

The linked list is :
56
78
98
12
34
55
0
Enter the data item 0
0 occurs 1 time(s) in the list.

コードの解説

• まず、連結リストのノードを表す「Node」クラスを作成します。このクラスはデータ本体を格納する data と、次のノードへの参照を持つ next の2つの属性を持ちます。

• 次に、必要な属性を備えた「LinkedList_structure」クラスを作成します。

• このクラスには __init__ 関数があり、連結リストの先頭要素である「head」を「None」で初期化します。あわせて末尾ノードを管理する「last_node」も初期化しています。

• 「add_vals」という名前のメソッドを定義します。このメソッドは、連結リストの末尾に新しい値を追加する役割を担います。リストが空の場合は先頭ノードとして設定し、そうでなければ末尾に接続します。

• 「print_it」という名前の別のメソッドを定義します。このメソッドは、連結リスト内の値を先頭から順番にコンソールへ表示します。

• さらに「count_elem」という名前のメソッドを定義します。このメソッドは、指定されたキーと一致する要素の個数を、リスト全体を走査しながらカウントし、その結果を返します。

• 「LinkedList_structure」クラスのインスタンスを作成します。

• 要素を含むリストを定義します。

• リストを反復処理し、その要素を順番に連結リストへ追加していきます。

• 連結リストの内容をコンソールに表示します。

• ユーザーから入力を受け取り、「count_elem」メソッドを呼び出して該当要素の出現回数を取得します。

• 最後に、カウント結果をコンソールに出力して完了です。

このプログラムの計算量は O(n) です。n は連結リストの要素数であり、リストを一度だけ走査すればよいため効率的な実装となっています。