Python实现-无头单向非循环链表
无头单向非循环链表链表
无头单向非循环链表结构简单，一般不会单独用来存数据。实际中更多是作为其他数据结构的子结构，如哈希桶、图的邻接表等等
无头单向非循环链表
对于任意一个数据元素a(i)来说，储存本身的数据.（这个域叫数据域） 存储一个下一个（后继）数据元素的信息（Next）（这个域叫指针域） Python实现
class Node:
def __init__(self, data):
"""
初始化链表：data相当于链表的数据域，next相当于链表的指针
:param data:存储数据本身
"""
self.data = data
self.next = None
return
def exist_value(self, value):
"""
查询数据是不是当前结点的数据
:param value:
:return:
"""
if self.data == value:
return True
else:
return False
class SingleList:
def __init__(self):
"""
初始化单链表
head：头结点
tail：尾结点
"""
self.head = None
self.tail = None
return
def add_list_item(self, item):
"""
添加结点
1.如果是空表,则头尾结点都为item,返回
2.如果非空表,item赋值当前的尾结点的下一个值,尾结点更新为新增的值
比如：当前表为空,添加1,则头尾结点都是1,然后再添加2，头结点还是1,1.next=2（尾结点1的下一个值为2）,tail=2（最后尾结点更新为2）；
添加3，1.next=2,2.next=3(尾结点2的下一个值为3),tail=3（最后尾结点更新为3）以此类推...
:param item: 添加结点的值
:return:
"""
#如果不是Node，构建为Node
if not isinstance(item, Node):
item = Node(item)
if self.head is None:
self.head = item
else:
self.tail.next = item
self.tail = item
return
def search_by_id(self, search_id):
"""
按序号查找并返回值
1.假设表长为length>0 并且search_id从头结点开始遍历，如果当前结点序号如果当前结点序号=需要查找的序号，证明找到了当前结点值并返回
2.如果是空表或者search_id>length，返回None
:param search_id: 需要查找的序号
:return:
"""
current_id = 1
current_node = self.head
while (current_id 如能查询成功则返回结果
-->如果查询的值不在表中，则返回空
:param value:要查询的值
:return: results
"""
current_node = self.head #头结点
node_id = 1 #第一个结点的位置
results = [] #返回结果列表
while current_node is not None:
if current_node.exist_value(value):
results.append(node_id)
current_node = current_node.next
node_id = node_id + 1
return results
def remove_by_id(self, value_id):
"""
删除特定序号的结点
1.空表，返回None
2.非空表
-->只有一个节点，则将头结点的下一个值None赋值给头结点，现在是空表了
-->多个节点，如果没有找到对应要删除的序号，当前结点变成上一个结点，下一个结点变成当前结点，当前序号+1，继续循环遍历直到current_id == value_id
—->因为当前结点被删除，将上一个结点指向当前结点的下一个即可
:param value_id:需要删除的序号
:return:
"""
current_id = 1
current_node = self.head
previous_node = None
while current_node is not None:
if current_id == value_id:
if previous_node is not None:
previous_node.next = current_node.next
else:
self.head = current_node.next
return
return
previous_node = current_node
current_node = current_node.next
current_id = current_id + 1
return
def insert_value(self, insert_id, value):
"""
插入数据到指定位置结点之后
1.链表为空、只有一个结点或者需要插入的位置>=表长，则新增数据至链表即可
2.循环链表找到需要插入的结点位置，插入数据
:value: 需要插入链表的值
:insert_id: 需要插入的位置
:return:
"""
if not isinstance(value, Node):
value = Node(value)
length = self.list_length()
if length = length:
self.add_list_item(value)
else:
current_id = 1
current_node = self.head
while current_id < insert_id:
current_node = current_node.next
current_id += 1
#首先value的next指针指向当前结点的下一个结点，然后将当前结点的next指针指向value
#下面两句一定不能调换（可以尝试调换以后会发生什么）
value.next = current_node.next
current_node.next = value
def list_length(self):
"""
1.如果表空，返回表长0
2.如果表不为空，则从表头开始遍历，每遍历一次表长加1，并且将下个结点赋值给当前结点，当下个结点为None，返回表长
"""
count = 0
current_node = self.head
while current_node is not None:
count = count + 1
current_node = current_node.next
return count
def print_value(self):
"""
循环打印链表中的每个值
:return:
"""
current_node = self.head
while current_node is not None:
print(current_node.data)
current_node = current_node.next
return None
if __name__ == '__main__':
node1 = Node(1)
node2 = Node(2)
node3 = Node(3)
node4 = Node(4)
single = SingleList()
for node in [node1, node2, node3, node4]:
single.add_list_item(node)
print(single.list_length())
print(single.search_by_id(1))
print(single.search_by_id(2))
print(single.search_by_id(3))
print(single.search_by_id(4))
print(single.search_by_id(100))
print(single.search_by_value(5))
single.remove_by_id(1)
print(single.search_by_id(1))
print(single.search_by_id(2))
print(single.search_by_id(3))
print(single.search_by_id(4))
参考：https://www.jianshu.com/p/af7fce25a54b
作者：LeechengLove
