在 Python 中用链表模仿字典列表

我将以我的思维过程和可视化来开始这篇文章。一个实验（你可以选择这样称呼它）让我大开眼界，更清楚地了解链表是什么。这让我不再将其视为抽象的，而是以陈词滥调的方式（数据和下一个）来解释它。

思维过程和可视化

最近我开始从更物理的角度（通常称为 OOP）来看待代码。然而，我的超越了类和属性；我开始在每次 while 和 for 循环之前写下步骤和算法。厌倦了仅仅为了目的而陷入抽象。这让我尝试了更多的事情，这进一步教会了我更多的事情，我将在本文中分享这些事情。

在我们深入研究之前三个关键问题和答案：

• 链表由什么组成？
• 节点是什么样的？
• 链表一开始是什么样子的？

回答第一个；节点组成一个链表。

对于第二个问题；将链表中的节点想象成一辆汽车牵引另一辆汽车。在这种情况下，假设两辆车都装有货物。第二辆车用链条固定在第一辆车的后面。节点通过保存数据（例如汽车中的货物或乘客）在链接列表中执行此操作。这种数据类型可以很简单，如整数或字符串，也可以是更复杂的数据结构。同时，每辆车都有一个连接器（链条）将其与道路上的下一辆车连接起来。在链表中，这是下一个属性，它指向下一个节点或之前节点（在双向链表中）的内存地址。没有 next 属性的列表不是链表。

每辆车只知道它前面或后面的汽车（取决于链表的类型）。最后一辆车没有链条，这意味着它指向任何东西。在链接列表中，这通常由 None 表示。

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

回答第三个问题；头节点启动一个链表，就像第一辆车开始拖车一样。

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 作为参数，允许方法接受任意数量的关键字参数，而无需显式定义每个参数。

每个节点不仅仅存储单个数据，而是将多个数据（用户名和肤色）组合成一个，使其比整数或字符串等基本数据结构更复杂。

我们现在将创建一个 My_List 类，它将管理 My_Dict 实例的链接列表。它需要一个 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 实例后，我们通过检查头部是否存在来确保列表不为空。如果头不存在，则意味着列表为空，因此我们将 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 初始化为 head，这将用于查找最后一个节点（列表的末尾），以便可以将新节点附加到那里。 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 实例的链接列表，维护头部并提供插入方法以在末尾添加新条目。每个节点通过next指针连接到下一个节点，模拟链表结构。

算法

编写代码时拥有算法总是好的。这称为所采取的步骤。也许我应该在上面的代码之前编写它们。但我只是想首先展示日常陈词滥调的链表和更复杂的类型之间的区别。话不多说，以下是步骤。

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 列表中，通过索引访问元素的时间复杂度为 O(1)（常数时间），因为 Python 列表本质上是数组。在末尾添加新字典通常是 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 字典，也不完全相同。

下面是我们如何继承 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'] = 用户名和 self['complexion'] = 肤色 将用户名和肤色存储为字典条目，允许像字典一样访问 My_Dict 实例（例如，new_dict['username']）。还有一个
next 属性初始化为 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 中的 keys 方法，允许它返回 My_Dict 中的所有键。使用 super().keys() 调用父级
keys() 方法，确保标准的字典行为。

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

在 MyList 类的 insert 方法中，我们可以看到如何使创建的字典实例表现出字典行为。我们将keys()方法链接到它，并且我们还用它评估用户名密钥。我们在 if 和 else 块中执行此操作。在 if 块中，它打印头节点的键和用户名。在 else 块中，它打印其他节点的键和其他节点的用户名。

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       

我们使用 current_dict 中的每个键值对构建一个字典。 current_dict = getattr(current_dict, 'next', None) 移动到下一个节点，继续直到 current_dict 变为 None。

注意：当涉及到内存使用时，让我们的类继承自 dict 意味着更多的内存使用。与我们之前创建的类似字典的节点的链表不同。

结论

本文的目的是提供更多关于链表的观点和见解，超出我通常所理解的范围。我没有创新。我只是在尝试代码，试图为那些可能认为代码过于抽象的人提供更多见解。不过我想从更资深的程序员那里知道，如果使用或过去使用时可能会有什么缺点。

以上是在 Python 中用链表模仿字典列表的详细内容。更多信息请关注PHP中文网其他相关文章！