데이터 구조의 python 은 양 방향 순환 링크 를 실현 합 니 다.

1. 양 방향 순환 링크
각 노드 는 두 개의 링크 가 있다. 하 나 는 앞의 노드 를 가리 키 고 이 노드 가 첫 번 째 노드 일 때 마지막 노드 를 가리킨다.다른 하 나 는 다음 노드 를 가리 키 고 이 노드 가 마지막 노드 일 때 첫 번 째 노드 를 가리킨다.
2. 조작

is_empty () 링크 가 비어 있 는 지 여부

length () 링크 길이

travel () 링크 옮 겨 다 니 기

add (item) 링크 헤드 추가

append (item) 링크 끝 에 추가

insert (pos, item) 지정 위치 추가

remove (item) 노드 삭제

search (item) 노드 가 존재 하 는 지 찾기

3. 코드 구현

class Node(object):
    #    
    def __init__(self,item):
        self.item = item  #     
        self.next = None  #        
        self.pre =  None  #       


class DoubleCycLinkList(object):
    #     
    def __init__(self):
        #           ,       
        self.__head = None

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

    def length(self):
        """    """
        if self.is_empty():
            return 0
            #      ，    
        count = 1
        cur = self.__head
        while cur.next is not self.__head:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        """      """
        if self.is_empty():
            return
            #     ，      
        cur = self.__head
        while cur.next is not self.__head:
            print(cur.item, end=" ")
            #        
            cur = cur.next
        # while        
        print(cur.item)

    def add(self,item):
        """        """
        #       
        node = Node(item)
        if self.is_empty():
            self.__head = node
            node.next = node
            return

        #        
        cur = self.__head
        while cur.next is not self.__head:
            cur = cur.next
        # while     ，cur     

        #     next        
        node.next = self.__head
        #            
        self.__head = node

        #          
        cur.next = self.__head
        #           
        self.__head.pre = cur

    def append(self,item):
        """"        """
        #         
        if self.is_empty():
            self.add(item)
            return

        #    ,    
        cur = self.__head
        while cur.next is not self.__head:
            #     pre    
            cur = cur.next
        # while     ,cur     
        #    ,        
        node = Node(item)
        #          
        cur.next = node
        #      pre      
        node.pre = cur

        #         
        node.next = self.__head
        #     pre     
        self.__head.pre = node

    def insert(self,pos, item):
        """        """
        if pos <=  0:
            self.add(item)
        elif pos >= self.length():
            self.append(item)
        else:
            # 1     ,       
            index = 0
            cur = self.__head
            while index < (pos - 1):
                index += 1
                cur = cur.next
            #      ,cur  pos    -
            node = Node(item)
            # 2、     next  pos     
            node.next = cur.next
            #  pos      pre     
            cur.next.pre = node
            # 3、 pos            
            cur.next = node
            #      pre  pos     
            node.pre = cur

    def remove(self,item):
        """    """
        if self.is_empty():
            return
            #   pre           
        pre = None
        cur = self.__head
        while cur.next is not self.__head:
            if cur.item == item:
                #       
                #   pre  ，                 
                if pre is None:
                    #      
                    temp = self.__head
                    while temp.next is not self.__head:
                        temp = temp.next
                    # while    ，temp     
                    #              
                    self.__head = cur.next
                    #              
                    cur.next.pre = self.__head
                    #          
                    temp.next = self.__head
                    #           
                    self.__head.pre = temp
                else:
                    #       
                    #       next      next      
                    pre.next = cur.next
                    cur.next.pre = cur.pre
                return
            # pre     cur     
            pre = cur
            cur = cur.next

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

    def search(self,item):
        """        """
        if self.is_empty():
            return False

        cur = self.__head
        while cur.next is not self.__head:
            if cur.item == item:
                return True
            cur = cur.next
        #        
        if cur.item == item:
            return True
        return False


if __name__ == '__main__':
    sll = DoubleCycLinkList()
    print(sll.length())
    sll.add(1)
    sll.add(2)
    sll.add(3)
    print("11111===========")
    sll.travel()
    sll.append(4)
    sll.travel()
    print("=====")
    sll.remove(1)
    sll.travel()
    sll.remove(4)
    sll.travel()
    sll.remove(3)
    sll.travel()
    sll.insert(-10,0)
    sll.travel()
    sll.insert(10, 10)
    sll.travel()
    sll.insert(1, 1)
    sll.travel()
    print(sll.length())
    print("======")
    print(sll.search(0))
    print(sll.search(2))
    print(sll.search(10))
    print(sll.search(7))
    sll.travel()

이상 의 내용 은 개인의 총 결 을 대표 하 는 것 일 뿐 입 니 다. 잘못된 점 이 있 으 면 비판 하고 지적 해 주 십시오. 여러분 이 함께 공부 하 는 것 을 환영 합 니 다!