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

た入场券 2023-10-06 01:25 3阅读 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

参考:来源网上

[https://www.cnblogs.com/Se7eN-HOU/p/11103891.html][https_www.cnblogs.com_Se7eN-HOU_p_11103891.html]

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200708172701347.png?x-oss-process=image/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]: https://img-blog.csdnimg.cn/20200708172806963.png?x-oss-process=image/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 2]: https://img-blog.csdnimg.cn/20200708172829859.png?x-oss-process=image/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 3]: https://img-blog.csdnimg.cn/20200708172905871.png?x-oss-process=image/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 4]: https://img-blog.csdnimg.cn/202007081729228.png?x-oss-process=image/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 5]: https://img-blog.csdnimg.cn/20200708172947214.png?x-oss-process=image/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 6]: https://img-blog.csdnimg.cn/20200708173047199.png?x-oss-process=image/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 7]: https://img-blog.csdnimg.cn/20200708173133472.png?x-oss-process=image/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 8]: https://img-blog.csdnimg.cn/20200708173219924.png?x-oss-process=image/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 9]: https://img-blog.csdnimg.cn/20200708173248122.png?x-oss-process=image/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 10]: https://img-blog.csdnimg.cn/20200708173312141.png?x-oss-process=image/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 11]: https://img-blog.csdnimg.cn/20200708173327765.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2diNDIxNTI4Nw==,size_16,color_FFFFFF,t_70
[https_www.cnblogs.com_Se7eN-HOU_p_11103891.html]: https://www.cnblogs.com/Se7eN-HOU/p/11103891.html