Python 实现双向循环链表：基于视频课程的完整代码示例

阿澈

发布时间：2026-10-14| 6人浏览过

原创

本文基于 B 站 Python 数据结构课程思路，补充实现了双向循环链表的完整操作。通过 Node 和 DoubleCycleLinkList 类，展示了判空、长度计算、遍历、头插法及节点查找等核心功能。代码包含双向指针处理逻辑，适合希望深入理解链表底层实现的开发者参考交流。

双向循环链表实现背景

在阅读本文之前，建议先观看 B 站上的“Python 数据结构与算法系列课程”。该课程中并未涵盖双向循环链表的实现部分，因此本文依据该视频中的链表设计思路，补充实现了双向循环链表的各项操作。欢迎读者阅读、交流，若涉及侵权问题，请联系博主处理。

Python 代码实现

以下是具体的代码实现：


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


class DoubleCycleLinkList:
  def __init__(self, node=None):
    self.__head = node

  def is_empty(self):
    """判空"""
    if self.__head is None:
      return True
    return False

  def length(self):
    """链表长度"""
    if self.is_empty():
      return 0
    cur = self.__head
    count = 1
    while cur.next is not self.__head:
      count += 1
      cur = cur.next
    return count

  def travel(self):
    """遍历链表"""
    if self.is_empty():
      return
    cur = self.__head
    while cur.next is not self.__head:
      print(cur.elem, end=" ")
      cur = cur.next
    print(cur.elem, end=" ")
    print("")

  def add(self, elem):
    """头插法"""
    node = Node(elem)
    if self.is_empty():
      self.__head = node
      node.prev = node
      node.next = node
    else:
      self.__head.prev.next = node
      node.prev = self.__head.prev
      node.next = self.__head
      self.__head.prev = node
      self.__head = node

  def append(self, elem):
    """尾插法"""
    node = Node(elem)
    if self.is_empty():
      self.__head = node
      node.prev = node
      node.next = node
    else:
      node.next = self.__head
      node.prev = self.__head.prev
      self.__head.prev.next = node
      self.__head.prev = node

  def insert(self, pos, elem):
    """任一位置（pos）插入， 下标从0数起"""
    if pos <= 0:
      self.add(elem)
    elif pos > (self.length() - 1):
      self.append(elem)
    else:
      count = 0
      cur = self.__head
      node = Node(elem)
      while count < (pos - 1):
        count += 1
        cur = cur.next
      node.next = cur.next
      node.prev = cur
      node.next.prev = node
      cur.next = node

  def remove(self, elem):
    """删除某一节点，若有多个符合条件的节点，删除第一个即可"""
    if self.is_empty():
      return
    cur = self.__head
    while cur.next is not self.__head:
      if cur.elem == elem:
        if cur is self.__head:
          self.__head = cur.next
          cur.prev.next = cur.next
          cur.next.prev = cur.prev
        else:
          cur.prev.next = cur.next
          cur.next.prev = cur.prev
        break
      cur = cur.next
    if cur.elem == elem:
      cur.prev.next = self.__head
      self.head = cur.prev

  def search(self, elem):
    """查找某一个节点"""
    if self.is_empty():
      return False
    cur = self.__head
    while cur.next is not self.__head:
      if cur.elem == elem:
        return True
      cur = cur.next
    # while中处理不到尾节点，所以进行最后尾节点的判断
    if cur.elem == elem:
      return True
    return False