I'm studying linked lists in Python 3.11. I wrote code given in the book. Code is below:
class Node:
def __init__(self, data, next=None):
self.data = data
self.next = next
class LinkedList:
def __init__(self):
self.head = None
def __str__(self):
node = self.head
while node is not None:
print(node.data)
node = node.next
def append(self, data):
if not self.head:
self.head = Node(data)
return
current = self.head
while current.next:
current = current.next
current.next = Node(data)
def search(self, target):
current = self.head
while current.next:
if current.data == target:
return True
else:
current = current.next
return False
def remove(self, target):
if self.head == target:
self.head = self.head.next
return
current = self.head
previous = None
while current:
if current.data == target:
previous.next = current.next
previous = current
current = current.next
def reverse_list(self):
current = self.head
previous = None
while current:
next = current.next
current.next = previous
previous = current
current = next
self.head = previous
a_list = LinkedList()
a_list.append("Tuesday")
a_list.append("Wednesday")
print(a_list)
import random
a_list = LinkedList()
for i in range(0, 20):
j = random.randint(1, 30)
a_list.search(j)
print(j, end=' ')
When I run this code, error appears:
Traceback (most recent call last): File linked_list.py, line 62, in print(a_list) TypeError: str returned non-string (type NoneType)
Since the problem in function str, I tried following (adding return in the end): 1)
def __str__(self):
node = self.head
while node is not None:
print(node.data)
node = node.next
return node
The result is the same:
Traceback (most recent call last): File linked_list.py, line 62, in print(a_list) TypeError: str returned non-string (type NoneType)
2)
def __str__(self):
node = self.head
while node is not None:
print(node.data)
node = node.next
return node.data
The result:
Traceback (most recent call last): File "linked_list.py", line 63, in print(a_list) File "linked_list.py", line 18, in str return node.data AttributeError: 'NoneType' object has no attribute 'data'
There is more than one problem in your code:
The issue you ask about: the author of the __str__ mistakenly thought that it should print the content of the list. This is not the purpose of __str__. Instead, it should return a string version of the list. It is up to the caller to do something with this string, which could be printing it or something else.
A quick fix would be to replace the print calls with code that concatenates the data into a string and then returns it:
def __str__(self):
s = ""
node = self.head
while node is not None:
s += f"{node.data} " # don't print, but collect in a string
node = node.next
return s
This is not the most elegant way to do it though. You could benefit from first defining __iter__, which is useful for other purposes as well...
search has a condition where it checks current.next but without ensuring that current is not None. So this code will run into an error when the list is empty. And secondly, it will not find a match when the last node (only) has the searched data. The condition should be on current, not current.next
remove compares head with target, and also current.data with target. This is inconsistent. Either the function is called with a node instance, or with data. Now you have a mix. I suppose you wanted remove to be called with data, and so the first if statement is wrong. You should first check if the list has a node and then check the data of the head node.
remove continues the loop after it has deleted a node, trying to find more matches. That is fine, but it is not consistent with how you deal with a match in the head node, because there you exit the function when there is a match. To be consistent, you should not exit there, and keep going (both checking the head, and later the rest of the nodes).
When remove finds a match in the loop, it updates previous to be the deleted node. This is not correct. For instance, it will mean that only one of two consecutive matching nodes is deleted. When you have a match, previous should remain unchanged and refer to the node that preceded the now deleted node.
Not a problem, but:
a_list.search(j) but doesn't do anything with the returned value, and so it is useless.search method.search does not reveal that it returns a boolean (and not a node or position). Call it has or includes or contains. Or even better, define __contains__, so that you can use the in operator instead. Or still better: when you have defined __iter__ it will be used to interpret the in operator, and so you can actually drop this search method completely._list in the name reverse_list is unnecessary. This is a method on a linked list, so it is evident that the reversal concerns a (linked) list.Here is suggested code for the LinkedList class:
class LinkedList:
def __init__(self):
self.head = None
def __iter__(self): # Make linked list iterable. Also supports IN operator
node = self.head
while node:
yield node.data
node = node.next
def __str__(self): # Don't print, but return str
# Make use of __iter__
return " ".join(map(str, self))
def append(self, data):
if not self.head:
self.head = Node(data)
return
current = self.head
while current.next:
current = current.next
current.next = Node(data)
def remove(self, target):
# Check in a loop, and don't return:
while self.head and self.head.data == target: # compare data, not node
self.head = self.head.next
current = self.head
previous = None
while current:
if current.data == target:
previous.next = current.next
else: # Only update previous when there is no match
previous = current
current = current.next
def reverse(self): # Better name
current = self.head
previous = None
while current:
next = current.next
current.next = previous
previous = current
current = next
self.head = previous
Driver code could be:
a_list = LinkedList()
a_list.append("Tuesday")
a_list.append("Wednesday")
a_list.append("Wednesday")
a_list.append("Thursday")
print(a_list)
a_list.remove("Wednesday")
print("Does it have Tuesday? ", "Tuesday" in a_list)
print(*a_list)