单向循环链表

---

单向循环链表：

在单向链表中，头指针是相当重要的，因为单向链表的操作都需要头指针，所以如果头指针丢失或者破坏，
那么整个链表都会遗失，并且浪费链表内存空间。

单向循环链表的构成：

如果把单链表的最后一个节点的指针指向链表头部，而不是指向NULL，那么就构成了一个单向循环链表。

python实现单向循环链表

class Node():
    '''单循环链表的结点：next默认指向头结点'''
    def __init__(self,elem):
        self.elem = elem
        self.next = None

class SingleCycleLinkList():
    '''循环单链表'''
    def __init__(self,node=None):
        self.__head = node
        #node如果不是指向None，说明不是空链表，next虚需要指向自己，构成环
        if node:
            node.next = node

    def is_empty(self):
        '''链表是否为空'''
        # 如果头结点为None，说明为空，返回true
        return self.__head == None


    def length(self):
        '''链表长度：求链表长度需要从头开始遍历并计数；
        注意考虑特殊情况，即链表为空链表，即头结点为None，不会进入循环，需要加判断如果链表为空，直接返回0 ；
        另一种特殊情况，循环链表只有一个结点，cur.next ==self.__head ,
        不会进入循环，返回的count为1'''
        if self.__head == None:
            return 0
        else:
            # 游标cut表示指向当前结点，初始指向头结点 
            cur =self.__head
            # count用来计数，从1开始
            count = 1
            #循环退出条件：由于单循环链表的尾结点不指向None，而是指向头结点；
            #所以当游标cur.next指向头结点时，整个链表循环一遍，循环结束。
            while cur.next != self.__head:
                #循环一次，count计数加1
                count += 1
                #游标cur也向后移动一个结点
                cur = cur.next
            # 循环结束，count的值即为链表长度，返回count
            return count 
       
    
    def travel(self):
        '''遍历整个链表:需要从头开始，输出每个结点的元素；
         注意考虑特殊情况，即链表为空链表，即头结点为None，不需要输出任何元素，所以需要另外写判断处理,如果为空，直接返回
        另一种特殊情况，链表只有一个结点，即cur.next == self._head ,不会进入循环，直接打印结点，符合要求 '''
        if self.is_empty():
            return
        else:
            #定义游标cur表示指向当前结点，初始指向头结点
            cur = self.__head
            #循环退出条件：由于单循环链表的尾结点不指向None，而是指向头结点；
            #所以当游标cur.next指向头结点时，整个链表循环一遍，循环结束
            while cur.next != self.__head:
                #输出当前指向元素
                print(cur.elem,end=' ')
                #游标向后移动一个结点
                cur = cur.next
            #由于循环结束时，即cur指向最后一个结点时，无法进入循环，所以最后一个结点没有输出，循环结束后补上最后一个结点
            print(cur.elem)
       
    
    def add(self,item):
        '''在头部插入结点:不需要遍历；
        注意考虑特殊情况，链表为空链表，即头结点为None，需单独判断处理。
        考虑另一种特殊情况，即非空时且链表只有一个元素，此时cur.next ==self.__head
        不会进入循环，符合要求，不用单独处理'''
        #定义要插入的结点
        node = Node(item)
        #判断如果链表为空，要插入的node即为头结点
        if self.is_empty():
            self.__head == node
            #自己的next指向自己形成循环
            node.next = node
        else:
            #如果链表不会空
            cur = self.__head
            while cur.next != self.__head:
                cur =  cur.next
            
            # 现将要插入的结点的next指向头结点
            node.next = self.__head
            # 再将头结点变成要插入的结点
            self.__head = node
            #循环结束后此时cur指向最后一个结点
            cur.next = self.__head


      
    def append(self,item):
        '''在尾部插入结点：需要从头遍历找到尾结点，在其后插入结点;
        考虑特殊情况，即向空链表尾部插入结点，空链表即头结点为空，需单独考虑，故需要在开始是判断链表是否为空'''
        #定义要插入的结点
        node = Node(item)
        #如果循环链表为空
        if self.__head == None:
            #要插入的node即为头结点
            self.__head = node
            # 自己的next指向自己形成循环
            node.next = node
        else:
            # 定义游标cur表示指向当前结点，初始时指向头结点
            cur = self.__head
            #循环退出条件，找到尾结点退出，即cur.next 指向头结点self.__head
            while cur.next != self.__head:
                # 游标向后移动一个结点
                cur = cur.next
            # 循环结束后，游标刚好指向尾结点，插入元素,首先要插入的结点的next指向头结点
            node.next = self.__head #或者node.next = cur.next也行
            # 当前结点的next指向要插入的结点
            cur.next = node

        
    
    def insert(self,pos,item):
        '''在指定位置插入结点：插入前需要遍历找到指定位置，在指定位置前插入;
        考虑特殊情况，如果pos输入的值小于等于0，则认为是在头部插入一个结点，
        如果输入的pos值比链表长度还大，则认为要在为不插入结点'''
        # 定义要插入的结点
        node = Node(item)
        if pos <= 0:
            self.add(item)
        elif pos > self.length()-1:
            self.append(item)
        else:
            # 定义游标pre表示指向所找位置的前一个结点,初始从头结点开始
            pre = self.__head
            #从头开始循环并用count计数，循环退出条件为 count < pos-1
            # count =0  pre指向0号结点  count=1 pre指向1号结点，pre到pos-1的结点即可
            count = 0
            while count < pos-1:
                # count加1
                count += 1
                # pre向后移动一个结点
                pre = pre.next 
            #循环结束，pre指向pos-1的结点，即pos的前一个结点，在pos结点的前面，pos-1结点的后面插入元素
            node.next = pre.next
            pre.next = node


               

    def remove(self,item):
        '''删除指定元素结点：遍历找到元素为item的结点，便删除，如果链表中有多个结点的元素与item相同，则只删除第一个;
        注意考虑特殊情况,链表为空，直接返回false即可，需单独判断
        另外的特殊情况，链表不为空，若删除的为第一个结点，需单独判断操作,
        由于循环结束时，没有判断尾结点，需要在循环结束后单独判断，并考虑特殊情况即循环链表中只有一个节点的情况'''
        if self.is_empty():
            return False
        else:
            #定义游标cur指向当前结点，初始指向头结点
            cur = self.__head
            #定义游标pre指向当前结点的前一个结点，初始也指向头结点
            pre = self.__head
            # 从头开始循环遍历每个结点,cur.next指向头结点时，说明循环结束
            while cur.next != self.__head:
                if cur.elem == item:
                    #如果找到了，判断是否为第一个结点
                    if cur == self.__head:

                        #如果要删除的是第一个结点
                        # 先循环找到尾结点
                        #定义游标rear，初始指向头结点
                        rear = self.__head
                        while rear.next != self.__head:
                            rear = rear.next
                        #循环结束，此时rear指向尾结点
                        self.__head = cur.next
                        rear.next = self.__head
                    else:
                        #要删除的元素是循环链表中间的元素
                        pre.next = cur.next
                        #返回True，循环结束
                    return True
                else:
                    #如果没有找到，游标pre向后移动一个结点
                    pre = cur
                    # 游标cur也移动一个结点，注意，一定是先移动pre后移动cur，保持前后关系
                    cur = cur.next
            #循环结束，此时cur指向最后一个结点，并没有判断
            if cur.elem == item:
                #如果最后一个结点就是要删除的结点，
                #判断 链表是否只有一个结点
                if cur == self.__head:
                    #如果只有这一个结点，即让链表为空
                    self.__head = None
                else:
                    # 删除,即将pre结点的next指向头结点
                    pre.next = cur.next
                    return True
            return False


     
                            

    
    def search(self,item):
        '''查询指定元素结点：从头循环遍历链表，找到第一个元素为item的结点，输出值；
        注意考虑特殊情况 如果链表为空，则cur就是指向None，直接返回flase，需单独判断处理；
        考虑另一种特殊情况，如果链表只有一个结点，即cur.next 开始就指向头结点，则不进入循环直接判断，程序合理'''
        if self.is_empty():
            return False
        else:
            # 定义游标cur 表示指向当前结点，初始指向头结点
            cur = self.__head
            #循环链表，查找
            while cur.next != self.__head:
                if cur.elem == item :
                    # 如果找到了，则输出，并返回True
                    print(cur.elem)
                    return True
                else:
                    #如果没有找到，cur向后移动一个结点
                    cur = cur.next
            #循环退出后cur指向尾结点，无法进入循环，需要判断
            if cur.elem == item:
                print(cur.elem)
                return True
            # 整个链表遍历结束仍然没有找到，返回false
            return False

if __name__ == '__main__':

    ll = SingleCycleLinkList()
    print(ll.is_empty())
    res = ll.length()
    print(res)
    ll.append(10)
    ll.append(8)
    ll.append(3)
    ll.append(5)
    ll.append(4)
    ll.travel()
    ll.add(100)
    ll.travel()
    res = ll.length()
    print(res)
    ll.travel()
    print(ll.is_empty())
    ll.insert(3,50)
    ll.travel()
    ll.insert(0,90)
    ll.travel()
    ll.insert(8,40)
    ll.travel()
    ll.search(3)
    ll.search(90)
    ll.search(40)

    ll.remove(8)
    ll.travel()
    ll.remove(90)
    ll.travel()
    ll.remove(40)

    ll.travel()

    
        

True
0
10 8 3 5 4
100 10 8 3 5 4
6
100 10 8 3 5 4
False
100 10 8 50 3 5 4
90 100 10 8 50 3 5 4
90 100 10 8 50 3 5 4 40
3
90
40
90 100 10 50 3 5 4 40
100 10 50 3 5 4 40
100 10 50 3 5 4