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)