データ構造接続リスト-1(シングルリンクリスト)

10127 ワード

前回の位置決めでは、配列について説明しました.
しかし、覚えていない場合は、次の定理を見てください.
  • Pythonでの配列はリスト型を採用している.
  • リストは、資料型連続の集合である.
  • リストは静的ではなく、可変の資料型である.
  • リストは、ダイナミックメモリ領域によって割り当てられます.
  • 今日整理する連結表は,上述した4つの特徴のうち,特に2つ目の特徴が異なる資料構造である.

    📘 接続リスト


    接続リストには、次のフィーチャーがあります.
  • ノード(データ+ポインタ).
  • アレイと異なり、ストレージは不連続です.
  • ノードのコンポーネントでは、データフィールドにはユーザが必要とする値や情報などが含まれ、ポインタフィールドには次のノードに移動する位置情報が格納される.
  • 🤔では、なぜ接続リストを書くのでしょうか。


    最大の理由は、データの挿入と削除を高速化するためです.
    アレイの場合、上部から挿入/削除しない場合、最悪の場合、時間複雑度O(n)である.
    接続リストでは,削除するノードの位置が分かっていればO(1)の時間的複雑さが必要となるため,挿入と削除が容易である.

    📘 単一リンクリスト


    まず,単一接続リストを整理した.
    単一の接続リストは、データ+次のノードの位置(ポインタ)として整理されます.
    下図をメモリ領域とした場合、描画した形式でデータを格納/位置決めします.

    ここで重要なのは一方向移動です.
    A->B->C->Dは順番に移動できますが、ポインタ(next)が示す方向以外は移動できません.

    💻 Node

    class Node: # 노드의 생성문 
        def __init__(self, data, next = None):
            self.data = data # 데이터 필드
            self.next = next # 포인터 필드
    前述したように、ノードの生成文です.
    ノードを呼び出すと、作成者(init)を使用してオブジェクトを作成できます.
    「データ」フィールドで、必要に応じて値または情報を入力します.nextフィールドは初期値Noneとして指定します.

    💻 Main

    class main:                      # 메인 메서드 동작 및 Head / Tail 생성문
        def __init__(self) -> None:
            self.head = None
            self.tail = None
    プライマリクラスでは、オブジェクト変数headとtailが宣言/初期化されます.

    💻 end_Insert & select_Insert

    def end_insert(self,data):       # 연결 리스트의 맨 끝에 새로운 값을 삽입
            new_node = Node(data)    # 새로운 노드 생성
    
            if self.head is None:    # 값이 비어있다면 실행
                self.head = new_node 
                self.tail = new_node
            else:                    # 값이 있다면 실행
                self.tail.next = new_node
                self.tail = new_node
    新しいノードを作成し、接続リストの最後に新しい値を挿入します.
    値が空の場合、オブジェクト変数(head、tail)に新しいノードを追加することでheadを定義できます.
    逆に、値(head)がある場合はheadのnext変数値を初期に設定します.
    (head.next値がtailを指す)
    次にtailのnext変数値をリセットし、tail変数に新しいノードを割り当てます.
    次の値を受信したときに接続リストを再編成するように設定します.
    def select_insert(self, data, pick_node):
        new_node = Node(data)    # 새로운 노드 생성                
        search = self.head       # 탐색 변수를 생성하여 head노드부터 순차적으로 탐색
    
        while self.head is not None:
            if search.data == pick_node:
                new_node.next = search.next
                search.next = new_node
                break
            else:
                search = search.next
    上のend Insert法と類似しているが,プローブを追加した.
    パラメータは受信(self、data、pick node)に設定されます.
    ここでnodeのデータ値とpick node(直接検索するデータ値)を比較しようとします.
    (data=new nodeの値または情報)
    (pick node=検索するノードのデータ値)

    💻 select_remove

    def select_remove(self, pick_node):
           prev_node = self.head                    # head값으로 초기 설정. 삭제할 노드를 찾았을 때 이전 노드의 next 값을 변경하기 위함.
           current_node = self.head.next            # head.next의 값. 이 변수를 통해 직접적인 값을 비교.
    
           while self.head is not None:
               if self.head.data == pick_node:      # head 값이 삭제해야할 데이터 값일 때, 실행
                   self.head = None
                   self.head = self.head.next
                   break
               if current_node.data == pick_node:   # 직접적인 값을 비교
                   prev_node.next = current_node.next
                   break
               else:
                   prev_node = current_node         # 다음 노드로 순차적 이동
                   current_node = current_node.next
    このメソッドにはselect Insertと同じナビゲーション構造も含まれています.
    削除する値とノードの値を直接比較する場合、前のノードのポインタを簡単に変更して、前のノードの情報と現在の比較ノードの情報を含む2つの変数を生成すべきだと思います.
    if文に最初に入り、headノードの値を検索する値と比較し、直接値を比較します.
    以降のif文では、値が一致すると、前のノードのポインタが変更されます.値が一致しないときに次のノードに移動するように設定します.

    🧐 How was it...and?


    1.配列との違いは?


    実際、必要なデータを検索して挿入または削除しようとすると、探索のプロセスが発生します.
    これにより,挿入と削除においてO(1)の時間的複雑さが探索+(挿入または削除)の過程となるため,O(n)と何ら変わらない.

    2.その他の実施


    上記の例に示すように、データに直接アクセスするかheadに直接値を割り当てるわけではありません.
    「スタックノード」を使用する実装方法とノード情報を含む戻り値をメソッドで受信し、他のメソッドで使用されるコードを決定しました.
    自分で実現するのもいいと思います.ノードとオブジェクト変数の基本フレームワークを見て、コードを書きましたが、より効率的なコードがあることを確認しました.
    いろいろな面でまだよく勉強していないようで、自分もたくさんの残念な思いを残しました.