この記事では、リンクされたリストの実装について学びます。 パイソン 。 Python でリンク リストを実装するには、次を使用します。 Python のクラス 。これで、リンク リストがノードで構成され、ノードには 2 つの要素 (データと別のノードへの参照) があることがわかりました。まずノードを実装しましょう。

Pythonのリンクリストとは何ですか

リンクされたリスト 配列に似た線形データ構造の一種です。相互にリンクされたノードの集合です。ノードには 2 つのものが含まれています。1 つはデータ、もう 1 つはノードを別のノードに接続するリンクです。以下は 4 つのノードを含むリンク リストの例です。各ノードには文字データと別のノードへのリンクが含まれています。最初のノードは次の場所です 頭 ポイントを使用すると、リンク リストのすべての要素にアクセスできます。 頭。

リンクされたリスト

Pythonでリンクリストを作成する

この LinkedList クラスでは、Node クラスを使用してリンク リストを作成します。このクラスでは、 __熱い__ リンクされたリストを空のヘッドで初期化するメソッド。次に、 insertAtBegin() リンクされたリストの先頭にノードを挿入するメソッド、 insertAtIndex() リンクされたリストの指定されたインデックスにノードを挿入するメソッド、および insertAtEnd() メソッドは、リンクされたリストの最後にノードを挿入します。その後、 削除_ノード() データを引数として受け取るメソッドを使用して、そのノードを削除します。の中に 削除_ノード() このメソッドでは、リンク リストを走査し、データと等しいノードが存在する場合、そのノードをリンク リストから削除します。それから、 サイズOfLL() リンク リストの現在のサイズを取得するメソッドと、LinkedList クラスの最後のメソッドは次のとおりです。 printLL() これはリンクされたリストを走査し、各ノードのデータを出力します。

ノードクラスの作成

を定義した Node クラスを作成しました。 __熱い__ この関数は、引数として渡されたデータと None で参照を使用してノードを初期化します。これは、ノードが 1 つしかない場合、その参照には何もないためです。

Python3

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

リンクされたリストへの挿入

リンクされたリストの先頭に挿入

このメソッドは、リンクされたリストの先頭にノードを挿入します。このメソッドでは、 新しいノード 与えられたものと一緒に データ ヘッドが空のノードかどうかを確認し、ヘッドが空の場合は、 新しいノード として 頭 そして 戻る それ以外の場合は次の部分にヘッドを挿入します 新しいノード そして、 頭 に等しい 新しいノード。

Python3

def> insertAtBegin(> self> , data):> > new_node> => Node(data)> > if> self> .head> is> None> :> > self> .head> => new_node> > return> > else> :> > new_node.> next> => self> .head> > self> .head> => new_node>

リンクされたリストの特定の位置にノードを挿入する

このメソッドは、リンクされたリストの指定されたインデックスにノードを挿入します。このメソッドでは、 新しいノード 指定された data 、head に等しい current_node 、および counter を持つ '位置' で初期化します 0. ここで、インデックスがゼロに等しい場合は、ノードが開始時に挿入されることを意味するため、次のように呼び出しました。 insertAtBegin() メソッド それ以外の場合は、while ループを実行します。 現在のノード に等しくありません なし または (位置+1) は、ノードのリンクを作成するために指定された位置に挿入するために 1 つ前の位置に戻る必要があるインデックスと等しくありません。各反復で、位置を 1 ずつインクリメントして、 現在のノード その次。ループが切れたときと、 現在のノード に等しくありません なし new_node を の後に挿入します。 現在のノード。 もし 現在のノード に等しい なし これはインデックスがリストに存在しないことを意味し、出力します。 インデックスが存在しません。

Python3

# Indexing starts from 0.> def> insertAtIndex(> self> , data, index):> > new_node> => Node(data)> > current_node> => self> .head> > position> => 0> > if> position> => => index:> > self> .insertAtBegin(data)> > else> :> > while> (current_node !> => None> and> position> +> 1> !> => index):> > position> => position> +> 1> > current_node> => current_node.> next> > if> current_node !> => None> :> > new_node.> next> => current_node.> next> > current_node.> next> => new_node> > else> :> > print> (> 'Index not present'> )>

リンクされたリストの末尾への挿入

このメソッドは、リンクされたリストの最後にノードを挿入します。このメソッドでは、 新しいノード 指定されたデータを使用して、 頭 が空のノードであるかどうか 頭 が空の場合は、 新しいノード として 頭 そして 戻る それ以外 私たちは、 current_node が等しい に 頭 最後まで横断する ノード リンクされたリストの内容と取得したとき なし current_node の後に while ループが中断され、 新しいノード の次の 現在のノード これはリンクされたリストの最後のノードです。

Python3

def> inserAtEnd(> self> , data):> > new_node> => Node(data)> > if> self> .head> is> None> :> > self> .head> => new_node> > return> > current_node> => self> .head> > while> (current_node.> next> ):> > current_node> => current_node.> next> > current_node.> next> => new_node>

リンクされたリストのノードを更新する

