python实现单向循环链表 -- 详细思路分析

单向循环链表其实就是在单向链表的基础上，让尾节点的下一个节点指向头节点，整个链表形成一个闭环。所以在整体思路上，和单向链表类似，只是在考虑问题时，需要考虑尾部节点指向头部节点的指针。

1.构造单向循环链表

1.1 构造节点

单向循环链表的节点与单向链表相同，因此，这部分的代码没有区别。

class Node(object):
    """节点"""
    def __init__(self,item):
        self.elem = item
        # 创建Node时，还不存在下一个节点,因此默认指定为None
        self.next = None

1.2 构造函数

作用：构造头节点

• 思路与单向链表相同
• 传入node时，由于是单向循环链表，因此node的next指针指向自身

class SingleLinklist(object):
    """单链表"""
    def __init__(self,node=None):     
        # 单向循环链表创建头节点后，头节点末尾指向自身
        self.__head = None
        if node:
            node.next = node

1.3 is_empty函数

作用：用于判断链表是否为空

• 思路和代码都与单向链表相同

 def is_empty(self):
        """判断是否为空"""
        return self.__head == None

1.3 length函数

作用：用于返回链表的长度

• 构建一个cur游标，起使指向头节点的位置，即cur = self.__head
• 创建一个计数器count，用于计算长度
• 单向循环链表的遍历条件为while cur.next != self.__head，由于遍历条件会少算一次【不算尾节点】，因此count需要从1开始计数
• 当cur的next指针所指的不是self.__head时遍历，每遍历一次，count+1，cur移动一个索引位置

def length(self):
        """返回长度"""
        if self.is_empty():
            return 0
        # 建立一个游标，由于对链表进行遍历
        # 当count = 0 时，可以解决链表为空的情况
        cur = self.__head
        # 区别单向链表，此时count需要从1开始
        count = 1
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count

1.4 travel函数

作用：遍历整个链表

• 创建一个cur游标，起使指向头节点的位置，即cur = self.__head
• 当cur的next指针所指的不是self.__head时遍历，打印当前cur所指的元素
• 由于while循环内不会打印尾节点的元素，因此退出循环后，要打印当前cur游标所处的尾节点的元素
  【注意】
• 由于单向循环链表的遍历条件，因此都需要考虑链表为空的情况
• 当链表为空时，结束函数

def travel(self):
        """遍历列表"""
        # 链表为空时直接结束
        if self.is_empty():
            return 
        cur = self.__head
        while cur.next != self.__head:
            print(cur.elem,end =" ")
            cur = cur.next
        # 循环退出后cur指向尾节点
        # 但尾节点的元素没有打印
        print(cur.elem)

1.5 add函数【头插法】

作用：在链表头部添加元素

• 创建cur游标，让其移动到尾节点
• 让node的next针先指向当前的头节点，然后在重新设置node为头节点
• 让cur的next指针指向node
  【注意】
• 当链表为空时，将头节点赋值为node，然后让node的下一个节点指向自身

 def add(self,item):
        """在头部添加元素 头插法"""
        node = Node(item)
        # 链表为空的情况
        if self.is_empty()
            self.__head = node
            node.next = node
        else:
            # 找到尾节点
            cur = self.__head
            while cur.next !- self.__head:
                cur = cur.next
            # 循环退出后，cur指向尾节点    
            node.next = self.__head  # 让新节点的下一个元素指向当前头节点的元素
            self.__head = node
            cur.next = node

1.6 append函数【尾插法】

作用：在链表尾部添加元素

• 大致思路与单向链表相同
  【注意】
• 当链表为空时，不存在cur.next，因此需要考虑链表为空的情况
• 当链表为空时，直接将当前的头节点赋值为node，node的next指针指向自身，当前尾节点的next指针指向node

