python实现单链表,单链表python基本操作_1

  python实现单链表,单链表python基本操作

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

  本文分享python实现双向链表的具体代码,供大家参考。具体内容如下

  实现双向链表需要注意什么

  1.如何插入元素,考虑特殊情况:头节点位置和尾节点位置;一般情况:中间位置

  2.如何删除元素,考虑特殊情况:头节点的位置和尾节点的位置;一般情况:中间位置

  

代码实现

  1.构造一个节点类和一个链表类。

  类别节点:

  def __init__(self,data):

  self.data=数据

  self.next=无

  self.previous=None

  类双链接表:

  双向链表

  def __init__(self,node=None):

  自我。_head=node

  以下方法在链表类中实现。

  2.确定链表是否为空。

  定义为_空(自身):

  回归自我。_head无

  3.输出链表的长度

  定义长度(自身):

  计数=0

  if self.is_empty():

  返回计数

  else:

  当前=自身。_head

  虽然当前不是:

  计数=1

  当前=当前。下一个

  返回计数

  4.遍历链表

  定义差旅(自助):

  当前=自身。_head

  虽然当前不是:

  打印(“{0}”。format(current.data),end= )

  当前=当前。下一个

  打印()

  5.通过头部插入添加新元素。

  定义添加(自身,项目):

  节点=节点(项目)

  #如果链表为空,让头指针指向当前节点

  if self.is_empty():

  自我。_head=node

  #注意插入顺序,

  else:

  node.next=self。_head

  自我。_head.previous=node

  自我。_head=node

  6.通过尾部插入添加新元素。

  定义附加(自身,项目):

  节点=节点(项目)

  #如果链表为空,让头指针直接指向节点。

  if self.is_empty():

  自我。_head=node

  #你需要找到尾节点,然后把它和新节点连接起来。

  else:

  当前=自身。_head

  而current.next不是None:

  当前=当前。下一个

  current.next=节点

  node.previous=当前

  7.找出该元素是否存在于链表中。

  定义搜索(自身,项目):

  当前=自身。_head

  发现=假

  而当前不是没有和没有发现:

  if current.data==item:

  发现=真

  else:

  c

  urrent = current.next

          return found

  8. 在某个位置中插入元素

  

def insert(self, item, pos):

          # 特殊位置,在第一个位置的时候,头插法

          if pos <= 0:

              self.add(item)

          # 在尾部的时候,使用尾插法

          elif pos > self.length() - 1:

              self.append(item)

          # 中间位置

          else:

              node = Node(item)

              current = self._head

              count = 0

              while count < pos - 1:

                  current = current.next

                  count += 1

              # 找到了要插入位置的前驱之后,进行如下操作

              node.previous = current

              node.next = current.next

              current.next.previous = node

              current.next = node

  

  

 # 换一个顺序也可以进行

  def insert2(self, item, pos):

          if pos <= 0:

              self.add(item)

          elif pos > self.length() - 1:

              self.append(item)

          else:

              node = Node(item)

              current = self._head

              count = 0

              while count < pos:

                  current = current.next

                  count += 1

              node.next = current

              node.previous = current.previous

              current.previous.next = node

              current.previous = node

  9. 删除元素

  

def remove(self, item):

          current = self._head

          if self.is_empty():

              return

          elif current.data == item:

              # 第一个节点就是目标节点,那么需要将下一个节点的前驱改为None 然后再将head指向下一个节点

              current.next.previous = None

              self._head = current.next

          else:

              # 找到要删除的元素节点

              while current is not None and current.data != item:

                  current = current.next

              if current is None:

                  print("not found {0}".format(item))

              # 如果尾节点是目标节点,让前驱节点指向None

              elif current.next is None:

                  current.previous.next = None

              # 中间位置,因为是双链表,可以用前驱指针操作

              else:

                  current.previous.next = current.next

                  current.next.previous = current.previous

  

# 第二种写法

      def remove2(self, item):

          """删除元素"""

          if self.is_empty():

              return

          else:

              cur = self._head

              if cur.data == item:

                  # 如果首节点的元素即是要删除的元素

                  if cur.next is None:

                      # 如果链表只有这一个节点

                      self._head = None

                  else:

                      # 将第二个节点的prev设置为None

                      cur.next.prev = None

                      # 将_head指向第二个节点

                      self._head = cur.next

                  return

              while cur is not None:

                  if cur.data == item:

                      # 将cur的前一个节点的next指向cur的后一个节点

                      cur.prev.next = cur.next

                      # 将cur的后一个节点的prev指向cur的前一个节点

                      cur.next.prev = cur.prev

                      break

                  cur = cur.next

  10. 演示

  

my_list = DoubleLinkList()

  print("add操作")

  my_list.add(98)

  my_list.add(99)

  my_list.add(100)

  my_list.travel()

  print("{:#^50}".format(""))

  print("append操作")

  my_list.append(86)

  my_list.append(85)

  my_list.append(88)

  my_list.travel()

  print("{:#^50}".format(""))

  print("insert2操作")

  my_list.insert2(66, 3)

  my_list.insert2(77, 0)

  my_list.insert2(55, 10)

  my_list.travel()

  print("{:#^50}".format(""))

  print("insert操作")

  my_list.insert(90, 4)

  my_list.insert(123, 5)

  my_list.travel()

  print("{:#^50}".format(""))

  print("search操作")

  print(my_list.search(100))

  print(my_list.search(1998))

  print("{:#^50}".format(""))

  print("remove操作")

  my_list.remove(56)

  my_list.remove(123)

  my_list.remove(77)

  my_list.remove(55)

  my_list.travel()

  print("{:#^50}".format(""))

  print("remove2操作")

  my_list.travel()

  my_list.remove2(100)

  my_list.remove2(99)

  my_list.remove2(98)

  my_list.travel()

  

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

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

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