Python でリンクされたリストを使用して辞書のリストを模倣する

この記事は私の思考プロセスと視覚化から始めます。この実験 (そう呼ぶこともできます) により、リンク リストとは何なのかをより明確に理解できるようになりました。これにより、私はそれを抽象的なものとして見るのをやめ、いつも説明されている決まり文句のやり方 (データと次) に従うようになりました。

思考プロセスと視覚化

最近、私はコードをより物理的な観点 (通常 OOP と呼ばれる) から見るようになりました。ただし、私の場合はクラスや属性を超えています。私は、while ループと for ループの前に、ステップとアルゴリズムを書き留め始めました。目的のためだけに抽象化に飛び込むのにはうんざりしました。これにより、さらにいくつかのことを試すようになり、さらにいくつかのことを学びました。それをこの記事で共有します。

さらに深く掘り下げる前に、3 つの重要な質問と回答:

• リンクされたリストは何で構成されますか?
• ノードはどのようなものですか?
• リンクされたリストは最初はどのように見えますか?

最初に答えると、ノードはリンクされたリストを構成します。

2 番目の質問については、リンクされたリスト内のノードを、別の車を牽引する車のようなものと考えてください。このシナリオでは、両方の車に物品が積まれていると仮定します。 2両目は1両目の後ろにチェーンで連結されています。ノードは、車両内の商品や乗客などのデータを保持することにより、これをリンクリスト内で実行します。このデータ型は、整数や文字列のような単純なデータ型にすることも、より複雑なデータ構造にすることもできます。同時に、各車には道路上の次の車に接続するコネクター (チェーン)が付いています。リンク リストでは、これは 次のノード または前のノード (二重リンク リスト内) の メモリ アドレス を指す 次の属性 です。 next 属性のないリストはリンク リストではありません。

各車は、(リンク リストの種類に応じて) 直前または直後の車についてのみ認識します。最後の車にはチェーンがありません。つまり、何も指していません。リンクされたリストでは、これは多くの場合 None で表されます。

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

3 番目の質問に答えるには;最初の車両が牽引を開始するのと同じように、ヘッド ノードはリンク リストを開始します。

class LinkedList:
    def __init__(self):
      self.head = None

これまで、リンク リストの基本について説明してきました。ここからは、この記事を書いた主な理由について説明します。

導入

Python の組み込みデータ構造 (リストや辞書など) は、データを保存および管理するための柔軟な方法を提供します。リストを使用すると、順序付けされたシーケンスを保存できます。一方、辞書を使用すると、簡単にアクセスできるようにキーと値をペアにすることができます。

この記事では、合成を使用して辞書のようなリンク リストを作成する方法を検討します。辞書のようなリンクされたリストと辞書のリストの間でメモリ使用量に差があることがわかります。また、ノードが dict から継承を取得して、ノード インスタンスを実際の辞書にする方法についても説明します。これらはすべて、リンクされたリストを理解するためのより多くの視点を提供するためのものです。

リンクリストの作成

前に調べたように、リンク リストはノードで構成されます。これらのノードにはそれぞれデータ セグメントと次のセグメントがあります。データは文字列や整数のような単純なものも、複雑なものも可能です。

シンプル:

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

Node クラス (My_Int で表される) には属性として data と next があります。

class LinkedList:
    def __init__(self):
      self.head = None

この記事では複雑なケースを扱います:

複合体:

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

ノード クラス (My_Dict で表される) は、ユーザー名、顔色、次の複数の属性を保持します。 **kwargs を引数として使用すると、メソッドはキーワード引数をそれぞれ明示的に定義せずに、任意の数だけ受け入れることができます。

各ノードは単一のデータを保存するだけではなく、複数のデータ (ユーザー名と顔色) を 1 つに結合するため、整数や文字列のような基本的なデータ構造よりも複雑になります。

ここで、My_Dict インスタンスのリンクされたリストを管理する My_List クラスを作成します。 head 属性を取ります。通常、このヘッドはリンク リストを初期化する最初のノードです。

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


