单向循环链表 用python语言描述

单向循环链表

单向循环链表是一个变形的单向链表，他的最后一个节点的地址域是第一个节点的地址

image.png

操作

• is_empty():判断链表是否为空
• length():返回链表的长度
• travel():遍历链表
• add(item):向链表头部中添加元素item
• append(item):向链表尾部添加元素item
• insert(pos, item)：向链表pos处插入元素item
• remove(item)：删除元素item
• search(item):查找元素item

实现

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

class SingleCycleLinkList(object):
    def __init__(self):
        self.__head = None
    
    def is_empty(self):
        return self.__head == None
    
    def length(self):
        '''返回链表的长度'''
        #如果链表为空  返回长度为0
        if self.is_empty():
            return 0
        count = 1
        cur = self.__head
        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=" ")
        print(cur.elem)

添加元素

注意：add(self,item)如果链表为空，添加元素item后 要return 结束函数
insert()函数 分为：

• 插在第一个位置
• 插在最后一个位置
• 插在中间位置

def add(self,item):
    node = Node(item)
    if self.is_empty():
        self.__head = node
        node.next = node
        return
    cur = self.__head
    while cur.next != self.next:
        cur = cur.next
    node.next = self.__head
    self.__head = node
    cur.next = self.__head

def append(self, item):
    node = Node(item)
    cur = self.__head
    if self.is_empty():
        self.__head = node
        node.next = node
    else:
        while cur.next != self.__head:
            cur = cur.next
            node.next = cur.next
            cur.next = node
def insert(self, pos, item):
    if pos<=0:
        self.add(self, item)
    elif: pos>= self.length()-1:
        self.append(self, item)
    else:
          node = Node(item)
          pre = self.__head
          count = 0
          while count <(pos-1):
              pre = pre.next
              count += 1
          node.next = pre.next
          pre.next = node
          

删除元素

删除元素分为

• 空链表
• 链表只包含一个元素（恰好删除）
• 删除第一个元素
• 删除最后一个元素

def (self, item):
    cur = self.__head
        pre = None
        if self.is_empty():
            return
        while cur.next != self.__head:
            if cur.elem == item:
                #判断是否是头结点
                if cur == self.__head:
                    rear = self.__head
                    while rear.next != self.__head:
                        rear = rear.next
                    self.__head = cur.next
                    rear.next = self.__head
                else:
                    pre.next = cur.next
                #注意与单链表区分  单链表是break 
                return
            else:
                pre = cur
                cur = cur.next
        #尾节点
        if cur.elem == item:
            if cur == self.__head:
                ##链表只有一个节点
                self.__head = None
            else:   
                pre.next = cur.next
def search(self, item):
        cur = self.__head
        if self.is_empty():
            return False
        while cur.next != self.__head:
            if cur.elem == item:
                return True
            else:
                cur = cur.next
        if cur.elem == item:
            return True
        return False

可以与单向链表比较：
https://www.jianshu.com/p/f5eebf58db47