このコードは、リンク リスト クラスで updateNode というメソッドを定義します。これは、リンクされたリスト内の特定の位置にあるノードの値を更新するために使用されます。

Python3

# Update node of a linked list> # at given position> def> updateNode(> self> , val, index):> > current_node> => self> .head> > position> => 0> > if> position> => => index:> > current_node.data> => val> > else> :> > while> (current_node !> => None> and> position !> => index):> > position> => position> +> 1> > current_node> => current_node.> next> > if> current_node !> => None> :> > current_node.data> => val> > else> :> > print> (> 'Index not present'> )>

リンクされたリスト内のノードの削除

リンクされたリストから最初のノードを削除

このメソッドは、2 番目のノードを作成するだけで、リンク リストの最初のノードを削除します。 頭 リンクされたリストの。

Python3

def> remove_first_node(> self> ):> > if> (> self> .head> => => None> ):> > return> > > self> .head> => self> .head.> next>

リンクされたリストから最後のノードを削除

このメソッドでは、最後のノードを削除します。まず、while ループを使用して最後から 2 番目のノードまで移動し、そのノードの次のノードを作成します。 なし そして最後のノードが削除されます。

Python3

def> remove_last_node(> self> ):> > if> self> .head> is> None> :> > return> > current_node> => self> .head> > while> (current_node.> next> .> next> ):> > current_node> => current_node.> next> > current_node.> next> => None>

指定された位置にあるリンク リスト ノードを削除します

このメソッドでは、指定されたインデックスにあるノードを削除します。このメソッドは次のようなものです。 の insert_at_inded() 方法。この方法では、 頭 は なし 私たちは単に 戻る それ以外の場合は初期化します 現在のノード と セルフヘッド そして 位置 と 0. 位置がインデックスと等しい場合、 Remove_first_node() それ以外の場合は、while ループを使用して、削除する 1 つ前のノードまで移動します。その後、while ループから抜け出すときにチェックします。 その current_node に等しい なし そうでない場合は、 current_node の次を削除するノードの次と等しくします。そうでない場合は、メッセージを出力します。 インデックスが存在しません なぜなら 現在のノード に等しい なし。

Python3

# Method to remove at given index> def> remove_at_index(> self> , index):> > if> self> .head> => => None> :> > return> > current_node> => self> .head> > position> => 0> > if> position> => => index:> > self> .remove_first_node()> > else> :> > while> (current_node !> => None> and> position> +> 1> !> => index):> > position> => position> +> 1> > current_node> => current_node.> next> > if> current_node !> => None> :> > current_node.> next> => current_node.> next> .> next> > else> :> > print> (> 'Index not present'> )>

指定されたデータのリンク リスト ノードを削除します

このメソッドは、指定されたデータを持つノードをリンク リストから削除します。この方法では、まず、 現在のノード に等しい 頭 そして実行します while ループ リンクされたリストを横断します。この while ループは次の場合に中断します。 現在のノード になる なし または、現在のノードの隣のデータが引数で指定されたデータと同じです。さて、ループから抜け出した後、 現在のノード に等しい なし これは、ノードがデータ内に存在しないことを意味し、単に戻るだけです。 現在のノード が指定されたデータと等しい場合、そのremoved_nodeの次をcurrent_nodeの次にすることによってそのノードを削除します。これは、if else 条件を使用して実装されます。

Python3

def> remove_node(> self> , data):> > current_node> => self> .head> > # Check if the head node contains the specified data> > if> current_node.data> => => data:> > self> .remove_first_node()> > return> > while> current_node> is> not> None> and> current_node.> next> .data !> => data:> > current_node> => current_node.> next> > if> current_node> is> None> :> > return> > else> :> > current_node.> next> => current_node.> next> .> next>

Python でのリンク リストのトラバーサル

このメソッドは、リンクされたリストを走査し、各ノードのデータを出力します。この方法では、 現在のノード に等しい 頭 を使用してリンクされたリストを反復処理します。 while ループ まで 現在のノード None になり、のデータを出力します 現在のノード 各反復で、 現在のノード その次。

Python3

def> printLL(> self> ):> > current_node> => self> .head> > while> (current_node):> > print> (current_node.data)> > current_node> => current_node.> next>

Python でリンクされたリストの長さを取得する

このメソッドは、リンクされたリストのサイズを返します。このメソッドでは、カウンターを初期化しました。 'サイズ' 0 を指定し、head が None に等しくない場合は、 while ループ そして増加します サイズ 各反復で 1 を使用し、次の場合にサイズを返します。 現在のノード になる 他には何もない 0を返します。

Python3

def> sizeOfLL(> self> ):> > size> => 0> > if> (> self> .head):> > current_node> => self> .head> > while> (current_node):> > size> => size> +> 1> > current_node> => current_node.> next> > return> size> > else> :> > return> 0>

Python のリンクリストの例

