单向循环列表如图所示

单向循环链表的实现

一、往链表头部添加一个节点值为4
1、新增一个节点node=Node(4)

新建一个节点

    node=Node(data)
    if self.is_empty():
        #即是头节点也是尾节点
        self.head=node
        #node.next=self.head
    else:
        # 先让node指向当前链表中的头节点
        node.next=self.head
        # 再让链表的尾节点的next指向node
        cur=self.head
        while cur.next!=self.head:
            cur=cur.next
        cur.next=node
        #再让链表的head指向当前node节点
        self.head=node
    #添加节点之后，链表的长度加1
    self._length+=1

二、往链表尾部添加一个节点

新建一个节点node，值为data

    node=Node(data)
    # 找到链表的尾节点
    # 思路：从头节点开始遍历链表中的所有节点]

    # 每次判断当前节点的next是否为空
    # 为空这说明当前节点就是尾节点
    # 不为空，通过当前节点的next方法去访问下一个节点，
    if self.head:
        cur = self.head
        while cur.next != self.head:
            cur = cur.next
        cur.next = node        #原本的尾节点指向新建的节点
    else:
        self.head=node
    node.next=self.head     #新的尾节点指向当前的头节点
    # 让当前的尾节点的指针指向新建的节点node
    # 链表的长度加1
    self._length+=1

三、往链表中插入一个节点

    if pos<=0:
        self.add(data)
    elif pos>self._length:
        self.append(data)
    else:
        # 1新建一个节点
        node = Node(data)
        # 2找到链表中索引为pos-1的节点
        cur=self.head
        while pos-1:
            cur=cur.next
            pos-=1
        #到这里之后，cur指向的是索引为pos-1的节点
        # node.next=prev_node.next
        # 3让node的next指向索引为pos的节点
        node.next=cur.next
        # 4让索引为pos-1的节点的next指向node
        cur.next=node
        # 5链表的长度加1
        self._length+=1

四、删除链表中第一个值为data的节点
1、删除的值为头部节点

2、删除的值为非头节点

a、先要判断链表是否为空，为空那必然没有值为data的节点

#判断链表是否为空，为空那必然没有值为data的节点
        cur=self.head
        flag=True       # 标志位的作用：让第一次循环能进入
        prev=None
        while cur!=self.head or flag:
            if cur.data==data:
                flag=False      #让循环继续的条件就是cur!=self.head
                #如果前驱节点为空，说明我们要删除的节点是第一个节点
                if not prev:
                    #找到尾节点
                    last_node=self.head
                    while last_node.next!=self.head:
                        last_node=last_node.next
                    #让尾节点的next指向头节点
                    last_node.next=self.head.next
                    self.head=cur.next          #self.head.next
                else:
                    prev.next = cur.next
                self._length-=1
                return 0
            prev=cur
            cur = cur.next
        return -1

五、修改链表中指定位置节点的值

    # 修改链表中指定位置节点的值
    if 0<pos<self._length:
        cur = self.head
        while pos:
            cur = cur.next
            pos -= 1
        cur.data=data
    else:
        print('输入的范围不符合要求')

六、查找链表中是否有节点的值为data

    if self.is_empty():
        return False
    cur = self.head
    flag=True
    while cur!=self.head or flag:
        flag=False
        if cur.data == data:
            return True
        cur = cur.next
    return False

代码块：

class Node:

    def __init__(self, data, _next=None):
        self.data = data  # 数据域
        self.next = _next  # 指针域


