python单向循环链表实例详解

使用python实现单向循环链表，供大家参考，具体内容如下

单向循环链表

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

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

单向链表操作

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

Python客栈送红bao、纸质书

代码实现
`# 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`

更多相关文章

随机推荐