02_单向循环链表[Python]

1. 简介

单链表的一个变形是单向循环链表，链表中最后一个节点的下一个域不再为无，而是指向链表的头节点。

单向循环链表

2. 操作

• is_empty（）判断链表是否为空

• length（）返回链表的长度
• travel（）遍历
• add（elem）在头部添加一个节点
• append（elem）在尾部添加一个节点
• insert（pos，elem）在指定位置pos添加节点
• remove（elem）删除一个节点
• search（elem）查找节点是否存在

3. 与单向链表的区别

• while循环遍历时，终止的条件
  单向：cur !=None
  单向循环：cur.next != self.head
  划重点: 单向循环链表中的这种遍历方式，最后一个节点是没有被算进来的，在travel（）、add（elem）、
  append（elem）等方法中都有体现
• 在进行增删操作时，要多考虑一步，如果节点在末尾时，需要特殊处理

4. 实现

• 没有区别的部分

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

class SingCycLinkList(object):
    def __init__(self):
        self.head=None

    def is_empty(self):
        return self.head==None

• 返回链表长度

def length(self):
        """返回链表的长度"""
        # 如果链表为空，返回长度0
        if self.is_empty():
            return 0
        count = 1
        cur = self._head
        while cur.next != self._head:
            count += 1
            cur = cur.next
        return count

• 遍历链表

    def travel(self):
        """遍历链表"""
        if self.is_empty():
            return
        cur = self._head
        print cur.item,
        while cur.next != self._head:
            cur = cur.next
            print cur.item,
        print ""

• 三种添加元素

 def add(self,elem):
        node = Node(elem)
        if self.is_empty():
            self.head=node
            node.next=self.head
            # node.next=node
        else:
            node.next=self.head

            #移动到链表的尾部，将尾部的next指针指向node
            cur=self.head
            while cur.next != self.head:
                cur=cur.next
            cur.next=node
            self.head=node

    def append(self,elem):
        node=Node(elem)
        if self.is_empty():
            self.add(elem)
            node.next=self.head
        else:
            #找到末尾节点
            cur=self.head
            while cur.next!= self.head:
                cur=cur.next
            cur.next=node
            node.next=self.head

    def insert(self,pos,elem):
        if pos<=0:
            self.add(elem)
        elif pos > (self.length()-1):
            self.append(elem)
        else:
            node =Node(elem)
            cur = self.head
            count=0
            while count<(pos-1):
                count += 1
                cur=cur.next

            node.next = cur.next
            cur.next=node

• 删除元素

    def remove(self,elem):
        if self.is_empty():
            return

        cur=self.head
        pre = None
        #如果是头结点
        if cur.elem==elem:
            #如果不止一个节点
            if cur.next!=self.head:
                # 要考虑尾结点
                while cur.next!=self.head:
                    cur=cur.next
                cur.next=self.head.next
                self.head=self.head.next
            else:
                self.head=None
        else:
            pre=self.head
            while cur.next!=self.head:
                if cur.elem==elem:
                    pre.next=cur.next
                    return
                else:
                    pre=cur
                    cur=cur.next
            #如果是尾指针
            if cur.elem==elem:
                pre.next=self.head

• 搜索元素

    def search(self,elem):
        if self.is_empty():
            return False
        else:
            cur= self.head
            while cur.next!=self.head:
                if cur.elem==elem:
                    return True
                else:
                    cur=cur.next
            #循环结束，尾部的节点没有判断
            if cur.elem==elem:
                return True
            else:
                return False

4. 测试

if __name__=="__main__":
    ll=SingCycLinkList()
    ll.add(2)
    ll.add(1)
    ll.append(4)
    ll.insert(2,3)
    ll.insert(4,5)
    ll.insert(0,0)
    ll.travel()
    print(ll.search(3))
    print("ll is empty: %s" %(ll.is_empty()))
    print("The length of ll is %d" %(ll.length()))
    ll.remove(2)
    ll.travel()
    print("ll is empty: %s" % (ll.is_empty()))
    print("The length of ll is %d" % (ll.length()))