单向循环链表|双向循环链表

单向循环链表

#定义节点
class Node(object):
    def __init__(self,elem,next_=None):
        self.elem=elem
        self.next=next_
class CircleLinklist(object):
    def __init__(self,node=None):
        self.head=node
    def is_empty(self):
        return self.head is None
    def length(self):
        if self.is_empty():
            return 0
        cur=self.head
        count = 0
        while cur.next!=self.head:
            count+=1
            cur=cur.next
        return count+1
    def travel(self):
        if self.is_empty():
            print('')
            return
        cur=self.head
        while cur.next!=self.head:
            print(cur.elem,end=' ')
            cur=cur.next
        #退出循环时指向了尾节点，没有输出
        print(cur.elem)
    def add(self,item):
        node =Node(item)
        if self.is_empty():
            #如果为空链表
            node.next=node
            self.head=node
        else:
            cur=self.head
            while cur.next!=self.head:
                cur=cur.next
            node.next=self.head
            self.head=node
            cur.next=node
    def append(self,item):
        node =Node(item)
        if self.is_empty():
            # 如果为空链表
            node.next = node
            self.head = node
        else:
            cur = self.head
            while cur.next != self.head:
                cur = cur.next
            node.next=self.head
            cur.next=node
            #比上方少了一个self.head=node 因为循环可以把任意一个节点当首部
    def insert(self,pos,item):

        if pos<=0:
            self.add(item)
        elif pos>=self.length():
            self.append(item)
        else:
            node = Node(item)
            cur =self.head
            count=0
            while count<(pos-1):
                cur=cur.next
            node.next=cur.next
            cur.next=node
    def remove(self,item):
        if self.is_empty():
            return
        cur=self.head
        pre=None
        while cur.next != self.head:
            # 找到了元素
            if cur.elem == item:
                if cur == self.head:
                    #在头部找到节点
                    rel = self.head
                    while rel.next != self.head:
                        #找到最后一个节点
                        rel = rel.next
                    #改变尾节点和头结点的指向
                    self.head = cur.next
                    rel.next = self.head
                else:
                    #不是头部节点
                    pre.next = cur.next
                return
            #pre 未当前节点的前一个
            pre = cur
            cur = cur.next
        # 退出循环后, cur指向了尾节点
        if cur.elem == item:
            if pre:
                pre.next = self.head
            else:
                # 链表只有一个节点
                self.head = None
    def search(self,item):
        cur=self.head
        while cur.next!=self.head:
            if cur.elem==item:
                return True
            cur=cur.next
        # 退出循环后, cur指向了尾节点
        if cur.elem == item:
            return True
        return False

if __name__ == '__main__':
    ll = CircleLinklist()
    for i in range(10):
        ll.append(i)
    print(ll.length())
    ll.travel()
    ll.remove(4)
    ll.travel()
    ll.add(90)
    ll.travel()
    print(ll.is_empty())
    print(ll.search(9))
    print(ll.length())

双向循环链表

class Node(object):
    def __init__(self,item):
        self.elem=item
        self.next=None
        self.prev=None
class DoubleCirclLin(object):
    def __init__(self):
        self.head=None
    def is_empty(self):
        return self.head==None
    def length(self):
        if self.is_empty():
            return 0
        cur=self.head
        count=0
        while cur.next is not self.head:
            count+=1
            cur=cur.next
        return count+1
    def travel(self):
        if self.is_empty():
            return
        cur =self.head
        while cur.next is not self.head:
            print(cur.elem,end=' ')
            cur =cur.next
        # 退出循环时指向了尾节点，没有输出
        print(cur.elem)
    def add(self,item):
        node =Node(item)
        if self.is_empty():
            self.head=node
            node.next=node
            node.prev=node
        else:
            node.next=self.head
            node.prev=self.head.prev
            self.head.prev.next=node
            self.head.prev=node
            self.head=node
    def append(self,item):
        node=Node(item)
        if self.is_empty():
            self.add(item)
        else:
            node.next=self.head
            node.prev=self.head.prev
            self.head.prev.next=node
            self.head.prev=node
    def insert(self,pos,item):
        if pos<=0:
            self.add(item)
        elif pos>=(self.length()-1):
            self.append(item)
        else:
            count=0
            cur=self.head
            while count<pos-1:
                count+=1
                cur=cur.next
            node=Node(item)
            node.next=cur.next
            node.prev=cur
            cur.next.prev=node
            cur.next=node
    def remove(self,item):
        if self.is_empty():
            return
        else:
            cur=self.head
            # 如果头结点就是 要删除的元素
            if cur.elem==item:
                # 如果只有一个节点 链表就空了 head设为None
                if self.length()==1:
                    self.head=None
                else:
                    self.head=cur.next
                    cur.next.prev=cur.prev
                    cur.prev.next=cur.next
            # 否则 头节点不是要删除的节点 我们要向下遍历
            else:
                cur=cur.next
                while cur is not self.head:
                    if cur.elem==item:
                        cur.prev.next = cur.next  # cur的前驱的后继改为cur的后继
                        cur.next.prev = cur.prev  # cur的后继的前驱改为cur的前驱
                    cur=cur.next
    def search(self,item):
        if self.is_empty():
            return False
        cur=self.head
        while cur.next is not self.head:
            if cur.elem==item:
                return True
            cur=cur.next
        if cur.elem==item:
            return True
        return False

if __name__=='__main__':
    print(123)
    dcl=DoubleCirclLin()
    for i in range(10):
        dcl.append(i)
    print(dcl.length())
    dcl.travel()
    dcl.add(89)
    dcl.travel()
    dcl.remove(9)
    dcl.travel()
    print(dcl.search(8))