Pythonの単一リンクリストでノードを見つけて削除するにはどうすればよいですか?

前の記事では[Pythonで単一リンクリストにノードを挿入して出力する方法は？ ] では、単一リンク リストとは何か、ノードを追加してすべてのノードを出力する方法を紹介します。以下の記事でノードの検索方法と削除方法を紹介しますので、ご参考になれば幸いです。

単一リンクリストからノードを見つけるにはどうすればよいでしょうか?

ほとんどのデータ構造と同様、要素が存在するかどうかを確認する唯一の方法は、リンク リスト全体を走査することです。リンクされたリストがソートされている場合は、二分検索を使用できることに注意してください。ただし、ここではソートされていないリンク リストについて考えます。

動作原理: ユーザーは、見つける必要があるノード要素を指定します。要素が見つかった場合は true を返し、そうでない場合は false を返します。カウンターを使用して要素のインデックスを返すこともできます (存在する場合)。

アルゴリズム

1. ポインタ curr を先頭に設定します

2. curr.data を入力値と比較します:

● 等しい場合は True を返します

● それ以外の場合は次のポインタに進みます

3. 要素が見つかるかリンク リストの最後に達するまで手順 1 ～ 2 を繰り返します

実装コード:

def findNode(self,value):
       curr = self.head
       while curr:
           if curr.getData() == value:
               return True
           curr = curr.getNextNode()
       return False

単一リンクリストからノードを削除するには?

上記の例から、ノードを見つける方法がわかり、それを使用してノードを削除できます。ユーザーから値を取得し、リンクされたリスト内の要素を見つけて、存在する場合は削除できます。

注: 要素が正常に削除されたかどうかをユーザーに知らせることは非常に重要です。したがって、削除が成功すると True を返し、それ以外の場合は False を返します。サイズ属性を 1 ずつ減らすことを忘れないでください。

削除するノードを現在のノードと呼びます。アイデアは、前のノードの次のノードを現在のノードの次のノードにリンクすることです。たとえば、指定されたリンク リストから 4 を削除するとします。

原链表： H-->3-->4-->5 
删除4后：H-->3-->5

3 の次のノードが 4 の次のノードである 5 を指す必要があります。

3

删除3后：H-->5

も削除するとします。注: 前のノードと現在のノードの隣のノードとの間の接続を確立するには、必ず前のノードを追跡してください。

アルゴリズム

1. 2 つのポインターがあります:

● CURR - 最初はヘッダーに割り当てられます

● prev - 最初に割り当てられます。 None

2 を指しています。入力した値が curr のデータと一致する場合、prev の存在を確認します:

● 存在する場合、prev の次のノードを curr# の次のノードに設定します。

# だけ減らします。 ## ● True を返します

3. 入力値が curr のデータと一致しない場合は、次の方法で次のノードに移動します:

● 前のカーブをポイントします

# CURR を次のノード CURR

4 にポイントします。リンク リストの終わりまで手順 1 ～ 3 を繰り返します。

5。リンク リストの終わりに到達した場合は、Falseが返され、入力値が

def removeNode(self,value):
        prev = None
        curr = self.head
        while curr:
            if curr.getData() == value:
                if prev:
                    prev.setNextNode(curr.getNextNode())
                else:
                    self.head = curr.getNextNode()
                return True
                    
            prev = curr
            curr = curr.getNextNode()
            
        return False