class LinkedList:
          def __init__(self):
                 self.head=None
          def  insert(self, node):
                  if self.head==None:
                     self.head = node
                     return

                  last_node = self.head
                  while(last_node.next):
                      last_node =last_node.next
                  last_node.next = node

          def traverse(self):
                current_node = self.head
                while(current_node):
                    print(current_node.data, end="->")
                    current_node = current_node.next
                print("None")

node1 = My_Int(5)
node2 = My_Int (10)
node3 = My_Int(15)

linked_list = LinkedList()
linked_list.insert(node1)
linked_list.insert(node2)
linked_list.insert(node3)
linked_list.traverse()

このクラスは、最後に新しいノード エントリを追加するための挿入メソッドも提供します。
ここで My_Dict のインスタンス (ノード) も作成します。 My_List は、リンク リスト構造内の My_Dict オブジェクトのコンテナとして機能します。各 My_Dict インスタンスは、My_List が My_Dict インスタンスの走査と挿入を動的に管理できるようにする次の参照によって接続されます。これは基本的に合成の例です。

My_Dict インスタンスの作成後、ヘッドの存在をチェックしてリストが空でないことを確認します。 head が存在しない場合は、リストが空であることを意味するため、self.head を新しいノード (my_dict) として初期化します。 return はすぐに関数を終了します。これ以上実行する必要はありません。

class My_Dict: #dict keys as attributes
    def __init__(self, **kwargs):
        self.username = kwargs['username']
        self.complexion = kwargs['complexion']
        self.next = None

return の後の行は、以前にリストにノードがあり、新しいノードを挿入したいときに実行されます。そのノード last_dict をヘッドとして初期化し、これを使用して最後のノード (リストの最後) を検索し、そこに新しいノードを追加できるようにします。 while ループは、最後のノードに到達するまでリストを繰り返します。 last_dict.next が None に等しくない限り、last_dict = lastdict.next と設定することで次のノードに移動します。

最後に last_dict.next = my_dict は my_dict をリストの最後に追加して挿入を完了します。 last_dict.next が None であることがわかったら (つまり、最後のノードにいます)、そこに my_dict をアタッチします。

今度はトラバース関数を扱います:

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

トラバース関数は、リンクされたリスト内の各ノードを反復処理し、先頭から最後まで各ノードでアクション (この場合は印刷) を実行します。このメソッドは、リスト内のすべてのノードの連続ビューを提供します。

以下の完全なコードをご覧ください:

class LinkedList:
    def __init__(self):
      self.head = None

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

上記の実装は、辞書のようなオブジェクトのカスタム リンク リストと考えることができますが、標準的な Python の典型的な辞書リストとは構造が異なります。 注意点は次のとおりです:

• My_Dict クラス: 各インスタンスは、属性 (ユーザー名と顔色) と次のポインターを備えた辞書のようなオブジェクトとして機能し、別の My_Dict インスタンスにリンクできます。
• My_List クラス: このクラスは、My_Dict インスタンスのリンクされたリストを管理し、先頭を維持し、最後に新しいエントリを追加する挿入メソッドを提供します。各ノードはネクスト ポインターを介して次のノードに接続され、リンク リスト構造をシミュレートします。

アルゴリズム

コードを書くときにアルゴリズムがあることは常に良いことです。これは、実行されたステップとして知られています。おそらく、上記のコードの前にそれらを記述する必要がありました。ただし、私は、毎日の決まり文句のリンク リストとより複雑なタイプの違いを最初に示したかっただけです。早速、以下に手順を示します。

1. ノード構造の属性を使用してクラスを作成します。
2. LinkedList (またはその他) という名前の別のクラスを作成します。唯一の属性として頭を追加します。ヘッドの作成 = なし。
3. ノードを作成して挿入するには:
   • Node のインスタンスを作成します。
   • リストが空の場合、ノード インスタンスを head の値にします。
   • リストが空でない場合は、値を先頭として前のノードを設定します。
   • 条件チェックあり;前のノードの次の属性が None でない場合、リストをループします。
   • 最後に、前のノードの次を新しいノードを指すように設定します。
