학습 노트 - 순환 싱글 체인 시트 (Python 구현)

순환 싱글 체인 표 는 싱글 체인 표 의 변형 으로 마지막 노드 의 next 도 메 인 은 None 이 아니 라 표 의 첫 번 째 노드 를 가리킨다.
순환 목록 대상 에 표 끝 점 을 기록 하면 O (1) 시간의 표 머리 / 표 끝 삽입 과 O (1) 시간의 표 머리 삭 제 를 실현 할 수 있 습 니 다.
순환 링크 의 결점 이 하나의 원 으로 연결 되 기 때문에 어느 결점 이 표 두 나 표 미 이 고 주로 개념 문제 이 며 표 의 형태 에서 구분 할 수 없다.
다음은 간단 한 순환 단일 체인 표 류 를 실 현 했 는데 그 중에서 몇 가지 전형 적 인 조작 을 포함한다.

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

    def __repr__(self):  #        ‘  ’     ，            
        return str(self.elem)


class LCList:
    def __init__(self):
        self.rear = None

    def is_empty(self):
        """
                 
        :return: boolean
        """
        return self.rear == None

    def prepend(self, elem):  #     
        p = Node(elem)
        if self.rear is None:
            p.pnext = p  #         
            self.rear = p
        else:
            p.pnext = self.rear.pnext
            self.rear.pnext = p

    def append(self, elem):  #     
        self.prepend(elem)
        self.rear = self.rear.pnext

    def pop_start(self):  #     
        if self.rear is None:
            print("The list is None.")
            return
        p = self.rear.pnext
        if self.rear is p:  #         
            self.rear = None
        else:
            self.rear.pnext = p.pnext  #  rear             
        return p.elem

    def printall(self):
        if self.is_empty():
            return
        p = self.rear.pnext
        print("Head", end=' ')
        while True:
            print("-->", p.elem, end=' ')
            if p is self.rear:
                break
            p = p.pnext
        print("--> None. Linked node finished")


if __name__ == '__main__':
    node1 = Node(elem='node1')
    node2 = Node(elem='node2')
    lclist = LCList()
    lclist.append(node1)
    lclist.append(node2)
    lclist.printall()
    print(lclist.pop_start())
    lclist.printall()