I plan to add a search function in python linkedlist. It aims to search a string whether in the linkedlist or not (Each node of the linkedlist has a word). For example, if the linkedlist is : I -> am -> a -> python -> developer. If I search the text 'python', it will return True, if I search the text 'apython', it will return True, but if I search 'java' or 'ajava' it will return false. I write my codes as below, but search function cannot work. I am not sure should I add recursive function to solve the issue.
class Node:
def __init__(self, value):
self.value = value
self.next = None
class LinkedList:
def __init__(self, head = None):
self.head = head
def append(self, new_node):
curr = self.head
if curr:
while curr.next:
curr = curr.next
curr.next = new_node
else:
self.head = new_node
def search(self, text, cur):
if cur.value == text:
return True
while cur.next != self.head and cur.next != None:
if cur.next:
cur = cur.next
if cur.value == text:
return True
return False
Your code is only testing cases where the text matches completely with a single node value.
Some other remarks:
cur.next != self.head
is never going to be true. By definition the head
node is the first node of the list, so it will never be the successor after a given node.
The if cur.next
is overkill, because that condition is always going to be true - it was the reason why the while
loop didn't exit yet.
if cur.value == text
appears twice in your code. This should not be necessary. Apply DRY.
But as stated, the main issue is that there is no code that tries to match a node with part of the given text.
One of the ways to tackle this, is to write two functions: one to check if the given node is the start of a series of nodes that together match the given text. Another function can call the first function on each node of the list. If any of those leads to success, then the search is successful.
Here is the code for that:
def startswith(self, text, cur):
while cur and text.startswith(cur.value):
text = text[len(cur.value):]
if not text:
return True
cur = cur.next
return False
def search(self, text, cur):
if not text: # Boundary case
return True # Or False, whatever you expect to happen
while cur and not self.startswith(text, cur):
cur = cur.next
return cur is not None
Example code to run your example scenario:
lst = LinkedList()
for word in "I am a python developer".split(" "):
lst.append(Node(word))
print(lst.search("apython", lst.head)) # True