4. リストを移動するには:
   • 一時ノードを作成し、head を開始値として設定します。
   • 一時ノードが None でない場合の条件を含むループ。
   • 一時ノードのデータを印刷します。
   • 一時ノードを次へ移動
   • 最後に、次は None なので、None を出力します。
5. 必要に応じてクラス インスタンスを作成します。

辞書一覧との比較

ここで、いくつかの点に注目して、上記の内容を Python の辞書リストと比較してみます。

• 構造と保管:

辞書のリスト: Python では、辞書のリストは各辞書を連続したリスト構造の要素として保存し、インデックスを介して各辞書にアクセスできるようにします。

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

辞書のリンク リスト: 私たちのコードはリンク リスト構造を使用しており、各ノード (辞書のような My_Dict インスタンス) は、連続したメモリ ストレージを使用するのではなく、次のノードへの参照を保持します。要素が頻繁に変更される場合、大きなリストの場合、これはメモリ効率が高くなりますが、位置によるアクセスの場合は遅くなります。

• アクセスと挿入: 辞書のリスト: 標準の Python リストでは、Python リストは内部で配列であるため、インデックスによる要素へのアクセスは O(1) (定数時間) です。新しい辞書を最後に追加する場合、通常は O(1) ですが、サイズ変更が必要な場合は O(n) になります。

辞書のリンク リスト: リンク リストでは、ノードごとに反復する必要があるため、要素にアクセスするにはトラバーサル (O(n) 時間) が必要です。毎回最後のノードを見つける必要があるため、最後に挿入する場合も O(n) になります。ただし、新しいノードを先頭に設定できるため、先頭への挿入は O(1) で済みます。

• メモリ使用量:

辞書のリスト: Python リストは、各項目が順番に格納されるため、連続したブロックに辞書を格納するためにより多くのメモリを使用します。メモリは Python リストに動的に割り当てられ、リストが大きくなると、リストのサイズ変更やコピーが行われることがあります。これは、sys モジュールを使用してコードで証明できます。

class LinkedList:
    def __init__(self):
      self.head = None

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

辞書のリンク リスト: リンク リストは、必要に応じてメモリのみを割り当てるため、各ノードのメモリを効率的に使用します。ただし、各ノードの次の参照のために追加のスペースが必要です。

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


class LinkedList:
          def __init__(self):
                 self.head=None
          def  insert(self, node):
                  if self.head==None:
                     self.head = node
                     return

                  last_node = self.head
                  while(last_node.next):
                      last_node =last_node.next
                  last_node.next = node

          def traverse(self):
                current_node = self.head
                while(current_node):
                    print(current_node.data, end="->")
                    current_node = current_node.next
                print("None")

node1 = My_Int(5)
node2 = My_Int (10)
node3 = My_Int(15)

linked_list = LinkedList()
linked_list.insert(node1)
linked_list.insert(node2)
linked_list.insert(node3)
linked_list.traverse()

class My_Dict: #dict keys as attributes
    def __init__(self, **kwargs):
        self.username = kwargs['username']
        self.complexion = kwargs['complexion']
        self.next = None

上記から、バイト単位の違いがわかります。 776と192。

技術的には辞書ではありません

私たちのコードでは、My_Dict インスタンスは真の辞書ではなく、辞書のようなオブジェクトです。

その理由は次のとおりです。

• 次の属性は My_Dict インスタンスを相互にリンクし、スタンドアロンの辞書というよりもリンク リスト内のノードに似たものにします。この次の属性は、通常の辞書にあるような機能ではありません。

  • メソッドと動作: 辞書のようなオブジェクト (My_Dict インスタンスなど) は、辞書に似たメソッドや動作を持つことができますが、技術的には辞書ではありません。 .keys()、.values()、.items() などのメソッドや、ハッシュなどの辞書固有の操作がありません。 My_Dict オブジェクトをより辞書のように動作させたい場合は、Python の組み込み dict を継承してメソッドを実装し、それらに辞書機能を与えることができます。しかし現状では、これらのオブジェクトはキーと値のスタイルでデータを格納するものの、Python 辞書を継承したり、Python 辞書とまったく同じように動作したりするわけではないため、辞書に似ています。

