উত্তরঃ
1. Linked List
A Linked List is a dynamic linear data structure in which elements are not stored at contiguous memory locations. Instead, elements are linked using pointers.
Each element in a linked list is called a Node, which consists of two main parts:
- Data: Stores the actual value or information.
- Next Pointer: Stores the memory address of the next node in the sequence.
Types of Linked List:
- Singly Linked List: Navigation is forward only; each node points to the next node, and the last node points to
NULL.
- Doubly Linked List: Each node contains two pointers, pointing to both the next and the previous nodes.
- Circular Linked List: The last node points back to the first node, forming a circular loop.
2. Searching
Searching is the process of finding the position of a specific target element (or key) within a collection of data structures (such as an array, linked list, or tree).
It is a fundamental operation in computer computer science that returns either the index/location of the requested element or a signal (e.g., -1 or NULL) indicating that the element does not exist in the dataset.
3. Binary Search
Binary Search is an efficient algorithm used to find the position of a target element within a sorted dataset (array or list). It works based on the Divide and Conquer algorithmic paradigm.
Prerequisite: The data elements must be strictly sorted in ascending or descending order.
Working Mechanism / Algorithm:
- Set two pointers, \(\text{low}\) at the first index (\(0\)) and \(\text{high}\) at the last index (\(n-1\)).
- Calculate the middle index: \(\text{mid} = \lfloor \frac{\text{low} + \text{high}}{2} \rfloor\).
- Compare the target element with the middle element (\(\text{Array}[\text{mid}]\)):
- If \(\text{Target} == \text{Array}[\text{mid}]\), the element is found; return \(\text{mid}\).
- If \(\text{Target} < \text{Array}[\text{mid}]\), search the left half by setting \(\text{high} = \text{mid} - 1\).
- If \(\text{Target} > \text{Array}[\text{mid}]\), search the right half by setting \(\text{low} = \text{mid} + 1\).
- Repeat steps 2 and 3 until the element is found or \(\text{low} > \text{high}\) (target not present).
Example Demonstration:
Given sorted array: \([10, 20, 30, 40, 50, 60, 70]\) and \(\text{Target} = 50\)
- Pass 1: \(\text{low} = 0\), \(\text{high} = 6\) \(\rightarrow\) \(\text{mid} = \lfloor \frac{0+6}{2} \rfloor = 3\). \(\text{Array}[3] = 40\). Since \(50 > 40\), search shifts right: \(\text{low} = 3 + 1 = 4\).
- Pass 2: \(\text{low} = 4\), \(\text{high} = 6\) \(\rightarrow\) \(\text{mid} = \lfloor \frac{4+6}{2} \rfloor = 5\). \(\text{Array}[5] = 60\). Since \(50 < 60\), search shifts left: \(\text{high} = 5 - 1 = 4\).
- Pass 3: \(\text{low} = 4\), \(\text{high} = 4\) \(\rightarrow\) \(\text{mid} = \lfloor \frac{4+4}{2} \rfloor = 4\). \(\text{Array}[4] = 50\). Target matched at index \(4\).
Complexity Analysis:
- Best-case Time Complexity: \(O(1)\) (When the element is at the mid position on the first check)
- Average & Worst-case Time Complexity: \(O(\log_2 n)\)
- Auxiliary Space Complexity: \(O(1)\) (Iterative implementation)
