I'm currently trying to create a function that will switch the nodes at index with the head of the list. So if my list (list) has the values [1, 7, 9, 12] and I call switch(list, 2), my result will be [9, 7, 1, 12]. This is the code I have so far:
"""
Creates and returns a linked list containing all of the elements
of the Python-style list parameter. A useful shortcut for testing.
"""
def createList(plist):
linkedList = None
# goes backwards, adding each element to the beginning
# of the list.
for index in range(len(plist)-1, -1, -1):
linkedList = insertValueHead(linkedList, plist[index])
return linkedList
'''
Create an empty linked list
'''
def emptyList():
return None #absence of a value -- nothing
'''
Creates a string representation of the values in the linked list such as:
5->6->9->14.
'''
def listString(linkedList):
ptr = linkedList
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(linkedList, 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"] = linkedList
return newnode
"""
Helper method: returns a reference to node n in a list counting from zero).
Parameters: the list and an index n
If there is no node n, returns None.
"""
def nthNode(linkedList, n):
ptr = linkedList
count = 0
if n < 0:
return None
while ptr != None and count < n:
ptr = ptr['next']
count += 1
return ptr
def switch(j, index):
head = j
currentItem = j # The head again
prevItem = None # The item that links to tempItem
for x in range(index): # Find the item to swap
prevItem = currentItem
currentItem = currentItem['next']
# Now we swap. We're rotating three items' .next values, so we can't
# do the really optimized way.
temp = currentItem['next']
currentItem.next = head['next']
head['next'] = prevItem['next']
prevItem['next'] = temp
def testSwitch():
#test code to ensure that switch() is working correctly.
myList = createList([10, 20, 30, 40, 50, 60])
print "The initial list", listString(myList)
myList = switch(myList, 2)
print "Switching the 1 and the 2. Resulting list is ", listString(myList)
myList = switch(myList, 3)
print "Switching the 4 and the 5. Resuling list is ", listString(myList)
myList = switch(myList, 5)
myList = switch(myList, 29) #should result in an error
From the switch() function I get an error saying AttributeError: 'dict' object has no attribute 'next'. How can I get around this to run the function? Where am I going wrong?
Edit 1: I've changed the parameter list to j and changed the switch functions .nexts to ['next']. Now, when running testSwitch() it comes up with the error "TypeError: 'NoneType' object has no attribute 'getitem'". Any idea where this is coming from? I've combed the code and I doesn't seem like it should be returning None before reaching the test portion...
