データ構造とアルゴリズム-python記述-一方向ループチェーンテーブル

# coding:utf-8

#            ：
# is_empty()         
# length()        
# travel()   
# add(item)          
# append(item)          
# insert(pos, item)      pos    
# remove(item)       
# search(item)         


class Node(object):
    """  """

    def __init__(self, item):
        self.elem = item
        self.next = None


class SingleCycleLinkedList(object):
    """      """

    def __init__(self, node=None):
        self.__head = node
        #   node   ，               
        if node:
            node.next = node

    def is_empty(self):
        """        """
        return self.__head is None

    def length(self):
        """       """
        if self.is_empty():
            return 0
        else:
            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
        else:
            cur = self.__head

            while cur.next is not 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 is not self.__head:
                cur = cur.next
            node.next = self.__head
            self.__head = node
            cur.next = node

    def append(self, item):
        """         ，   """
        node = Node(item)

        if self.is_empty():
            self.__head = node
            node.next = node
        else:
            #           
            cur = self.__head
            while cur.next is not self.__head:
                cur = cur.next
            cur.next = node
            node.next = self.__head

    def insert(self, pos, item):
        """     pos    """
        if pos <= 0:
            self.add(item)
        elif pos > (self.length() - 1):
            self.append(item)
        else:
            node = Node(item)
            prev = self.__head
            count = 0
            while count < pos - 1:
                count += 1
                prev = prev.next
            #     ，prev             
            node.next = prev.next
            prev.next = node

    def remove(self, item):
        """      ，          ，         ，   ，      """
        if self.is_empty():
            return
        else:
            cur = self.__head
            pre = None

            while cur.next is not self.__head:
                if cur.elem == item:
                    #       ，      
                    if cur is self.__head:
                        #    ，       
                        rear = self.__head
                        while rear.next is not 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

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

    def search(self, item):
        """        """
        if self.is_empty():
            return False
        else:
            cur = self.__head
            while cur.next is not self.__head:
                if cur.elem == item:
                    return True
                else:
                    cur = cur.next
            #     ，cur     ，           ，         
            if cur.elem == item:
                return True
            else:
                return False


if __name__ == "__main__":
    scll = SingleCycleLinkedList()

    print("befor initialized:", scll.is_empty())
    print("befor initialized:", scll.length())

    scll.add(1)
    scll.add(2)
    scll.add(3)
    scll.add(4)
    scll.add(5)
    scll.add(6)
    scll.travel()

    scll.append(7)
    scll.travel()

    scll.insert(3, 99)
    scll.travel()

    print("scll.search(99):", scll.search(99))

    scll.remove(99)
    scll.travel()