reverse the python linked list
In any experiment, if I'm not clear on what to do, I will probably google for a solution, see what I can find and work from there. This one has a lot of solutions.
The one I found that had the visual I need was the one below, but note, it uses recursion. I use a while loop in this experiment.
Here's a link that even has a python linked list reversal:
https://www.geeksforgeeks.org/reverse-a-linked-list/
Lets build it piece by piece.
First the node, and a test on the node.
The Pytest for original single linked list I made for LearnMorePythonTheHardWay:
https://camelcasenoodles.blogspot.com/2017/12/pytest-for-my-single-linked-list-in.html
So our list will need:
* push (add item to list)
* get(retrieve item by index)
* dump/graphical (see what the list looks like)
* reverse(reverse the items in the list back to front)
We'll do small bits at a time.
First the node. and a small test.
--- start code block ---
--- end code block ---
About Push-Append
Now that we have a node, you can see a little there in the test how we'd -push- or -append- an item to a list. A single linked list traditionally has a node holding data that points to the next item in the list, or None if there is no next item.
These lists are faster in languages such as C in that the machine code can look up an address for a next item, instead of a python list, which would do a little math to find the next item in memory. For example if mynode is stored at memory spot 0x6767....
and we want the next item, we can look at that self.next which holds the address in memory. maybe it's 0x7788.... The memory can just grab whats in that location. Other lists and arrays use math to determine where items are. A simple example: first item is at point 0x00010 in our memory, and we want item 5. Some secret magical algorithm says something along the lines of, next item is 0x00010 + 5, we want item at 0x00015. I don't honestly know how specifically the memory and look up works, if someone wants to drop a comment and explain, that would be most excellent.
Next Step
IMAGE: The nodes being printed off in the terminal in a visual way. The items index is first, then the data, then an arrow pointing to the next item's index and data, or if it is a None, it will say NONE.
Lets add things to the list. Now to test this part, we'll need a way to verify what is in the list where, so we are going to need a 'get' just to be able to test if our items are pushed properly into the list.
But first, lets use a method to print off our pushed items, and see what it looks like. Small chunks, lay brick by brick until your foundation is built.
Feel free to remove Node tests from previous code block, but the SLLNode needs to be present in the file for the SLList to use it. (Wether by import or direct code, SLList needs to access it to use it)
--- code block start ---
--- code block end ---
Next Step
Lets add the get, and a test. The thing I love about writing my own manual tests, is I get to decide what info I want to see, what things it needs to show me, and how it shows me.
Add the code below to your SLList class. You can also add the test outside the class at the bottom of the file and run it to see that in action.
Image: The terminal print off of the code from the test_push_get():
****** testing SLList.push and SLList.get ********
test fruits.get(0) = pass
test fruits.get(1) = pass
test fruits.get(2) = pass
test fruits.get(3) = pass
test a None is recieved on bad index fruits.get(28) = pass
This list is EMPTY.
test a None is recieved on empty list veggies.get(2) = pass
************* End tests *************
--- start code block ---
--- end code block ---
Next Step
create the reverse. Swapping links. This part always gets my brain a bit warped. It took me a few hours to get it right. If you have even one of the swap's wrong, the list will break.
In the next code block is the code for the reverse method, and it's test. It looks a lot bigger than it is. The print statements and count were used as I tried to figure out what was going wrong in the swaps.
Here's an image of the terminal graphical print off of the reversed list:
***** end loop *****
next_node.data = Maple-3-
current.next = [Maple-3- ---> None]
[(0) Maple-3- ---> Palm-2-(1)]
[(1) Palm-2- ---> Oak-1-(2)]
[(2) Oak-1- ---> Apple-0-(3)]
[(3) Apple-0- ---> NONE(/)]
--code block start --
--code block end --
Happy coding! break it, tame it, make it do what you want. As always, feel free to leave a comment.
The one I found that had the visual I need was the one below, but note, it uses recursion. I use a while loop in this experiment.
Here's a link that even has a python linked list reversal:
https://www.geeksforgeeks.org/reverse-a-linked-list/
Lets build it piece by piece.
First the node, and a test on the node.
The Pytest for original single linked list I made for LearnMorePythonTheHardWay:
https://camelcasenoodles.blogspot.com/2017/12/pytest-for-my-single-linked-list-in.html
So our list will need:
* push (add item to list)
* get(retrieve item by index)
* dump/graphical (see what the list looks like)
* reverse(reverse the items in the list back to front)
We'll do small bits at a time.
First the node. and a small test.
--- start code block ---
class SLLNode(object):
# data is data you wish to store
def __init__(self, data, nxt):
self.data = data
# next is a reference to the next node in the list
self.next = nxt
def __repr__(self):
# if this is printing something like:
# <__main__.SLLNode object at 0x000001FF561D7128>
# there is a 'next', 'data' or 'nval' is not properly handled.
# check that your variables match with this code.
# this creates a string representation of the data and next
nval = self.next and self.next.data or None
# nval is the next node, so it needs the (node = next and it's data) or None
return f"[{self.data} ---> {repr(nval)}]"
def test_node():
# create two nodes
mynode = SLLNode('start node data', None)
mynextnode = SLLNode('some more node data', None)
# link the mynode to the nextnode
mynode.next = mynextnode
print(mynode)
print(mynextnode)
# I will run this first part, make sure it's working with the prints, then add asserts.
#### stop here, run test, then add asserts. ####
assert mynode.data == 'start node data'
assert mynextnode.data == 'some more node data'
assert mynode.next.data == 'some more node data'
assert mynextnode.next == None
## will this error?
#assert mynextnode.next.data == None
# when you uncomment this and see the Error, NoneType is not an actual type you can test for in Python.
# it's just telling you that since mynextnode.next is None, it has no operator .data.
#---run first test, pass, and then continue.---#
test_node() # comment out to continue
#----------------------------------------------#
About Push-Append
Now that we have a node, you can see a little there in the test how we'd -push- or -append- an item to a list. A single linked list traditionally has a node holding data that points to the next item in the list, or None if there is no next item.
These lists are faster in languages such as C in that the machine code can look up an address for a next item, instead of a python list, which would do a little math to find the next item in memory. For example if mynode is stored at memory spot 0x6767....
and we want the next item, we can look at that self.next which holds the address in memory. maybe it's 0x7788.... The memory can just grab whats in that location. Other lists and arrays use math to determine where items are. A simple example: first item is at point 0x00010 in our memory, and we want item 5. Some secret magical algorithm says something along the lines of, next item is 0x00010 + 5, we want item at 0x00015. I don't honestly know how specifically the memory and look up works, if someone wants to drop a comment and explain, that would be most excellent.
Next Step
IMAGE: The nodes being printed off in the terminal in a visual way. The items index is first, then the data, then an arrow pointing to the next item's index and data, or if it is a None, it will say NONE.
Lets add things to the list. Now to test this part, we'll need a way to verify what is in the list where, so we are going to need a 'get' just to be able to test if our items are pushed properly into the list.
But first, lets use a method to print off our pushed items, and see what it looks like. Small chunks, lay brick by brick until your foundation is built.
Feel free to remove Node tests from previous code block, but the SLLNode needs to be present in the file for the SLList to use it. (Wether by import or direct code, SLList needs to access it to use it)
--- code block start ---
class SLLNode(object):
# data is data you wish to store
def __init__(self, data, nxt):
self.data = data
# next is a reference to the next node in the list
self.next = nxt
def __repr__(self):
# if this is printing something like:
# <__main__.SLLNode object at 0x000001FF561D7128>
# there is a 'next', 'data' or 'nval' is not properly handled.
# check that your variables match with this code.
# this creates a string representation of the data and next
nval = self.next and self.next.data or None
# nval is the next node, so it needs the (node = next and it's data) or None
return f"[{self.data} ---> {repr(nval)}]"
def test_node():
# create two nodes
mynode = SLLNode('start node data', None)
mynextnode = SLLNode('some more node data', None)
# link the mynode to the nextnode
mynode.next = mynextnode
print(mynode)
print(mynextnode)
# I will run this first part, make sure it's working with the prints, then add asserts.
#### stop here, run test, then add asserts. ####
assert mynode.data == 'start node data'
assert mynextnode.data == 'some more node data'
assert mynode.next.data == 'some more node data'
assert mynextnode.next == None
## will this error?
#assert mynextnode.next.data == None
# when you uncomment this and see the Error, NoneType is not an actual type you can test for in Python.
# it's just telling you that since mynextnode.next is None, it has no operator .data.
#---run first test, pass, and then continue.---#
# test_node() # comment out to continue
#----------------------------------------------#
class SLList(object):
# We are not initiating anything for this list. It will be empty until we 'push' an object, obj or data to it.
# start with a begin that is None. This is where our first Node will go.
def __init__(self):
self.begin = None
self.end = None
# lets add a length to avoid using a while loop count. While loops
# can easily eat up delivery time, and are easily faulted into infinites,
# been there done that TONS of times.
self.length = 0
def push(self, obj):
# create a node with the object data.
# the next will be None, because we are pushing to the end of the list.
# if this is the first item, we still want that to be None.
# The next is handled farther down if the list is not empty
node = SLLNode(obj, None)
# check if the list is empty by checking our self.begin
if self.begin == None:
self.begin = node
elif self.begin != None and self.end == None:
# There is only one item in this list.
# The original assignment had self.end and self.begin setting
# as the same node if it is only a length of one.
# I tend to believe this is a really bad thing to do.
self.begin.next = node
self.end = node
self.length += 1
else:
# the list contains an end node, and a begin node. Neither is None.
# we push a new node always to the end of a list.
#---------------#
# we want to change that end node so it points to the next new node we are adding.
self.end.next = node
# Now tell python to reassign the value of self.end to our new node.
# the original self.end does not dissappear, but is saved by the node before it who
# holds it's memory address in it's 'next' pointer/link
self.end = node
# Lets make a way to print these nodes in command prompt: terminal so we can see where everything is.
def graphical(self):
# format:
# [(index in list)item ---> (index of next item or None) next item )]
node = self.begin
i = 0
#because we set a next to None at the end of the list, this loop will stop when node = None
print("\n\n")
if node == None:
print("The list is Empty, no begin node!")
else:
while node:
if node.next != None:
# if the next node is None, this will error because node.next.data does not exist.
print(f"\t[({i}) {node.data} ---> {node.next.data}({i + 1})]")
else:
# the next item is None, to prevent it from erroring on print statement,
# do not call the node.next.data.
print(f"\t[({i}) {node.data} ---> NONE(/)]")
# increment the node, go to next one.
node = node.next
# increment the index - i
i += 1
print("\n\n")
### --------------------------- ####
# test graphical: move this code to the end of the file, and run.#
trees = SLList()
trees.push("Apple")
trees.push("Oak")
trees.push("Palm")
trees.push("Maple")
trees.graphical()
Next Step
Lets add the get, and a test. The thing I love about writing my own manual tests, is I get to decide what info I want to see, what things it needs to show me, and how it shows me.
Add the code below to your SLList class. You can also add the test outside the class at the bottom of the file and run it to see that in action.
Image: The terminal print off of the code from the test_push_get():
****** testing SLList.push and SLList.get ********
test fruits.get(0) = pass
test fruits.get(1) = pass
test fruits.get(2) = pass
test fruits.get(3) = pass
test a None is recieved on bad index fruits.get(28) = pass
This list is EMPTY.
test a None is recieved on empty list veggies.get(2) = pass
************* End tests *************
--- start code block ---
# indent is because it is in the SLList class
def get(self, i):
# here is where length will come in handy. If you use length instead of
# a count loop, remember that any method such as delete or pop needs to
# change the length to reflect the change in size or this all breaks.
current = 0
if type(i) != int:
# make sure they are using an int for the index argument.
print("Index-i in SLList.get(i) must be an integer.")
raise IndexError
elif self.begin == None:
# make sure list is not empty
print("This list is EMPTY.")
return None
else:
node = self.begin
while node:
if current == i:
return node.data
else:
node = node.next
current += 1
# fail safe. Return None if index is not found.
return None
def test_push_get():
## If asserts pass, nothing happens.
## uncomment the fail to see an assert fail.
print("\n ****** testing SLList.push and SLList.get ********\n")
fruits = SLList()
veggies = SLList()
fruits.push('apple')#<-- self.begin 0
fruits.push('orange')#<-- item 1
fruits.push('pear')#<-- item 2
fruits.push('banana') #<-- self.end item 3
assert fruits.get(0) == 'apple'
print("test fruits.get(0) = pass")
assert fruits.get(1) == 'orange'
print("test fruits.get(1) = pass")
assert fruits.get(2) == 'pear'
print("test fruits.get(2) = pass")
assert fruits.get(3) == 'banana'
print("test fruits.get(3) = pass")
assert fruits.get(28) == None
print("test a None is recieved on bad index fruits.get(28) = pass")
assert veggies.get(2) == None
print("test a None is recieved on empty list veggies.get(2) = pass")
# --- Fail assert ---- #
#assert veggies.get(0) == 'YUMMY'
print(" \n************* End tests *************\n")
test_push_get()
Next Step
create the reverse. Swapping links. This part always gets my brain a bit warped. It took me a few hours to get it right. If you have even one of the swap's wrong, the list will break.
In the next code block is the code for the reverse method, and it's test. It looks a lot bigger than it is. The print statements and count were used as I tried to figure out what was going wrong in the swaps.
Here's an image of the terminal graphical print off of the reversed list:
***** end loop *****
next_node.data = Maple-3-
current.next = [Maple-3- ---> None]
[(0) Maple-3- ---> Palm-2-(1)]
[(1) Palm-2- ---> Oak-1-(2)]
[(2) Oak-1- ---> Apple-0-(3)]
[(3) Apple-0- ---> NONE(/)]
#indent is because it's in the class SLList
# add this bit to complete the code from this experiment.
def reverse(self):
# check for empty:
if self.begin == None:
# Do nothing.
pass
# check if length == 1
elif self.length == 1:
# Do nothing
pass
elif self.begin != None and self.end != None:
# lets loop through it, and swap out those 'next' pointers.
# end has no next pointer.
# TONS of prints. The setting of the links is a very minimal
# amount of code, but getting it "JUST" right is the kick in the head
prev = self.begin
current = prev.next
next_node = current.next
count = 0
while next_node:
if next_node.next == None:
print("\n\n\n\n next=None if block \n\n\n\n")
print("***** end loop *****")
print("next_node.data =", next_node.data)
print("current.next =", current.next)
self.end = self.begin
self.end.next = None
current.next = prev #<----without this, infinite loops in SLList.graphical()
self.begin = next_node
self.begin.next = current
break
else:
print("\n\n\n ELSE LOOP \n\n\n")
if prev == None:
print("prev = ", 'None')
print("current =", current.data)
print("next =", next_node.data)
print("swapping------")
else:
print("prev = ", prev.data)
print("current =", current.data)
print("next =", next_node.data)
print("swapping------")
### set link ###
current.next = prev
### reset prev, current, next ####
prev = current
current = next_node
next_node = next_node.next
print("***** after SWAP *******")
print("prev = ", prev.data)
print("current =", current.data)
print("next =", next_node.data)
count += 1
### Test it ####
def test_reverse():
trees = SLList()
trees.push("Apple-0-")
trees.push("Oak-1-")
trees.push("Palm-2-")
trees.push("Maple-3-")
trees.reverse()
trees.graphical()
nums = SLList()
for i in range(0, 50):
nums.push(i)
nums.reverse()
nums.graphical()
#test_reverse()
Happy coding! break it, tame it, make it do what you want. As always, feel free to leave a comment.
Comments
Post a Comment