单向循环链表

Mangena ·

更新时间:2024-11-14

· 810 次阅读

循环链表

循环链表是一种特殊的单链表。实际上，循环链表也很简单。它跟单链表唯一的区别就在尾结点。我们知道，单链表的尾结点指针指向空地址，表示这就是最后的结点了。而循环链表的尾结点指针是指向链表的头结点。从我画的循环链表图中，你应该可以看出来，它像一个环一样首尾相连，所以叫作“循环”链表。
在这里插入图片描述

操作

is_empty() 判断链表是否为空
length() 返回链表的长度
travel() 遍历
add(item) 在头部添加一个节点
append(item) 在尾部添加一个节点
insert(pos, item) 在指定位置pos添加节点
remove(item) 删除一个节点
search(item) 查找节点是否存在

代码实现 结点

class Node(object):
    """节点"""
    def __init__(self, item):
        # item存放数据元素
        self.item = item
        # next是下一个节点的标识
        self.next = None

创建单向循环链表类

class SinCycLinkList(object):
    """单项循环链表"""
    # 空的单链表   self.__head = None
    # 非空的单链表 node.next = node
    def __init__(self, node=None):
        self.__head = None
        if node:
            node.next = node

is_empty

def is_empty(self):
	"""判断链表是否为空"""
	if self.__head == None:
		return True
	else:
		return False

length

def length(self):
	"""返回链表的长度"""
	# 空链表的情况下
	if self.is_empty():
		return 0
	# cur游标 指向首节点 用来遍历
	cur = self.__head  # None
	# is 对象   == 数值是否相等
	count = 1
	while cur.next != self.__head:
		count += 1
		# 将游标后移动一位
		cur = cur.next
	return count

travel

def travel(self):
	"""遍历"""
	# 空链表
	if self.is_empty():
		return None
	cur = self.__head
	while cur.next != self.__head:
		# 结点中的数据
		print(cur.item, end=' ')
		cur = cur.next
	# 退出循环的时候,cur指向尾结点,但是尾结点并没有打印
	print(cur.item)

add

在这里插入图片描述

def add(self, item):
    """链表头部添加元素"""
    # item 你要具体插入的数据
    node = Node(item)
    # 空链表
    if self.is_empty():
        self.__head = node
        node.next = self.__head
    else:
        cur = self.__head  # None
        while cur.next != self.__head:
            cur = cur.next
        # 找到尾节点
        # 添加的节点指向原先的头节点
        node.next = self.__head
        # __head指向node
        self.__head = node
        # 尾结点指向新的节点
        cur.next = node

append

在这里插入图片描述

def append(self, item):
    """链表尾部添加元素"""
    node = Node(item)
    # 空链表
    if self.is_empty():
        self.__head = node
        node.next = self.__head
    else:
        cur = self.__head
        while cur.next != self.__head:
            cur = cur.next
        # 找到尾节点
        # 将尾结点指向node
        cur.next = node
        # 将node指向__head
        node.next = self.__head

insert

在这里插入图片描述

def insert(self, pos, item):
    """指定位置添加元素"""
    # 头部插入
    if pos  self.length() - 1:
        self.append(item)
    else:
        # 指定位置插入
        node = Node(item)
        cur = self.__head
        count = 0
        while count < (pos - 1):
            count += 1
            cur = cur.next
        node.next = cur.next
        cur.next = node

remove

在这里插入图片描述

def remove(self, item):
    """删除节点"""
    # 空链表
    if self.is_empty():
        return
    cur = self.__head
    pre = None
    # 头节点的元素就是要删除的元素
    if cur.item == item:
        # 链表中的节点不止一个
        if cur.next != self.__head:
            while cur.next != self.__head:
                cur = cur.next
            # 循环结束 cur 指向尾结点
            cur.next = self.__head.next
            self.__head = cur.next
        else:
            self.__head = None
    # 第一个节点不是要删除的
    else:
        while cur.next != self.__head:
            if cur.item == item:
                # 删除
                pre.next = cur.next
                return
            else:
                # 游标继续往下走
                pre = cur
                cur = cur.next
        if cur.item == item:
            pre.next = cur.next

search

def search(self, item):
    """查找节点是否存在"""
    if self.is_empty():
        return False
    cur = self.__head
    while cur.next != self.__head:
        if cur.item == item:
            return True
        else:
            # 让游标继续执行
            cur = cur.next
    # 循环退出 cur指向尾节点
    if cur.item == item:
        return True
    return False

作者：夕麻

循环循环链表链表

1024 个赞