class SingleCycleLinkList:

    def __init__(self):
        self.head = None  # 链表的的头节点
        self._length = 0  # 链表的长度，链表的元素个数
        #self.tail=None    # 链表的尾节点
    def is_empty(self):
        # 判断链表的是否为空
        return self._length==0

    def length(self):
        # 返回链表的长度
        return self._length

    def nodes_list(self):
        # 返回链表中的所有节点的值组成的列表
        res=[]
        #判断链表是否为空
        if self.is_empty():
            return res

        else:
            res.append(self.head.data)
            cur=self.head.next
            while cur!=self.head:
                res.append(cur.data)
                cur=cur.next
            return res


    def add(self, data):
        # 往链表的头部添加一个节点，值为data
        # 新建一个节点
        node=Node(data)
        if self.is_empty():
            self.head=node
            node.next=self.head
        else:
            # 先让node指向当前链表中的头节点
            node.next=self.head
            # 再让链表的尾节点的next指向node
            cur=self.head
            while cur.next!=self.head:
                cur=cur.next
            cur.next=node
            #再让链表的head指向当前node节点
            self.head=node
        #添加节点之后，链表的长度加1
        self._length+=1

    def append(self, data):
        # 往链表的尾部添加一个节点，值为data
        # 新建一个节点node，值为data
        node=Node(data)
        # 找到链表的尾节点
        # 思路：从头节点开始遍历链表中的所有节点
        # 每次判断当前节点的next是否为空
        # 为空这说明当前节点就是尾节点
        # 不为空，通过当前节点的next方法去访问下一个节点，
        if self.head:
            cur = self.head
            while cur.next != self.head:
                cur = cur.next
            cur.next = node        #原本的尾节点指向新建的节点
        else:
            self.head=node
        node.next=self.head     #新的尾节点指向当前的头节点
        # 让当前的尾节点的指针指向新建的节点node
        # 链表的长度加1
        self._length+=1
    def insert(self, pos, data):
        # 往链表的指定位置插入一个节点，值为data
        if pos<=0:
            self.add(data)
        elif pos>self._length:
            self.append(data)
        else:
            # 1新建一个节点
            node = Node(data)
            # 2找到链表中索引为pos-1的节点
            cur=self.head
            while pos-1:
                cur=cur.next
                pos-=1
            #到这里之后，cur指向的是索引为pos-1的节点
            # node.next=prev_node.next
            # 3让node的next指向索引为pos的节点
            node.next=cur.next
            # 4让索引为pos-1的节点的next指向node
            cur.next=node
            # 5链表的长度加1
            self._length+=1

    def remove(self, data):
        # 删除链表中第一个值为data的节点
        # 判断链表是否为空，为空那必然没有值为data的节点
        cur=self.head
        flag=True       # 标志位的作用：让第一次循环能进入
        prev=None
        while cur!=self.head or flag:
            if cur.data==data:
                flag=False      #让循环继续的条件就是cur!=self.head
                #如果前驱节点为空，说明我们要删除的节点是第一个节点
                if not prev:
                    #找到尾节点
                    last_node=self.head
                    while last_node.next!=self.head:
                        last_node=last_node.next
                    #让尾节点的next指向头节点
                    last_node.next=self.head.next
                    self.head=cur.next          #self.head.next
                else:
                    prev.next = cur.next
                self._length-=1
                return 0
            prev=cur
            cur = cur.next
        return -1

    def modify(self, pos,data):
        # 修改链表中指定位置节点的值
        if 0<pos<self._length:
            cur = self.head
            while pos:
                cur = cur.next
                pos -= 1
            cur.data=data
        else:
            print('输入的范围不符合要求')

    def search(self, data):
        # 查找链表中是否有节点的值为data
        if self.is_empty():
            return False
        cur = self.head
        flag=True
        while cur!=self.head or flag:
            flag=False
            if cur.data == data:
                return True
            cur = cur.next
        return False

if __name__ == '__main__':
    l1=SingleCycleLinkList()    #新建一个链表类
    # print(l1.head,l1.length())
    # l1.add(1)
    # print(l1.head.data, l1.length())
    # print(l1.nodes_list())
    # l1.add(5)
    # print(l1.head.data, l1.length())
    # print(l1.nodes_list())
    #
    # print(l1.head.data,l1.head.next.data,l1.head.next.next.data)   #验证是循环的
    # l1.append(2)
    # print(l1.head.data, l1.length())
    # print(l1.nodes_list())
    # print(l1.head.data, l1.head.next.data, l1.head.next.next.data,l1.head.next.next.next.data)  # 验证是循环的
    # l1.insert(1,7)
    # print(l1.nodes_list())
    # l1.insert(-1, 6)
    # print(l1.nodes_list())
    # print(l1.is_empty())
    # l1.remove(7)
    # print(l1.nodes_list())
    # l1.modify(2,8)
    # print(l1.nodes_list())
    # print(l1.search(8))
    l1.add(1)
    l1.add(2)
    l1.add(3)
    l1.add(4)
    l1.add(5)
    print(l1.nodes_list())
    l1.remove(5)
    print(l1.nodes_list())
    l1.modify(1,7)
    print(l1.nodes_list())
    print(l1.search(8))