Usage:
L = SingLin()
L.insert('fred')
L.insert('bellatrix')
L.insert('george')
print (L.toList())['bellatrix', 'george', 'fred']
element = L.getFirst()
while element:
print (element)
element = L.getNext()bellatrix
fred
george
class Node:
def __init__(self, data):
self.data = data
self.next = None
def value(self):
return self.data
def toString(self,withLink=False):
'''if withLink == True, returns string as "current_value->next_value"'''
if withLink:
if self.next:
return '%s->%s' % (self.toString(),self.next.toString())
else:
return '%s->None' % self.toString()
return str(self.data)
def __str__(self):
return str(self.data)
class SingLin:
def __init__(self):
self.first = None
self.size = 0
self.current = None
def insert(self,data):
'''inserts a new node containing data'''
anode = Node(data)
if self.size == 0:
self.first = anode
elif data < self.first.value():
anode.next = self.first
self.first = anode
else:
insert_after = self.first
insert_before = insert_after.next
while insert_before and data >= insert_before.value():
insert_after = insert_before
insert_before = insert_before.next
anode.next = insert_after.next
insert_after.next = anode
self.size += 1
def has(self,data):
'''returns True if a node containing data is found'''
if self.size == 0:
return False
trial = self.first
while trial and trial.value() < data:
trial = trial.next
if trial and trial.value() == data:
return True
return False
def delete(self,data):
'''deletes the first node that contains the given data and returns True, else False if not found'''
trial = self.first
trial_before = None
while trial and trial.value() < data:
trial_before = trial
trial = trial.next
if trial and trial.value() == data:
if trial == self.first:
self.first = trial.next
else:
trial_before.next = trial.next
del trial
self.size -= 1
return True
return False
def getFirst(self):
'''returns the data in the first node, or None'''
if self.size == 0:
return None
else:
self.current = self.first
return self.current.value()
def getNext(self):
'''returns the data in the node after current, updating current, else None'''
if not self.current or not self.current.next:
self.current = None
return None
self.current = self.current.next
return self.current.value()
def getSize(self):
'''returns number of elements in the list'''
return self.size
def toList(self):
'''returns a list of node values'''
lout = []
trial = self.first
while trial:
lout.append(trial.value())
trial = trial.next
return lout
# Test to see if this Singly-linkned ordered list actually delivers ordered lists
from random import randint
linked_list = SingLin()
just_list = []
for i in range(10):
num = randint(1,100)
linked_list.insert(num)
just_list.append(num)
print(linked_list.toList())
if sorted(just_list) == linked_list.toList():
print('Passed')
else:
print('Failed')