python算法与数据结构-双向链表-蒲公英云

python算法与数据结构-双向链表

た入场券 2023-10-06 01:25 116阅读 0赞

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 1

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 2

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 3

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 4

尾部添加元素如下所示:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 5

指定位置插入元素如下所示:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 6

上面的对的可以比照下面的图片看，node2节点相当于上图中的cur节点，如下所示:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 7

代码等价于:

node.next = cur <===> node.next = node2
node.prev = cur.prev <===> node.prev = node1
cur.prev.next = node <===> node1.next = node
cur.prev = node <===> node2.prev = node

删除元素如下所示:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 8

结合下图查看，如下所示:

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 9

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 10

watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70 11

具体代码如下所示:

# -*-coding=utf-8-*-
class Node(object):
     """结点"""
     def __init__(self,item):
         self.elem = item
         self.next = None
         self.prev = None
class DoubleLinkList(object):
      """双链表"""
      def __init__(self,node=None):
          self.__head = None
      def is_empty(self):
          """链表是否为空"""
          return self.__head is None
      def length(self):
          """链表长度"""
          #cur游标，用来移动遍历节点
          cur = self.__head
          #count 记录数量
          count = 0
          while cur != None:
               count+=1
               cur = cur.next
          return  count
      def travel(self):
           """遍历整个链表"""
           cur = self.__head
           while cur != None:
               print(cur.elem,end=" ")
               cur = cur.next
           print("")
      def add(self,item):
           """链表头部添加元素，头插法"""
           node = Node(item)
           #先写箭头指向右边的代码，node节点先写next方向的，再写prev方向的
           node.next = self.__head
           self.__head = node
           #最后写箭头指向左边的代码
           node.next.prev = node
      def append(self,item):
           """链表尾部添加元素，尾插法"""
           node = Node(item)
           if self.is_empty():
               self.__head = node
           else:
               cur = self.__head
               while cur.next != None:
                   cur = cur.next
               cur.next = node
               node.prev = cur
      def insert(self, pos, item):
          """链表指定位置添加元素
          :param pos 从0开始
          """
          # 若指定位置pos为第一个元素之前，则执行头部插入
          if pos <= 0:  # 头插法
              self.add(item)
          # 若指定位置超过链表尾部，则执行尾部插入
          elif pos > (self.length() - 1):  # 尾插法
              self.append(item)
          # 找到指定位置
          else:
              # pre用来指向指定位置pos的前一个位置pos-1，初始从头节点开始移动到指定位置
              cur = self.__head
              count = 0
              while count < pos:
                  count += 1
                  cur = cur.next
              # 当循环退出后,cur指向pos位置
              node = Node(item)
              node.next = cur
              node.prev = cur.prev
              cur.prev.next = node
              cur.prev = node
      def remove(self, item):
          """删除节点"""
          cur = self.__head
          while cur != None:
              # 找到了指定元素
              if cur.elem == item:
                  # 先判断此节点是否是头节点
                  # 头节点 # 如果第一个就是删除的节点
                  if cur == self.__head:
                      # 将头指针指向头节点的后一个节点
                      self.__head = cur.next
                      if cur.next:
                          #判断链表是否只有一个节点
                          cur.next.prev = None
                  else:
                      cur.prev.next = cur.next
                      if cur.next:
                          cur.next.prev = cur.prev
                  break  # 删除后再退出循环,需要一个总的break退出
              else:
                  # 继续按链表后移节点
                  cur = cur.next
      def search(self, item):
          """查找节点是否存在"""
          """链表查找节点是否存在，并返回True或者False"""
          cur = self.__head
          while cur != None:
              if cur.elem == item:
                  return True
              else:
                  cur = cur.next
          return False
if __name__ == "__main__":
    # node = Node(100)
    ll = DoubleLinkList()
    print(ll.is_empty())  # True
    print(ll.length())  # 0
    ll.append(1)
    print(ll.is_empty())  # False
    print(ll.length())  # 1
    ll.append(2)
    ll.add(8)
    ll.append(3)
    ll.append(4)
    ll.append(5)
    ll.append(6)
    # 8 1 2 3 4 5 6
    ll.insert(-1, 9)
    ll.travel()  # 9 8 1 2 3 4 5 6
    ll.insert(3, 100)
    ll.travel()  # 9 8 1 100 2 3 4 5 6
    ll.insert(10, 200)
    ll.travel()  # 9 8 1 100 2 3 4 5 6 200
    ll.remove(100)
    ll.travel()  # 9 8 1 2 3 4 5 6 200
    ll.remove(9)
    ll.travel()  # 8 1 2 3 4 5 6 200
    ll.remove(200)
    ll.travel()  # 8 1 2 3 4 5 6