python实现单链表,双链表合并python

  python实现单链表,双链表合并python

  本文主要详细介绍了基于python的双向链表的实现。本文中的示例代码非常详细,具有一定的参考价值。感兴趣的朋友可以参考一下。

  00-1010一、建立链表节点二。实现一个链表类III。在一些面试或扣分题中要求用双向链表实现测试逻辑。下面是一个基于python的双向链表实现。

  

目录

  类别节点:

  def __init__(self,key,value):

  初始化方法

  :参数键:

  :参数值:

  self.key=key

  自我价值=价值

  self.prev=无

  self.next=无

  def __str__(self):

  val={%s: %s} % (self.key,self.value)

  返回值

  def __repr__(self):

  val={%s: %s} % (self.key,self.value)

  返回值

  除了一些节点的基本属性,还有__str__方法自定义print(node)的字符串描述(类似Java的toString()),以及__repr__方法自定义直接调用node类时的字符串描述。

  

一、构建链表节点

  逻辑主要包括添加头、添加尾、删除头、删除尾、删除任意节点。所有对双向链表的操作都是基于这些方法,具体流程写在注释里。

  class DoubleLinkedList:

  def __init__(self,capacity=0xffffffff):

  双向链表

  :param capacity:链表容量初始化为int 2 32-1的最大值

  :返回:

  自我能力=能力

  self.size=0

  self.head=无

  self.tail=无

  def __add_head(self,node):

  向链表头添加一个节点。

  头节点不存在。新添加的节点是头节点和尾节点。

  头节点已经存在。新添加的节点是新的头节点。

  3360 ParamNode 3360要添加的节点

  :返回:个添加的节点

  #标题节点为空

  如果不是自己. head:

  self.head=node

  self.tail=node

  self.head.next=无

  self.tail.prev=None

  #头节点不为空

  else:

  node.next=self.head

  self.head.prev=node

  self.head=node

  self.head.prev=None

  self.size=1

  返回节点

  def __add_tail(self,node):

  向链表的末尾添加一个节点

  尾节点不存在。新添加的节点是头节点和尾节点。

  尾节点已经存在。新添加的节点是新的尾节点。

  3360参数节点3360添加的节点

  :返回:个添加的节点

  #尾节点为空。

  如果不是self.tail:

  self.tail=node

  self.head=node

  self.head.next=无

  self.tail.prev=None

  #尾巴

  部节点不为空

          else:

              node.prev = self.tail

              self.tail.next = node

              self.tail = node

              self.tail.next = None

          self.size += 1

          return node

      def __remove_head(self):

          """

          删除头部节点

              头部节点不存在 返回None

              头部节点已存在 判断链表节点数量 删除头部节点

          :return: 头部节点

          """

          # 头部节点不存在

          if not self.head:

              return None

          # 链表至少存在两个节点

          head = self.head

          if head.next:

              head.next.prev = None

              self.head = head.next

          # 只存在头部节点

          else:

              self.head = self.tail = None

          self.size -= 1

          return head

      def __remove_tail(self):

          """

          删除尾部节点

              尾部节点不存在 返回None

              尾部节点已存在 判断链表节点数量 删除尾部节点

          :return: 尾部节点

          """

          # 尾部节点不存在

          if not self.tail:

              return None

          # 链表至少存在两个节点

          tail = self.tail

          if tail.prev:

              tail.prev.next = None

              self.tail = tail.prev

          # 只存在尾部节点

          else:

              self.head = self.tail = None

          self.size -= 1

          return tail

      def __remove(self, node):

          """

          删除任意节点

              被删除的节点不存在 默认删除尾部节点

              删除头部节点

              删除尾部节点

              删除其他节点

          :param node: 被删除的节点

          :return: 被删除的节点

          """

          # 被删除的节点不存在

          if not node:

              node = self.tail

          # 删除的是头部节点

          if node == self.head:

              self.__remove_head()

          # 删除的是尾部节点

          elif node == self.tail:

              self.__remove_tail()

          # 删除的既不是头部也不是尾部节点

          else:

              node.next.prev = node.prev

              node.prev.next = node.next

              self.size -= 1

          return node

      def pop(self):

          """

          弹出头部节点

          :return: 头部节点

          """

          return self.__remove_head()

      def append(self, node):

          """

          添加尾部节点

          :param node: 待追加的节点

          :return: 尾部节点

          """

          return self.__add_tail(node)

      def append_front(self, node):

          """

          添加头部节点

          :param node: 待添加的节点

          :return: 已添加的节点

          """

          return self.__add_head(node)

      def remove(self, node=None):

          """

          删除任意节点

          :param node: 待删除的节点

          :return: 已删除的节点

          """

          return self.__remove(node)

      def print(self):

          """

          打印当前链表

          :return:

          """

          node = self.head

          line =

          while node:

              line += %s % node

              node = node.next

              if node:

                  line += =>

          print(line)

  

  

三、测试逻辑

  

if __name__ == __main__:

      double_linked_list = DoubleLinkedList(10)

      nodes = []

      # 构建十个节点的双向列表

      for i in range(10):

          node_item = Node(i, i)

          nodes.append(node_item)

      double_linked_list.append(nodes[0])

      double_linked_list.print()

      double_linked_list.append(nodes[1])

      double_linked_list.print()

      double_linked_list.pop()

      double_linked_list.print()

      double_linked_list.append_front(nodes[2])

      double_linked_list.print()

      double_linked_list.append(nodes[3])

      double_linked_list.print()

      double_linked_list.remove(nodes[3])

      double_linked_list.print()

      double_linked_list.remove()

      double_linked_list.print()

  测试结果:

  

  以上就是本文的全部内容,希望对大家的学习有所帮助,也希望大家多多支持盛行IT软件开发工作室。

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: