单向循环链表

单链表的尾结点不指向None，而是指向头节点，我们称为单向循环链表

单向循环链表的操作

与单链表一样

节点的构造

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

与单链表类似

链表的构造

考虑用户是否传入了节点

• 没有传入节点，也就没有node.next，头节点直接指向空
• 当用户传入了节点，因为是循环链表，所以，节点的next去不能指向None，而是指向node

class singlecyclelinklist(object):
    def __init__(self,node=Node):
        self.__head=node
        if node:
            node.next=node

1.判断链表是否为空

def is_empty(self):
    return self.__head==None

与单链表类似

2.计算链表长度

与单链表相比，不能用cur来进行遍历（链表为空cur也是指向self.head），所以用count.next进行判断
当cur遍历到尾节点，尾结点的next是指向self.head，就代表遍历结束

cur.next==self.__head

当cur指向第一个节点时count=1，但是cur.next的count=2

所以当cur指向尾结点,如果cur的count=1，那么cur.next的count=2

cur.next == self.__head时，count=n+1

所以count一开始要置为1，遍历完后才是链表的长度

def length(self):
    cur=self.__head
    count=1
    while cur.next != self.__head:
        count+=1
        cur=cur.next
        return count

特殊情况

当链表是为空，直接返回0

• 方法1：调用is_empty()；return 0
• 方法2：如果cur==None；return 0

def length(self):
    if self.is_empty():
        return 0
    cur=self.__head
    count=1
    while cur.next !=None:
        count+=1s
        cur=cur.next
        return count

3.遍历链表

思路与单链表类似，但是当指向最后的一个节点的时候没有打印这个节点的元素，所以当遍历结束后，再打印一个尾结点元素即可

def travel(self):
    cur=self.__head
    while cur.next !=None:
        print(cur.elem)
        cur=cur.next
     #退出循环，cur指向尾结点，但尾结点的元素未打印
    print(cur.elem)

特殊情况

当链表为空时，没有cur.next，添加判断函数，什么都不返回

def travel(self):
    if self.is_empty():
        return
    cur=self.__head
    while cur.next != self.__head:
        print(cur.elem)
        cur=cur.next
    print(cur.elem)

4.头部添加元素

与单链表类似，
但是要找到尾结点，并把尾结点指向self.__head，

方法一：先连节点，再找尾节点，不易理解

def add(self,item):
    node=Node(item)
    cur=self.__head
    node.next=self.__head
    self.__head=node
    while cur.next != self.__head:
        cur=cur.next
    #退出循环，cur指向尾结点
    cur.next=node

方法二：先找尾节点，再连节点

def add(self,item):
    node=Node(item)
    cur=self.__head
    while cur.next != self.__head:
        cur=cur.next
    #退出循环，cur指向尾结点
    node.next=self.__head
    self.__head=node
    cur.next=node
    #或者：
    #cur.next=self.__head

特殊情况

链表为空链表，cur指针没有next

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

5.尾部添加元素

def  append(self,item):
    node=Node(item)
    cur=self.__head
    while cur.next != self.__head:
        cur=cur.next
    node.next=cur.next
    cur.next=node

特殊情况

当链表为空，与头插法类似

if self.is_empty():
        self.__head=node
        node.next=node

6.指定位置添加元素

与单链表类似

7.查找元素

与单链表类似，当找到最后一个元素指向self.__head，时就退出了，没有把最后一个元素查找出来

就要进行判断，是否最后一个元素是我们要查找的元素，如果是，返回最后一个元素

def search(self,item):
    cur=self.__head
    while cur.next != self.__head:
        if cur.elem == item:
            return Ture
        else:
            cur=cur.next
        #cur指向尾结点
    if cur.elem ==item:
        return True
    return Flase

特殊情况

当链表为空时：

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

8.删除节点

基本思路与单链表类似

1. 创建两个指针，pre指向None，cur向头节点
2. pre指向的cur，cur往后移，指向下一个节点cur.next
3. 将节点的前一个节点的next指向节点的next域（后一个节点）

当删除的节点cur.next不等于头节点

• 如果，删除的值等于传入的值：

  • 删除的是头节点cur==self.__head
    1. 需要再定义一个指针real
    2. 把尾结点指向的删除的节点，重新向下一个节点

• 删除中间节点

把节点的前一个节点的next指向节点的next域（后一个节点）

• 删除最后退出

• 否则，向下寻找

当从头找到尾没找到，那么此时的情况就是:（cur.next==self.__head）
当前的值cur.elem是要删除的节点，做法与删除中间的类似

def remove(self ,item):
    cur=self.__head
    pre=Node
    while cur.next != self.__head:
        if cur.elem == item:
            if cur==self.__head:
                real=self.__head
                while real.next != self.__head:
                    real=real.next
                self.__head=cur.next
                real.next=self.__head
            else:
                pre.next=cur.next
                break
        else:
            pre=cur
            cur=cur.next
    if cur.elem ==item:
        pre.next=cur.next

特殊情况

为空：

        #为空的情况
    if self.is_empty():
         return

当链表只有一个元素的时候，尾部插入的情况，没有pre.next

 if cur.elem == item:
        if cur == self.__head:
            self.__head = None
        else:
            pre.next = cur.next

def remove(self, item):
    if self.is_empty():
        return

    cur = self.__head
    pre = None

    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
            return
        else:
            pre = cur
            cur = cur.next

    if cur.elem == item:
        if cur == self.__head:
            self.__head = None
        else:
            pre.next = cur.next