以下は、dict クラスから継承する方法を示しています。

class My_List: #manager
    def __init__(self):
        self.head=None

def insert(self, **kwargs):
        my_dict = My_Dict(**kwargs) #instantiate dict
        #check if list is empty
        if self.head==None:
            self.head=my_dict
            return

        last_dict = self.head
        while(last_dict.next): 
            last_dict = last_dict.next
            last_dict.next = my_dict #makes the insertion dynamic       

最初の行は、Python の入力モジュールから Dict をインポートします。これは、My_Dict が特殊な辞書であることを示しています。

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

My_Dict クラスは dict から継承します。つまり、辞書のプロパティを持ちますが、カスタマイズできます。

class LinkedList:
    def __init__(self):
      self.head = None

コンストラクターを見てみましょう:

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

__init__ は、ユーザー名と顔色属性を使用して My_Dict のインスタンスを初期化します。 super().__init_() は、親 Dict クラスのコンストラクターを呼び出します。 self['username'] = username および self['complexion'] = complexion は、ユーザー名と顔色を辞書エントリとして保存し、My_Dict インスタンスに辞書のようにアクセスできるようにします (例: new_dict['username'])。
もあります 次の属性は None として初期化され、各 My_Dict インスタンスが別のインスタンスにリンクできるようにすることでリンク リスト構造を設定します。

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


class LinkedList:
          def __init__(self):
                 self.head=None
          def  insert(self, node):
                  if self.head==None:
                     self.head = node
                     return

                  last_node = self.head
                  while(last_node.next):
                      last_node =last_node.next
                  last_node.next = node

          def traverse(self):
                current_node = self.head
                while(current_node):
                    print(current_node.data, end="->")
                    current_node = current_node.next
                print("None")

node1 = My_Int(5)
node2 = My_Int (10)
node3 = My_Int(15)

linked_list = LinkedList()
linked_list.insert(node1)
linked_list.insert(node2)
linked_list.insert(node3)
linked_list.traverse()

上記のメソッドは、dict のキー メソッドをオーバーライドして、My_Dict 内のすべてのキーを返すことができるようにします。 super().keys() を使用すると、親
が呼び出されます。 key() メソッドにより、標準の辞書動作が保証されます。

class My_Dict: #dict keys as attributes
    def __init__(self, **kwargs):
        self.username = kwargs['username']
        self.complexion = kwargs['complexion']
        self.next = None

MyList クラスの挿入メソッドでは、作成された辞書のインスタンスが辞書の動作を示すようにする方法を確認できます。これにkeys()メソッドを連鎖させ、それを使用してユーザー名キーも評価します。これを if ブロックと else ブロックで行います。 if ブロックでは、ヘッド ノードのキーとユーザー名が出力されます。 else ブロックでは、他のノードのキーと他のノードのユーザー名を出力します。

class My_List: #manager
    def __init__(self):
        self.head=None

辞書内包表記内の上記の traverse メソッド内:

def insert(self, **kwargs):
        my_dict = My_Dict(**kwargs) #instantiate dict
        #check if list is empty
        if self.head==None:
            self.head=my_dict
            return

        last_dict = self.head
        while(last_dict.next): 
            last_dict = last_dict.next
            last_dict.next = my_dict #makes the insertion dynamic       

current_dict からの各キーと値のペアを使用して辞書を構築します。 current_dict = getattr(current_dict, 'next', None) は次のノードに移動し、current_dict が None になるまで継続します。

注: メモリ使用量に関して言えば、クラスを dict から継承させると、より多くのメモリ使用量が発生することになります。以前に作成した辞書のようなノードのリンク リストとは異なります。

結論

この記事の目的は、リンク リストとは何かについて、私が通常説明しているものを超えた、より多くの視点と洞察を提供することです。私は革新的ではありませんでした。私はただコードを実験していて、コードが抽象的すぎると考えている人たちに、より多くの洞察を提供しようとしていました。ただし、上級プログラマーから、使用した場合、または過去に使用した場合にどのような欠点があるのか​​を知りたいと思っています。

以上がPython でリンクされたリストを使用して辞書のリストを模倣するの詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。