单向链表结构
链表由一连串的节点组成,单向链表中节点包含一个用来存储下一个节点引用的成员,如图所示:
因为单向链表只有一个指针/引用成员,所以操作起来不是很方便,很多地方都需要从头节点开始遍历。
实现代码完整代码如下:
class Node:
''' 节点的结构体 '''
def __init__(self,value=None):
self.value=value
self.next=None
class SingleLinkedList:
''' 单链表类 '''
def __init__(self):
self.__head=None
def isEmpty(self):
''' 判空 '''
return self.__head==None
def __len__(self):
''' Node个数 '''
count=0
cursor=self.__head
while cursor!=None:
count+=1
cursor=cursor.next
return count
def __str__(self):
''' 输出元素列表 '''
value_list=[]
cursor=self.__head
while cursor!=None:
value_list.append(cursor.value)
cursor=cursor.next
return str(value_list)
def pushBack(self,value):
''' 尾部添加一个节点 '''
new_node=Node(value)
if self.isEmpty():
self.__head=new_node
else:
cursor=self.__head
while cursor.next!=None:
cursor=cursor.next
cursor.next=new_node
def popBack(self):
''' 尾部删除一个节点 '''
pop_node=None
#三种情况,无节点,单个节点,多个节点
if self.__head==None:
pass
elif self.__head.next==None:
pop_node=self.__head
self.__head=None
else:
cursor=self.__head
pop_node=self.__head.next
while pop_node.next!=None:
cursor=cursor.next
pop_node=cursor.next
cursor.next=None
if pop_node!=None:
return pop_node.value
return None
def pushFront(self,value):
''' 从头部插入节点 '''
new_node=Node(value)
new_node.next=self.__head
self.__head=new_node
def popFront(self):
''' 从头部删除节点 '''
pop_node=self.__head
if self.__head!=None:
self.__head=self.__head.next
if pop_node!=None:
return pop_node.value
return None
def find(self,value):
''' 查找某个值第一次出现的pos '''
find_pos=None
count=0
cursor=self.__head
while cursor!=None:
if cursor.value==value:
find_pos=count
break
count+=1
cursor=cursor.next
return find_pos
def insert(self,pos,value):
''' 任意位置插入 '''
# 对于无效的位置,可以抛出异常,或者用布尔返回值
length=len(self)
if pos>=0 and pos
关注
打赏
最近更新
- 深拷贝和浅拷贝的区别(重点)
- 【Vue】走进Vue框架世界
- 【云服务器】项目部署—搭建网站—vue电商后台管理系统
- 【React介绍】 一文带你深入React
- 【React】React组件实例的三大属性之state,props,refs(你学废了吗)
- 【脚手架VueCLI】从零开始,创建一个VUE项目
- 【React】深入理解React组件生命周期----图文详解(含代码)
- 【React】DOM的Diffing算法是什么?以及DOM中key的作用----经典面试题
- 【React】1_使用React脚手架创建项目步骤--------详解(含项目结构说明)
- 【React】2_如何使用react脚手架写一个简单的页面?