I am trying to implement a linked list class from scratch in Python, and am encountering an issue that is probably related to how Python is intended to work, but I would like to make sure.
Here is the basis of my implementation:
class Node(object):
def __init__(self, data=None, next=None):
self.next = next
self.data = data
def appendToTail(self, d: int):
newNode = Node(d)
while self.next is not None: self = self.next
self.next = newNode
And the class method that does not work as I would like it to :
def reverse(self):
prevNode = None
currentNode = self # current = 1
while self is not None:
nextNode = self.next
self.next = prevNode
prevNode = self
self = nextNode
self = prevNode
I am trying to reverse the linked list in place, but when I call this method, the list appears to be empty.
I also implemented another version of this method that preforms a return self
at the end, and the returned list is indeed the correct result I am looking for:
def reverseNotInPlace(n: Node()) -> Node():
prevNode = None
n = n.next
while n is not None:
nextNode = n.next
n.next = prevNode
prevNode = n
n = nextNode
return prevNode
To summarize:
# creating a linked list such as: [1 -> 2 -> 3]
myList = Node()
myList.appendToTail(1)
myList.appendToTail(2)
myList.appendToTail(3)
# inverting it not in place works
invList = reverseNotInPlace(myList)
# returns [3 -> 2 -> 1]
myList.reverse()
# returns only the first node of myList()
So my question is: is there something wrong with my implementation ? Or is what I am trying to do not exactly possible ?
Thank you very much !
classmethod
which operates on the class (cls
) not the instance (self
).self
doesn't change the list. Once the method returns,self
still refers to the original head of the list. Unless you use a dummy node (so thatself.next
, notself
itself, refers to the first item), you can't do an in-place reversal without modifyingself.data
.self = prevNode
just binds the local nameself
to another values. It does not modify any of the other aliases to the instance.node
and one for thelist
. The latter one maintains the head (and optionally) tail pointers. This way, you don't need to modifyself
.