Arrays in Data Structures

Arrays

• A data structure that stores a collection of elements, each identified by an index or key
• Elements are stored in contiguous memory locations
• Each element is of the same data type
• Arrays have a fixed size, which is determined at the time of creation
• Operations:
  • Accessing an element: O(1) time complexity
  • Inserting or deleting an element: O(n) time complexity, where n is the size of the array
  • Searching for an element: O(n) time complexity (see Linear Search below)

Linear Search

• A search algorithm used to find an element in a data structure, such as an array
• Works by iterating through the elements of the data structure one by one, checking if the target element is equal to the current element
• Time complexity: O(n), where n is the size of the data structure
• Space complexity: O(1), since only a single element is accessed at a time
• Linear search is not efficient for large data structures, but it is simple to implement and works well for small data structures
• Example pseudo-code:

for i = 0 to n-1
  if array[i] == target
    return i
return -1  // element not found

Note: The time complexity of linear search can be improved to O(n/2) on average by starting the search from the middle of the array, but the worst-case time complexity remains O(n).

Arrays

• Stores a collection of elements, each identified by an index or key
• Elements are stored in contiguous memory locations
• Each element is of the same data type
• Fixed size, determined at the time of creation
• Operations have different time complexities:
  • Accessing an element: O(1)
  • Inserting or deleting an element: O(n)
  • Searching for an element: O(n)

Linear Search

• A search algorithm used to find an element in a data structure
• Iterates through elements one by one, checking for the target element
• Time complexity: O(n)
• Space complexity: O(1)
• Not efficient for large data structures, but simple to implement and suitable for small data structures
• Can be improved to O(n/2) on average by starting from the middle of the array
• Pseudo-code example:
  • Iterate through the array from index 0 to n-1
  • Check if the current element is equal to the target
  • Return the index if found, -1 if not found