Python实现单向循环链表

单向循环链表

将所有的链接在一起，每一个节点分为数据存储区和链接区，数据区存储数据，链接区链接下一个节点

item： 存储数据的地方
next： 链接下一个节点
注意： 单向循环链表是首位链接，即尾部的节点要和头部的节点链接

单向链表操作

1、链表是否为空
2、链表的长度
3、遍历链表
4、链表头部添加元素
5、链表尾部添加元素
6、链表指定位置添加元素
7、链表删除节点
8、查找节点是否存在

代码实现

# Functions  函数声明
class Node():
    """实例化节点类"""
    def __init__(self, item):
        self.item = item
        self.next = None

class Linklist():
    """
    存放节点类
    """
    def __init__(self):
        self.head = None

    # 1. 链表是否为空
    def is_empty(self):
        return self.head == None

    # 2. 链表的长度
    def length(self):
        """
        返回链表的长度
        遍历所有的节点，使用计数器计数
        1、链表为空情况
        """
        # 实例化节点
        cur = self.head
        if self.is_empty():
            return 0
        else:
            # 计数
            count = 1
            # 遍历链表
            while cur.next != self.head:
                count+=1
                cur = cur.next
            return count

    # 3. 遍历链表
    def travel(self):
        """
        遍历链表，获取所有的数据
        实例游标，遍历数据，输出数据
        1、 空链表情况
        2、 只有头部节点情况
        3、 只有尾部节点情况
        """
        # 实例化游标
        cur = self.head
        if self.is_empty():
            return None
        else:
            # 遍历数据
            while cur.next != self.head:
                print(cur.item, end=' ')
                cur = cur.next
            # 最后一个节点要单独输出
            print(cur.item)

    # 4. 链表头部添加元素
    def add(self, item):
        """
        往链表头部添加数据
        分析
        链表为空
            self.head 直接指向node， 再讲node指向自己
        链表不为空
            node.next = self.head
        """
        # 实例化游标
        cur = self.head
        # 实例化节点
        node = Node(item)
        # 判断是否为空
        if self.is_empty():
            self.head = node
            node.next = node
        else:
            # 不为空的情况
            # 要将最后一个节点指向node
            while cur.next != self.head:
                cur = cur.next
            node.next = self.head
            self.head = node
            cur.next = node

    # 5. 链表尾部添加元素
    def append(self, item):
        """
        往尾部添加数据
        分析
        实例化节点，再实例化游标先指向最后一个节点
        调换指向
        1、空链表情况
        2、只有一个链表情况

        """
        # 实例化节点
        node = Node(item)
        # 实例化游标
        cur = self.head
        # 判断是否为空
        if self.is_empty():
            self.add(item)
        else:
            # 不为空的情况,移动游标指向最后一个节点
            while cur.next != self.head:
                cur = cur.next
            node.next = self.head
            cur.next = node
            pass

    # 6. 链表指定位置添加元素
    def insert(self, index, item):
        """
        指定位置添加数据
        实例化节点， 实例化游标指向索引的数据，更改指向
        位置大小
        链表是否为空

        """
        # 实例化节点
        node = Node(item)
        # 实例化游标
        cur = self.head
        if index <=0:
            self.add(item)
        elif index > (self.length()-1):
            self.append(item)
        else:
            # 判断链表是否为空
            if self.is_empty():
                self.add(item)
            else:
                # 移动游标，指向指定的索引位置
                count = 0
                while count < index-1:
                    count+=1
                    cur = cur.next
                node.next = cur.next
                cur.next = node
            pass

    # 7. 链表删除节点
    def remove(self, item):
        """
        删除指定的节点
        实例化游标，遍历链表插件这个节点是否存在，存在则更改指向
        不存在，则不修改
        空链表情况
        头节点情况
        尾结点情况
        """
        # 实例化游标
        cur = self.head
        if self.is_empty():
            return None
        else:
            # 不为空，遍历链表，对比数据是否相等
            # 如果头节点是要删除的数据
            if cur.item == item:
                self.head=cur.next
                # 找出最后的节点，将最后的节点指向，删除后面的那个节点
                while cur.next != self.head:
                    cur = cur.next
                cur.next = cur.next
            else:
                pro = None
                while cur.next != self.head:
                    if cur.item == item:
                        if cur.item == item:
                            pro.next = cur.next
                            return True
                    else:
                        pro = cur
                        cur = cur.next
                if cur.item == item:
                    pro.next = self.head
            pass

    # 8. 查找节点是否存在
    def search(self, item):
        """
        查找该节点是否存在
        实例化游标，遍历所有的节点
        查看当前节点的数据是否和item 相等
        空链表
        头节点
        尾结点
        """
        # 实例化游标
        cur = self.head
        # 判断空链表
        if self.is_empty():
            return None
        else:
            # 不为空遍历整个链表
            if cur.item == item:
                return True
            else:
                while cur.next != self.head:
                    if cur.item == item:
                        return True
                    else:
                        cur = cur.next
                if cur.item == item:
                    return True
            pass

测试运行

# 程序的入口
if __name__ == "__main__":
    a = Linklist()
    a.add(400)
    a.add(300)
    a.add(200)
    a.add(100)
    # a.append(10)
    a.insert(4,6)
    # a.remove(6)
    print(a.length())  # 5
    a.travel()         # 100 200 300 400 6
    print(a.search(100)) # True
    pass