概念

将单链表的终端节点的指针由原来的空指针改为指向头节点, 就是整个单链表形成一个环, 这种首尾相接的单链表称为单循环链表.

实现

class Node:
    """
    节点
    """

    def __init__(self, value):
        self.data = value
        self.next = None


class CircularLinkedList:
    def __init__(self):
        self.rear = None    # 尾节点

    def is_empty(self):
        return self.rear is None

    # def append(self, elem):
    #     """
    #     尾插法
    #     """
    #     temp = Node(elem)
    #     if self.rear is None:
    #         temp.next = temp
    #         self.rear = temp
    #     else:
    #         temp.next = self.rear.next
    #         self.rear.next = temp
    #         self.rear = temp

    def prepend(self, elem):
        """
        头插法
        """
        temp = Node(elem)
        if self.rear is None:
            temp.next = temp
            self.rear = temp
        else:
            temp.next = self.rear.next
            self.rear.next = temp

    def append(self, elem):
        """
        尾插法
            先将节点插入头部,然后尾指针后移
        """
        self.prepend(elem)
        self.rear = self.rear.next

    def print_all(self):
        if self.is_empty():
            return
        p = self.rear.next      # 取得头部节点
        print('Head', end='')
        while True:
            print('-->', p.data, end='')
            if p is self.rear:      # 到达尾部停止
                break
            p = p.next
        print('-->Finish')

    def pop(self, index=0):
        """
        弹出指定索引的节点, 默认头部节点
        """
        if self.rear is None:
            raise IndexError('pop from empty circular linked list.')
        p = self.rear
        for _ in range(index):
            p = p.next
        target = p.next
        if target is self.rear:
            self.rear = None
        p.next = target.next
        target.next = None
        return target.data

    def __iter__(self):
        if self.rear is None:
            return
        p = self.rear.next
        while p is not self.rear:
            yield p.data
            p = p.next
        yield p.data