Searching in Array and Linked List:
Searching in arrays and linked lists are fundamental operations in data structures, but they are implemented differently due to the underlying structure of each.
1. Searching in an Array:
Arrays provide random access to elements because they are stored in contiguous memory locations. This allows quick access to any element using its index.
Types of Searches in Arrays:
1. Linear Search (Sequential Search):
Start from the first element and compare each element with the target value.
Continue searching until the target is found or the end of the array is reached.
Time Complexity: O(n) (n is the number of elements in the array).
Algorithm:
def linear_search(arr, target):
for i in range(len(arr)):
if arr[i] == target:
return i # Return the index if the target is found
return -1 # Return -1 if the target is not found
2. Binary Search (For Sorted Arrays Only):
Works only on sorted arrays.
It repeatedly divides the array in half and checks whether the target value is in the left half or the right half.
Time Complexity: O(log n) because the array is divided in half in each step.
Algorithm:
def binary_search(arr, target):
low, high = 0, len(arr) - 1
while low <= high:
mid = (low + high) // 2
if arr[mid] == target:
return mid # Return the index if the target is found
elif arr[mid] < target:
low = mid + 1
else:
high = mid - 1
return -1 # Return -1 if the target is not found
2. Searching in a Linked List:
Linked lists do not provide random access to elements. Since each element is stored in a node and each node points to the next node, accessing an element requires sequential traversal from the head (starting node).
Types of Searches in Linked Lists:
1. Linear Search (Sequential Search):
Traverse the list starting from the head and compare each node's data with the target value.
Continue until the target is found or the end of the list is reached.
Time Complexity: O(n) (n is the number of nodes in the linked list).
Algorithm (Singly Linked List):
def __init__(self, data):
self.data = data
self.next = None
def search_linked_list(head, target):
current = head
while current:
if current.data == target:
return current # Return the node if target is found
current = current.next
return None # Return None if the target is not found
Summary:
• Arrays support faster access via indexing and allow binary search if sorted. However, searching can still take O(n) time if the array is unsorted, and insertion or deletion requires shifting elements.
• Linked lists require linear time to search (O(n)) and don’t support binary search, but they offer more flexibility with dynamic memory allocation and efficient insertion/deletion operations.