Python单向循环链表

单向循环链表与单向链表类似,在操作上,最主要的区别在于判断链表结束的方式.

• 单链表结束,游标cur或next的值为None
• 循环链表结束,游标cur或next值为__head,即指向头部指针
• 这就导致遍历、插入、删除判断条件不同

学习本节请先阅读上一节：Python单向链表

一、节点及链表定义

循环链表的与单向链表相同

1. 节点定义

   class LinkNode:
    def __init__(self, val):
        self.item = val
        self.next = None
   

2. 链表定义

   class CycleLinkList:
    def __init__(self):
        self.__head: LinkNode = None
   

二、链表遍历

注意这里while循环结束方式,是与单链表最大的区别之一. while cur.next != self.__head:,此时游标cur指向最后一个节点,但尚未输出,因此循环结束后,需要输出最后一个元素,即print(cur.item)

    def travel(self):
        if self.is_empty():
            print("linklist id empty")
            return
        cur = self.__head
        while cur.next != self.__head:
            print(cur.item, end=" ")
            cur = cur.next
        # 此时cur位于最后一个节点，他的next指向__head，但是在while循环中并未打印
        print(cur.item)

三、链表查找

这里与循环链表的遍历travel类似,while循环结束后,最后一个节点在while中未进行比较,需要在循环外进行比较操作if cur.item==val:

    def search(self,val):
        if self.is_empty():
            return False
        cur=self.__head
        while cur.next!=self.__head:
            if cur.item==val:
                return True
            cur=cur.next

        if cur.item==val:
            return True
        return False

四、链表插入节点

循环链表的插入与单链表类似,同样需要考虑三种情况:头部插入,尾部插入,中间插入

• 循环链表首尾相连,头部插入和尾部插入,貌似都是在最后面插入一个节点,但是头部插入需要移动head指针,而尾部插入无须移动head指针
• 中间插入与单链表相同

• 头部插入

  • 先将游标cur移动至尾部;
  • 将新节点指向头部
  • 将游标cur指向新节点
  • 移动head指针指向新节点

    def addHead(self, val):
        node = LinkNode(val)
        # 链表为空，head指向node，同时node指向自己
        if self.is_empty():
            self.__head = node
            node.next = node

        cur = self.__head
        while cur.next != self.__head:
            cur = cur.next
        node.next = self.__head
        # 下面两个顺序没有先后
        cur.next = node
        self.__head = node

• 尾部插入

  尾部插入节点与单链表基本相同:

  • 将游标cur移动到链表尾部
  • 将尾部指向新节点:cur的next指向node
  • 将新节点指向链表头部

    def addTail(self,val):
        node=LinkNode(val)
        if self.is_empty():
            self.__head=node
            node.next=node

        cur=self.__head
        while cur.next!=self.__head:
            cur=cur.next
        # node节点链接首尾，head位置不变，这里与在头部插入不同
        cur.next=node
        node.next=self.__head

• 中间插入

  中间插入与单链表基本相同

    def insert(self,pos,val):
        if pos<=0:
            self.addHead(val)
        elif pos>=self.length():
            self.addTail(val)
        else:
            node = LinkNode(val)
            cur=self.__head
            count=0
            while count<(pos-1):
                count+=1
                cur=cur.next
            node.next=cur.next
            cur.next=node

五、链表删除节点

循环链表的删除应该是操作最复杂的功能,需要对三种情况进行逐一理解:

• 头部删除:如果删除元素在链表头部,需要另定义一个游标rear循环至链表尾部,然后将头部head向后移,将rear指向head
• 中间删除:中间删除与单链表类似,不做介绍,同单链表的处理,设置2个游标:pre和cur
• 尾部删除:循环链表的while循环结束后,游标cur在尾部,但没有在while循环中进行处理,因此当查找元素在尾部时,跳出循环后需要单独处理.同时要考虑当链表只有一个节点时,while循环时没有执行的,因此也需要在这里处理.

    def remove(self,val):
        cur=self.__head
        pre=None
        if self.is_empty():
            return False
        while cur.next!=self.__head:
            if cur.item==val:
                # 如果需要删除的元素是在头部，则需要再定义一个游标变量rear，循环至尾部，然后让head指向下一个元素，让
                if cur==self.__head:
                    rear=self.__head
                    while rear.next!=self.__head:
                        rear=rear.next
                    # 由于头部节点已经删除，需要将head向后移动一位，并将尾部（rear）指向新的头部
                    self.__head=cur.next
                    rear.next=self.__head
                else:
                    pre.next=cur.next
                return True
            else:
                pre=cur
                cur=cur.next

        # 跳出循环后，cur位于链表尾部，开始比较尾部是否为要删除数据
        if cur.item==val:
            # 判断链表是否只有一个元素，即cur==__head
            if cur==self.__head:
                self.__head=None
            else:
                pre.next=cur.next
            return True
        # 没有找到元素，返回False
        return False