def append(self,item):
        """在尾部添加元素 尾插法"""
        # 注意item是传进来的一个数据，不是节点
        node = Nonde(item)
        # 需要考虑链表为空的情况
        if self.is_empty():
            self.__head = node
            node.next = node
            
        cur = self.__head
        # 让cur一直往后走，走到尾节点
        while cur.next != self.__head:
            cur = cur.next
            
        node.next = self.__head
        cur.next = node

1.7 search函数

作用：查找节点是否存在

• 当cur的next指针所指的不是self.__head时遍历。每次对比cur是否和item相等，相等则返回True，结束遍历，不相等则cur移动一个索引位置，继续比较
• 退出循环后，游标处于尾节点，需要对比尾节点的元素是否和item相等，相等则返回True，结束遍历，不相等则返回False
  【注意】
• 当链表为空时，不存在cur.next，因此需要考虑链表为空的情况
• 当链表为空时，直接返回False

 def search(self,item):
        """查找某个元素是否存在"""
        cur = self.__head
        # 链表为空时直接返回False
        if self.is_empty():
            return False
        # 当cur没有移动到末尾时
        while cur.next != self.__head:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        # 游标指向尾节点，需要判断尾节点是否是item
        if cur.elem == ietm:
            return True
        return False

1.8 insert函数

作用：在指定位置插入元素

• insert方法与单向链表完全相同

# insert方法与单链表相同
    def insert(self,pos,item):
        """在指定位置添加节点"""
        # 特殊情况
        if pos <= 0:
        # pos小于等于0视为在头部插入元素
            self.add(item)
        # pos大于链表长度，视为在尾部添加
        elif pos > self.length()-1:
            self.append(item)
        
        else:
        # pos 从0开始
        cur = self.__head
        count = 0
         # cur需要移动到pos所在位置的前面
        while count < (pos-1):
            # cur后移
            cur = cur.next
            count += 1
        #当循环退出后，cur指向pos-1位置
        node = Node(item)
        node.next = cur.next
        cur.next = node

1.9 remove函数

作用：删除指定位置元素

• 需要创建两个游标，pre和cur，pre始终指向cur的前一个节点
• 遍历链表【while cur.next != __head】,如果当前节点不是要删除的节点，则移动cur 和 pre
• 当cur指向的元素于要删除的元素相等时，直接让pre的next指针指向cur的next位置，即可删除此节点元素
• 如果要删除的节点为头节点，即cur处于head的位置，需要创建rear游标，让其移动到尾节点的位置【需要让尾节点的next指针指向新的头节点】
• 当前cur处于头节点的位置，让新的头节点指向cur.next
• rear指向的尾节点重新指向新的头节点
  修改完后return结束函数【区别单链表的break】
  【注意】
• 循环退出后处于尾节点，要处理尾节点的情况
• 如果链表只有一个节点，则直接让self.__head为None即可
  如果是遍历到尾节点的部分，则让pre.next = cur.next

def remove(self,item):
        """删除节点"""
        if self.is_empty():
            return
            
        # 需要cur和pre两个游标
        cur = self.__head
        pre = None
        while cur.next != self.__head:
            if cur.elem == item:
                # 如果是头节点，则直接指向cur.next
                if cur == self.__head:
                    # 找到尾节点
                    # 创建一个rear游标，用于查找尾节点
                    while rear.next != self.__head:
                        rear = rear.next
                    # 循环退出后rear处于尾节点
                    self.__head = cur.next
                    rear.next = self.__head                 
                else:
                    # 中间节点
                    pre.next = cur.next
                # 区别单链表，这里必须使用return ,因为循环结束后还有代码
                # 如果使用break，否则删除头节点时会报错
                return
            else:
                # 不是需要删除的节点则移动游标
                pre = cur
                cur = cur.next
        
        # 退出循环时代表处于尾节点
        if cur.elem == item:
            # 当链表只有1个节点时
            if cur == self.__head:  # 或者pre == None??  
                self.head = None
            else:
                pre.next = cur.next

2 完整代码

