Pythonで連結リストの末尾からN番目のノードを取得・表示する方法

連結リスト（リンクリスト）の末尾から特定の位置にあるノードを取得して表示したい場合、「list_length」関数と「return_from_end」関数を定義するアプローチが効果的です。

「list_length」関数は、連結リスト全体の長さ（ノード数）を計算して返します。

一方、「return_from_end」関数は、この長さ情報をもとに、連結リストの末尾からn番目の要素を返す役割を担います。

以下に具体的な実装例を示します。

サンプルコード

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 list_length(my_list):
    my_len = 0
    curr = my_list.head
    while curr:
        curr = curr.next
        my_len = my_len + 1
    return my_len

def return_from_end(my_list, n):
    l = list_length(my_list)
    curr = my_list.head
    for i in range(l - n):
        curr = curr.next
    return curr.data

my_instance = LinkedList_structure()

my_list = input('Enter the elements of the linked list..').split()
for elem in my_list:
    my_instance.add_vals(int(elem))

n = int(input('Enter the value for n.. '))
my_result = return_from_end(my_instance, n)

print('The nth element from the end is: {}'.format(my_result))

実行結果

Enter the elements of the linked list..45 31 20 87 4
Enter the value for n.. 2
The nth element from the end is: 87

アルゴリズムのポイント

この手法の考え方はシンプルです。まずリスト全体の長さLを求め、その後、先頭から(L − n)回ポインタを進めることで、末尾からn番目のノードに到達します。例えば、5つの要素を持つリストで末尾から2番目の要素を取得したい場合、先頭から3つ進んだ位置にあるノードが該当します。上記の実行例では、リスト「45 → 31 → 20 → 87 → 4」の末尾から2番目の要素である「87」が出力されています。

コードの解説

• まず、ノードを表す「Node」クラスを作成します。各ノードはデータ（data）と次のノードへの参照（next）を持ちます。

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

• このクラスには「__init__」関数があり、先頭ノードを指す「head」と最終ノードを指す「last_node」を「None」で初期化します。

• 「add_vals」というメソッドを定義し、連結リストの末尾に新しい値を追加できるようにします。リストが空の場合は新規ノードが先頭になり、そうでなければ既存の最終ノードの後に接続されます。

• 「list_length」という関数を定義し、連結リストを先頭から順にたどりながら長さをカウントし、その結果を返します。

• さらに「return_from_end」という関数を定義し、連結リストの末尾からn番目の値を返します。

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

• ユーザーから入力を受け取り、空白区切りで分割した各要素を整数に変換して連結リストへ追加します。

• nの値も入力として受け取ります。

• この連結リストに対して「return_from_end」関数を呼び出し、結果を変数に格納します。

• 最後に、計算結果をコンソールに出力します。