Python 实现单向循环链表

循环链表的概念

1.什么是循环链表

  所谓的循环链表就是让单向链表的首尾相连,组成一个环状。

2.循环链表的典型应用

  约瑟夫环问题。

3.实现循环链表的重点

  1,循环链表在插入第一个元素的时候,需要我们将第一元素的指针域指向其自身,也就构成了循环链表。

  2,循环链表基于单向链表而生,单是比循环链表多了游标这个概念。要想实现循环链表的插入,删除的关键是考虑头结点问题,因为在头插法方式(往链表的头部插入数据)中,需要将末尾数据元素的指针域指向新插入的节点。将新插入的节点的指针域指向头结点的指针域的指针域,还需要将头结点指向新插入的结点。(插入相同)。

#!usr/bin/env python  
# -*- coding:utf-8 -*-

""" 
@author:yzk13 
@time: 2018/04/17

单向循环链表
"""


class Node(object):
    """
    节点类
    """
    def __init__(self, value, next):
        self.value = value
        self.next = next

class SinCycLinkedList(object):
    def __init__(self):
        self.root = None

    def is_empty(self):
        """
        判断链表是否为空
        :return:
        """
        return self.root == None

    @property
    def length(self):
        """
        求链表长度
        :return:
        """
        if self.is_empty():
            return 0
        else:
            counter = 1
            cursor = self.root
            while cursor.next != self.root:
                counter += 1
                cursor = cursor.next
            return counter

    def print(self):
        """
        打印链表
        :return:
        """
        if self.is_empty():
            print('Nothing')
        else:
            cursor = self.root
            print('[%s' % str(cursor.value), end='')
            while cursor.next != self.root:
                cursor = cursor.next
                print(', ', cursor.value, end='')
            print(']')

    def prepend(self, value):
        """
        在表头添加Node
        :return:
        """
        node = Node(value, None)
        if self.is_empty():
            self.root = node
            node.next = self.root
        else:
            # 设置节点指向头
            node.next = self.root
            # 找到表尾
            cursor = self.root
            while cursor.next != self.root:
                cursor = cursor.next
            # 设置最后一个节点指向添加的节点
            cursor.next = node
            # 设置表头指向添加的节点
            self.root = node

    def append(self, value):
        """
        在表添加节点
        :return:
        """
        node = Node(value, None)
        if self.is_empty():
            self.root = node
            node.next = self.root
        else:
            cursor = self.root
            while cursor.next != self.root:
                cursor = cursor.next
            # 将尾节点指向新增节点
            cursor.next = node
            node.next = self.root

    def insert(self, index, value):
        """
        在指定位置添加节点
        :return:
        """
        if index < 0 or index > self.length:
            print('Index错误, 索引越界')
        elif index == 0:
            self.prepend(value)
        else:
            node = Node(value, None)
            cursor = self.root
            counter = 0
            # counter 小于索引时 继续往前搜索
            while counter < index-1:
                counter += 1
                cursor = cursor.next
            node.next = cursor.next
            cursor.next = node

    def remove(self, value):
        """
        删除某个值的所有
        :param index:
        :return:
        """
        # 若链表为空,则直接返回
        if self.is_empty():
            return
        # 将cur指向头节点
        cur = self.root
        pre = None
        # 若头节点的元素就是要查找的元素value
        if cur.value == value:
            # 如果链表不止一个节点
            if cur.next != self.root:
                # 先找到尾节点,将尾节点的next指向第二个节点
                while cur.next != self.root:
                    cur = cur.next
                # cur指向了尾节点
                cur.next = self.root.next
                self.root = self.root.next
            else:
                # 链表只有一个节点
                self.root = None
        else:
            pre = self.root
            # 第一个节点不是要删除的
            while cur.next != self.root:
                # 找到了要删除的元素
                if cur.value == value:
                    # 删除
                    pre.next = cur.next
                    return
                else:
                    pre = cur
                    cur = cur.next
            # cur 指向尾节点
            if cur.value == value:
                # 尾部删除
                pre.next = cur.next

    def search(self, value):
        """
        查找节点是否存在
        :param value:
        :return:
        """
        if self.is_empty():
            return False
        cur = self.root
        if cur.value == value:
            return True
        while cur.next != self.root:
            cur = cur.next
            if cur.value == value:
                return True
        return False

if __name__ == '__main__':
    l = SinCycLinkedList()
    l.print()

    # --------测试添加节点----------
    # 表头添加
    l.prepend(3)
    l.prepend(4)

    # 表尾添加
    l.append(5)
    l.append(1)

    l.print()

    # 在指定位置插入节点
    l.insert(0, 1)
    l.insert(3, 7)
    l.print()

    # 测试删除
    l.remove(2)
    l.print()

    # ------- 测试是否为空----------
    print('链表是否为空?: ', l.is_empty())

    # ------- 测试查询 -----------
    print('是否存在7?:', l.search(7))

    # ------- 测试长度----------
    print('链表长度为: ', l.length)

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏算法channel

程序员必知的算法和数据结构:用这种方法理解链表,更易懂

一个单链表包括一系列节点(Nodes), 每个节点包括对后继节点的引用。通常,链表最后一个节点是null,这样表明链表终止了。

1050
来自专栏趣谈编程

一文读懂Java泛型中的通配符 ?

之前不太明白泛型中通配符"?"的含义,直到我在网上发现了Jakob Jenkov的一篇文章,觉得很不错,所以翻译过来,大家也可以点击文末左下角的阅读原文看英文版...

1263
来自专栏全沾开发(huā)

数组的遍历你都会用了,那Promise版本的呢

2694
来自专栏海天一树

小朋友学C++(12):多态

(一) 先编写函数: #include <iostream> using namespace std; class Shape { protected:...

3286
来自专栏HappenLee的技术杂谈

C++雾中风景3:const用法的小结

const关键字,翻译成中文是常量,常数的意思。所以在绝大多数场合之中,const是来定义常量的,定义常量也是好的编程习惯。在C类语言之中,定义常量通常会使用宏...

1153
来自专栏互联网杂技

深入理解javascript原型和闭包(1)——一切都是对象

“一切都是对象”这句话的重点在于如何去理解“对象”这个概念。 ——当然,也不是所有的都是对象,值类型就不是对象。 首先咱们还是先看看javascript中一个常...

37016
来自专栏彭湖湾的编程世界

【数据结构】实现字典API:有序数组和无序链表

参考资料 《算法(java)》                           — — Robert Sedgewick, Kevin Wayne 《数据结...

3315
来自专栏Python攻城狮

self 应用

·cookedLevel :这是数字;0~3表示还是生的,超过3表示半生不熟,超过5表示已经烤好了,超过8表示已经烤成木炭了!我们的地瓜开始时时生的

623
来自专栏编程坑太多

js数组的拷贝赋值复制-你真的懂?

3353
来自专栏谈补锅

C语言之指针变量

  4、指向常量的常量指针:有2个const修改,既不能间接修改变量的值,也不可重新赋值新变量地址

2843

扫码关注云+社区

领取腾讯云代金券