I want to create a function that inserts a node into any place in a linked list. There is a test function to test if the function works. My problem is that when I run the test function none of the outputs show, any ideas?
"""
Creates and returns a linked list containing all of the elements
of the Python-style list parameter.
"""
def createList(plist):
myList = None
# goes backwards, adding each element to the beginning
# of the list.
for index in range(len(plist)-1, -1, -1):
myList = insertValueHead(myList, plist[index])
return myList
'''
Creates a string representation of the values in the linked list such as:
5->6->9->14.
'''
def listString(myList):
ptr = myList
str1 = ''
while ptr != None:
str1 += str(ptr['data'])
ptr = ptr['next']
if ptr != None:
str1 += "->"
str1 = str1
return str1
'''
Inserts a new node containing the value "value" to the head of the list.
LinkedList is the head of the list to be added to
Value is the data to be stored in the node'''
def insertValueHead(myList, value):
newnode = {}
newnode["data"] = value
#set the next pointer of this new node to the head of the list, linkedList
#newnode is now the head of the list
newnode["next"] = myList
return newnode
def insertNode(myList, index, value):
if index == 0:
newnode = {}
newnode["data"] = value
newnode["next"] = myList
elif index > 0:
newnode = {}
newnode["data"] = value
ptr = myList
count = 0
while ptr != None and count < index-1:
ptr = ptr['next']
print count
count += 1
return ptr
newnode['next'] = ptr['next']
ptr['next'] = newnode
def testInsert():
#test code to ensure that insertNode is working correctly.
myList = createList([1, 2, 3, 4, 5, 6])
print "The initial list", listString(myList)
#insert 0 at the head
myList = insertNode(myList,0, 0)
print "Inserted 0 at the start of list: ", listString(myList)
#insert 7 at the end
myList = insertNode(myList, 7, 7)
print "Inserted 7 at the end of list: ", listString(myList)
myList= insertNode(myList, 3, 2.2)
print "Inserted 2.2 in the 3rd position: ", listString(myList)
myList = insertNode(myList, 26, 12) #should generate an error
testInsert()
Your insertNode()
function never returns newnode
when inserting at index 0. As such, None
is returned instead.
Since that's the first operation that the testInsert()
function does after building the initial linked list, myList
in that function is now None
and the rest of the test is invalid.
For the index > 0
case, your return
statement comes too early; you return ptr
, e.g. the node at index - 1
before inserting the new value. All statements after that return
statement are not executed.
You don't need to special-case the index = 0
case, really. Here is a better version:
def insertNode(myList, index, value):
newnode = {'data': value, 'next': None}
retval = myList if index else newnode
prev, ptr = None, myList
while ptr is not None and index > 0:
prev, ptr = ptr, ptr['next']
index -= 1
if index > 0:
raise ValueError('Index out of range')
newnode['next'] = ptr
if prev is not None:
prev['next'] = newnode
return retval
This version actually raises an error if you try to insert a value past the end; index
will be greater than 0 in that case.
Collected from the Internet
Please contact [email protected] to delete if infringement.
Comments