この記事では、リンクされたリストの実装について学びます。 パイソン 。 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> |
>
Javaのプライムノーコード
>
リンクされたリストから最後のノードを削除
このメソッドでは、最後のノードを削除します。まず、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>