Search code examples
pythonstringsearchlinked-list

add search function in linkedlist


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

Solution

  • 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