Lecture 180:- Improve Searching in Linked List

To improve the searching in a linked list, we can implement a more efficient search by using a technique called "skip searching" or "jump searching." In skip searching, we make use of a secondary pointer that "jumps" ahead by a fixed number of steps at each iteration. This helps to skip unnecessary iterations and reduce the search time, especially for large linked lists.

Let's add a method called improved_search to the LinkedList class using the skip searching technique:

pythonCopy code

class Node:    def __init__(self, data):        self.data = data        self.next = None class LinkedList:    def __init__(self):        self.head = None    def append(self, data):        new_node = Node(data)        if not self.head:            self.head = new_node        else:            current = self.head            while current.next:                current = current.next            current.next = new_node    def remove(self, data):        if not self.head:            return        if self.head.data == data:            self.head = self.head.next            return        current = self.head        while current.next:            if current.next.data == data:                current.next = current.next.next                return            current = current.next    def display(self):        current = self.head        while current:            print(current.data, end=" -> ")            current = current.next        print("None")    def find_max(self):        if not self.head:            return None        max_value = self.head.data        current = self.head.next        while current:            if current.data > max_value:                max_value = current.data            current = current.next        return max_value    def search(self, value):        current = self.head        while current:            if current.data == value:                return True            current = current.next        return False    def improved_search(self, value):        if not self.head:            return False        jump = 3  # You can choose an appropriate jump value based on the size of the linked list.        current = self.head        while current:            if current.data == value:                return True            elif current.data > value:                return False            else:                for _ in range(jump):                    if current.next:                        current = current.next                    else:                        break        return False # Example usage: if __name__ == "__main__":    linked_list = LinkedList()    linked_list.append(3)    linked_list.append(7)    linked_list.append(1)    linked_list.append(9)    print("Original Linked List:")    linked_list.display()    search_value = 7    if linked_list.improved_search(search_value):        print(f"{search_value} found in the linked list.")    else:        print(f"{search_value} not found in the linked list.")

In the example usage above, we have added an improved_search method to the LinkedList class using the skip searching technique. We create a linked list and add elements 3, 7, 1, and 9 to it. We then search for the value 7 in the linked list using the improved_search method and display whether the value is found or not.

Please note that the effectiveness of skip searching depends on the jump value chosen. If the jump value is too large, we might end up skipping over the target value. Therefore, the choice of the jump value should be done carefully, keeping the size and distribution of the linked list data in mind.