この例では、Node および LinkedList クラスを定義した後、という名前のリンク リストを作成しました。 リストする リンク リスト クラスを使用し、文字データを含む 4 つのノードを挿入します。 'あいうえお' そして 「ぐ」 リンクされたリストでは、次を使用してリンクされたリストを印刷します printLL() メソッドリンクリストクラス その後、削除メソッドを使用していくつかのノードを削除しました その後、リンクされたリストを再度印刷すると、ノードが正常に削除されたことが出力で確認できます。その後、リンクされたリストのサイズも出力します。

Python3

# Create a Node class to create a node> class> Node:> > def> __init__(> self> , data):> > self> .data> => data> > self> .> next> => None> # Create a LinkedList class> class> LinkedList:> > def> __init__(> self> ):> > self> .head> => None> > # Method to add a node at begin of LL> > def> insertAtBegin(> self> , data):> > new_node> => Node(data)> > if> self> .head> is> None> :> > self> .head> => new_node> > return> > else> :> > new_node.> next> => self> .head> > self> .head> => new_node> > # Method to add a node at any index> > # Indexing starts from 0.> > def> insertAtIndex(> self> , data, index):> > new_node> => Node(data)> > current_node> => self> .head> > position> => 0> > if> position> => => index:> > self> .insertAtBegin(data)> > else> :> > while> (current_node !> => None> and> position> +> 1> !> => index):> > position> => position> +> 1> > current_node> => current_node.> next> > if> current_node !> => None> :> > new_node.> next> => current_node.> next> > current_node.> next> => new_node> > else> :> > print> (> 'Index not present'> )> > # Method to add a node at the end of LL> > def> insertAtEnd(> self> , data):> > new_node> => Node(data)> > if> self> .head> is> None> :> > self> .head> => new_node> > return> > current_node> => self> .head> > while> (current_node.> next> ):> > current_node> => current_node.> next> > current_node.> next> => new_node> > # Update node of a linked list> > # at given position> > def> updateNode(> self> , val, index):> > current_node> => self> .head> > position> => 0> > if> position> => => index:> > current_node.data> => val> > else> :> > while> (current_node !> => None> and> position !> => index):> > position> => position> +> 1> > current_node> => current_node.> next> > if> current_node !> => None> :> > current_node.data> => val> > else> :> > print> (> 'Index not present'> )> > # Method to remove first node of linked list> > def> remove_first_node(> self> ):> > if> (> self> .head> => => None> ):> > return> > self> .head> => self> .head.> next> > # Method to remove last node of linked list> > def> remove_last_node(> self> ):> > if> self> .head> is> None> :> > return> > current_node> => self> .head> > while> (current_node.> next> .> next> ):> > current_node> => current_node.> next> > current_node.> next> => None> > # Method to remove at given index> > def> remove_at_index(> self> , index):> > if> self> .head> => => None> :> > return> > current_node> => self> .head> > position> => 0> > if> position> => => index:> > self> .remove_first_node()> > else> :> > while> (current_node !> => None> and> position> +> 1> !> => index):> > position> => position> +> 1> > current_node> => current_node.> next> > if> current_node !> => None> :> > current_node.> next> => current_node.> next> .> next> > else> :> > print> (> 'Index not present'> )> > # Method to remove a node from linked list> > def> remove_node(> self> , data):> > current_node> => self> .head> > if> current_node.data> => => data:> > self> .remove_first_node()> > return> > while> (current_node !> => None> and> current_node.> next> .data !> => data):> > current_node> => current_node.> next> > if> current_node> => => None> :> > return> > else> :> > current_node.> next> => current_node.> next> .> next> > # Print the size of linked list> > def> sizeOfLL(> self> ):> > size> => 0> > if> (> self> .head):> > current_node> => self> .head> > while> (current_node):> > size> => size> +> 1> > current_node> => current_node.> next> > return> size> > else> :> > return> 0> > # print method for the linked list> > def> printLL(> self> ):> > current_node> => self> .head> > while> (current_node):> > print> (current_node.data)> > current_node> => current_node.> next> # create a new linked list> llist> => LinkedList()> # add nodes to the linked list> llist.insertAtEnd(> 'a'> )> llist.insertAtEnd(> 'b'> )> llist.insertAtBegin(> 'c'> )> llist.insertAtEnd(> 'd'> )> llist.insertAtIndex(> 'g'> ,> 2> )> # print the linked list> print> (> 'Node Data'> )> llist.printLL()> # remove a nodes from the linked list> print> (> ' Remove First Node'> )> llist.remove_first_node()> print> (> 'Remove Last Node'> )> llist.remove_last_node()> print> (> 'Remove Node at Index 1'> )> llist.remove_at_index(> 1> )> # print the linked list again> print> (> ' Linked list after removing a node:'> )> llist.printLL()> print> (> ' Update node Value'> )> llist.updateNode(> 'z'> ,> 0> )> llist.printLL()> print> (> ' Size of linked list :'> , end> => ' '> )> print> (llist.sizeOfLL())>

出力

Node Data c a g b d Remove First Node Remove Last Node Remove Node at Index 1 Linked list after removing a node: a b Update node Value z b Size of linked list : 2