六、其他功能函数

1. 判断链表为空

   此处同单链表操作,判断头部指针即可

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

1. 计算链表长度

   这里需要注意的是,count从1开始计数,由于前面已经判断链表是否为空None 且while循环判断条件与单链表不同,当只有一个节点时,while循环未启动;当游标cur到最后一个节点时,count在while循环也为+1,所以count计数从1开始.

    def length(self):
        if self.is_empty():
            return 0
        cur = self.__head
        # 这里count的从1开始，注意while循环的终止条件，此时cur到最后一个元素即跳出循环，而count没有即会+1
        count = 1
        # 游标又回到头部节点，即链表遍历完毕，返回链表长度
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count

七、完整代码

class LinkNode:
    def __init__(self, val):
        self.item = val
        self.next = None

class CycleLinkList:
    def __init__(self):
        self.__head: LinkNode = None

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

    def length(self):
        if self.is_empty():
            return 0
        cur = self.__head
        # 这里count的从1开始，注意while循环的终止条件，此时cur到最后一个元素即跳出循环，而count没有即会+1
        count = 1
        # 游标又回到头部节点，即链表遍历完毕，返回链表长度
        while cur.next != self.__head:
            count += 1
            cur = cur.next
        return count

    def travel(self):
        if self.is_empty():
            print("linklist id empty")
            return
        cur = self.__head
        while cur.next != self.__head:
            print(cur.item, end=" ")
            cur = cur.next
        # 此时cur位于最后一个节点，他的next指向__head，但是在while循环中并未打印
        print(cur.item)

    def search(self,val):
        if self.is_empty():
            return False
        cur=self.__head
        while cur.next!=self.__head:
            if cur.item==val:
                return True
            cur=cur.next

        if cur.item==val:
            return True
        return False

    def addHead(self, val):
        node = LinkNode(val)
        # 链表为空，head指向node，同时node指向自己
        if self.is_empty():
            self.__head = node
            node.next = node

        cur = self.__head
        while cur.next != self.__head:
            cur = cur.next
        node.next = self.__head
        # 下面两个顺序没有先后
        cur.next = node
        self.__head = node

    def addTail(self,val):
        node=LinkNode(val)
        if self.is_empty():
            self.__head=node
            node.next=node

        cur=self.__head
        while cur.next!=self.__head:
            cur=cur.next
        # node节点链接首尾，head位置不变，这里与在头部插入不同
        cur.next=node
        node.next=self.__head

    def insert(self,pos,val):
        if pos<=0:
            self.addHead(val)
        elif pos>=self.length():
            self.addTail(val)
        else:
            node = LinkNode(val)
            cur=self.__head
            count=0
            while count<(pos-1):
                count+=1
                cur=cur.next
            node.next=cur.next
            cur.next=node

    def remove(self,val):
        cur=self.__head
        pre=None
        if self.is_empty():
            return False
        while cur.next!=self.__head:
            if cur.item==val:
                # 如果需要删除的元素是在头部，则需要再定义一个游标变量rear，循环至尾部，然后让head指向下一个元素，让
                if cur==self.__head:
                    rear=self.__head
                    while rear.next!=self.__head:
                        rear=rear.next
                    # 由于头部节点已经删除，需要将head向后移动一位，并将尾部（rear）指向新的头部
                    self.__head=cur.next
                    rear.next=self.__head
                else:
                    pre.next=cur.next
                return True
            else:
                pre=cur
                cur=cur.next

        # 跳出循环后，cur位于链表尾部，开始比较尾部是否为要删除数据
        if cur.item==val:
            # 判断链表是否只有一个元素，即cur==__head
            if cur==self.__head:
                self.__head=None
            else:
                pre.next=cur.next
            return True
        # 没有找到元素，返回False
        return False