Python写数据结构:单向循环链表

痛定思痛。 2022-05-31 00:45 205阅读 0赞

注：带头结点

#!/usr/bin/python3.5
    # _*_coding:utf-8_*_
    
    
    class Node:
        def __init__(self, value):
            self.data = value
            self.next = None
    
    
    class CycleList:
        def __init__(self):
            self._head = Node(None)
            self._head.next = self._head
            self.rear = self._head
    
        def insert(self, index, value):
            n = Node(value)
            cur = self._head
            for i in range(index - 1):
                cur = cur.next
            n.next = cur.next
            cur.next = n
            if n.next == self._head:
                self.rear = n
    
        def remove(self, index):
            if index <= 0 or index > self.length():
                print('删除位置有误')
                return
            cur = self._head
            for i in range(index - 1):
                cur = cur.next
                if cur == None:
                    print('删除位置有误')
                    return
            n = cur.next
            cur.next = cur.next.next
            del n
            if cur.next == self._head:
                self.rear = cur
    
        def empty(self):
            return self._head.next == self._head
    
        def search(self, value):
            cur = self._head.next
            index = 1
            while cur != self._head and cur.data != value:
                cur = cur.next
                index += 1
            if cur == self._head:
                print('没有该元素')
                return
            print("index:%d,value:%d" % (index, value))
    
        def clear(self):
            cur = self._head.next
            while cur != self._head:
                n = cur
                cur = cur.next
                del n
            self._head.next = self._head
            self.rear = self._head
    
        def length(self):
            count = 0
            cur = self._head.next
            while cur != self._head:
                count += 1
                cur = cur.next
            return count
    
        def travel(self):
            if self.empty():
                print('空')
                return
            cur = self._head
            while cur.next != self._head:
                cur = cur.next
                print(cur.data)
    
        def appendhead(self, value):
            n = Node(value)
            if self.empty():
                self.rear = n
            n.next = self._head.next
            self._head.next = n
    
        def appendrear(self, value):
            n = Node(value)
            n.next = self.rear.next
            self.rear.next = n
            self.rear = n
    
    
    if __name__ == '__main__':
        link = CycleList()