python3实现单向链表
2019-06-08 本文已影响0人
前端艾希
python3实现单向链表
最近重学数据结构,无奈c语言已经忘得一干二净,所以干脆用python来写。
一、代码结构:
-
节点类
-
单向列表类
-
链表初始化操作
-
init 初始化链表
-
is_empty 判断链表是否为空
-
get_len 获取链表的长度
-
clear_list 清除列表
-
-
增加节点
-
append 从链表尾部添加节点
-
insert 在链表的任意位置插入节点
-
-
删除节点
-
remove 删除节点内容 为data的所有节点
-
pop 删除第i个节点并且返回节点的内容
-
查看节点
-
get_data 查看第i个节点的内容
-
-
-
二、代码详情
#-*- coding:utf-8 -*-
#Author: Bing Xu
class Node(object):
def __init__(self,data):
self.data = data
self.next = None
class Single_Linklist(object):
def __init__(self):
'''
链表初始化
'''
self.head_node = None
def is_empty(self):
'''
判断链表是否为空
:return:
'''
return self.head_node == None
def get_len(self):
'''
获取链表对象的长度
:return: 链表长度
'''
counter = 0
cur = self.head_node
while cur:
counter += 1
cur = cur.next
return counter
def clear_list(self):
'''
清除链表所有元素
:return: 空链表
'''
self.head_node = None
def append(self,data):
'''
链表尾部追加节点
:param data: 追加节点的内容
:return:
'''
node = Node(data)
if self.is_empty():
self.head_node = node
else:
cur = self.head_node
while cur.next:
cur = cur.next
cur.next = node
def insert(self,i,data):
'''
插入新的节点
:param i: 待插入的位置,0 <= i <= self.length
:param data: 待插入的节点数据
:return:
'''
node = Node(data)
length = self.get_len()
cur = self.head_node
if length >= i:
if i == 0:
self.head_node = node
node.next = cur
else:
for item in range(i-1):
cur = cur.next
temp = cur.next
cur.next = node
node.next = temp
else:
return False
def remove(self,data):
'''
删除链表内容为data的所有节点
:param data: 要删除的内容
:return:
'''
cur = self.head_node
if cur.data == data:
self.head_node = cur.next
return
else:
while cur.next:
# temp = cur
# cur = cur.next
temp,cur = cur,cur.next
if cur.data == data:
temp.next = cur.next
def pop(self,i):
'''
删除链表对象第i个节点并返回该节点内容
:param i: 要删除的节点,0 <= i < self.length
:return: 删除节点的内容
'''
length = self.get_len()
cur = self.head_node
if i == 0:
Data = cur.data
self.head_node = cur.next
return Data
elif i < length:
for j in range(i):
temp, cur = cur, cur.next
Data = cur.data
temp.next = cur.next
return Data
def reset_data(self,i,data):
'''
修改第i个节点的内容
:param i: 要修改的节点,0 <= i < self.length
:param data: 修改后的内容
:return:
'''
cur = self.head_node
if 0 <= i < self.get_len():
for j in range(i):
cur = cur.next
cur.data = data
else:
return False
def get_data(self,i):
'''
获取链表第i个的值
:param i: 0 <= i < self.length
:return: 节点的内容
'''
cur = self.head_node
if 0 <= i < self.get_len():
for j in range(i):
cur = cur.next
return cur.data
else:
return False
三、代码测试
# 链表初始化:
sin_list = Single_Linklist()
print(sin_list.get_len())
print(type(sin_list))
# 结果为:
<class '__main__.Single_Linklist'>
# 增:
for i in range(10):
sin_list.append(i)
sin_list.insert(0,'insert')
print(sin_list.get_len())
for j in range(sin_list.get_len()): #遍历打印
print(sin_list.get_data(j),end=',')
# 结果:
insert,0,1,2,3,4,5,6,7,8,9,
# 删
for i in range(10):
sin_list.append(i)
sin_list.remove(0)
sin_list.pop(sin_list.get_len()-1)
for j in range(sin_list.get_len()): #遍历打印
print(sin_list.get_data(j),end=',')
结果:
1,2,3,4,5,6,7,8,
# 改
for i in range(10):
sin_list.append(i)
sin_list.reset_data(0,'修改')
sin_list.reset_data(9,'完成')
for j in range(sin_list.get_len()): #遍历打印
print(sin_list.get_data(j),end=',')
结果:
修改,1,2,3,4,5,6,7,8,完成,