class SingleLinklist(object):
    """单链表"""
    def __init__(self,node=None):     
        # 单向循环链表创建头节点后，头节点末尾指向自身
        self.__head = None
        if node:
            node.next = node
        
    def is_empty(self):
        """判断是否为空"""
        return self.__head == None
    
    def length(self):
        """返回长度"""
        if self.is_empty():
            return 0
        # 建立一个游标，由于对链表进行遍历
        # 当count = 0 时，可以解决链表为空的情况
        cur = self.__head
        # 区别单向链表，此时count需要从1开始
        count = 1
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count
    
    def travel(self):
        """遍历列表"""
        # 链表为空时直接结束
        if self.is_empty():
            return 
        cur = self.__head
        while cur.next != self.__head:
            print(cur.elem,end =" ")
            cur = cur.next
        # 循环退出后cur指向尾节点
        # 但尾节点的元素没有打印
        print(cur.elem)
        
    def add(self,item):
        """在头部添加元素 头插法"""
        node = Node(item)
        # 链表为空的情况
        if self.is_empty()
            self.__head = node
            node.next = node
        else:
            # 找到尾节点
            cur = self.__head
            while cur.next !- self.__head:
                cur = cur.next
            # 循环退出后，cur指向尾节点    
            node.next = self.__head  # 让新节点的下一个元素指向当前头节点的元素
            self.__head = node
            cur.next = node
        
        
    def append(self,item):
        """在尾部添加元素 尾插法"""
        # 注意item是传进来的一个数据，不是节点
        node = Nonde(item)
        # 需要考虑链表为空的情况
        if self.is_empty():
            self.__head = node
            node.next = node
            
        cur = self.__head
        # 让cur一直往后走，走到尾节点
        while cur.next != self.__head:
            cur = cur.next
            
        node.next = self.__head
        cur.next = node
        
        
    # insert方法与单链表相同
    def insert(self,pos,item):
        """在指定位置添加节点"""
        # 特殊情况
        if pos <= 0:
        # pos小于等于0视为在头部插入元素
            self.add(item)
        # pos大于链表长度，视为在尾部添加
        elif pos > self.length()-1:
            self.append(item)
        
        else:
        # pos 从0开始
        cur = self.__head
        count = 0
         # cur需要移动到pos所在位置的前面
        while count < (pos-1):
            # cur后移
            cur = cur.next
            count += 1
        #当循环退出后，cur指向pos-1位置
        node = Node(item)
        node.next = cur.next
        cur.next = node
        
    def remove(self,item):
        """删除节点"""
        if self.is_empty():
            return
            
        # 需要cur和pre两个游标
        cur = self.__head
        pre = None
        while cur.next != self.__head:
            if cur.elem == item:
                # 如果是头节点，则直接指向cur.next
                if cur == self.__head:
                    # 找到尾节点
                    # 创建一个rear游标，用于查找尾节点
                    while rear.next != self.__head:
                        rear = rear.next
                    # 循环退出后rear处于尾节点
                    self.__head = cur.next
                    rear.next = self.__head                 
                else:
                    # 中间节点
                    pre.next = cur.next
                # 区别单链表，这里必须使用return ,因为循环结束后还有代码
                # 如果使用break，否则删除头节点时会报错
                return
            else:
                # 不是需要删除的节点则移动游标
                pre = cur
                cur = cur.next
        
        # 退出循环时代表处于尾节点
        if cur.elem == item:
            # 当链表只有1个节点时
            if cur == self.__head:  # 或者pre == None??  
                self.head = None
            else:
                pre.next = cur.next
        
    def search(self,item):
        """查找某个元素是否存在"""
        cur = self.__head
        # 链表为空时直接返回False
        if self.is_empty():
            return False
        # 当cur没有移动到末尾时
        while cur.next != self.__head:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        # 游标指向尾节点，需要判断尾节点是否是item
        if cur.elem == ietm:
            return True
        return False