Everything about ARRAY

• The simplest form of array is a one-dimensional array
• Data is strored in contiguous memory locations.
• Arrays are classified as Homogeneous Data Structures because they store elements of the same type.
• Cannot add different types of data to a same array.

Fixed-Size Arrays and Dynamic Arrays

• Fixed-Size Arrays: In languages like C, arrays have a pre-defined size at the time of creation. Adding elements beyond this size is not possible and typically results in errors.
• Dynamic Arrays (Resizeable Arrays): In languages like Python and Java, arrays can be resized dynamically to accommodate new elements.

Create an Array in Python

import array as arr
# creating an integer data type array
array_one = arr.array('i',[1,2,3])

Here i is the typecode (datatype)passed into the array.
Typecodes are alphabetic representations that are used to define the type of value the array is going to store.

Type Code for array

https://docs.python.org/3/library/array.html

Adding Elements to a Array

• Elements are added using the insert() function.
• Used to enter one or more data elements into the array.
• insert(index, element_to_add), takes the first argument as the index where the element to be added and the second argument as the element to add to the array.|
• append(element_to_add)adds the element to the end of the array

import array as arr
# creating an integer data type array
array_one = arr.array('i',[1,2,3])

# Add element in a particular index
array_one.insert(1,2)

#Add element to the end of the array
array_one.append(5)

Complexity for adding elements

Fixed-Size Arrays:

• Appending: Not possible (throws errors)
• Inserting at Beginning/Middle: Not possible (throws errors)

Dynamic Arrays:

• Appending to the End:
  Constant Time (O(1)) Average Case: In many dynamic arrays, appending an element involves updating a pointer or index to the end of the array. This is a constant time operation in most cases.
  Amortized Constant Time (O(1) amortized): Some dynamic arrays might need to be resized (allocated a new larger block of memory) when they reach capacity. This resizing operation can take some additional time. However, the overall cost of appending elements over a series of operations is considered amortized constant time.
• Inserting at the Beginning/Middle:
  Linear Time (O(n)) Worst Case: Inserting at the beginning or middle requires shifting existing elements to create space for the new element. In the worst case (e.g., inserting at the beginning of a full array), all elements need to be shifted, resulting in linear time complexity.

Accessing Elements from the Array

• Items in array are accessed using the index number.
• Index operator [] is used in python and it is an integer.

import array as arr
# creating an integer data type array
array_one = arr.array('i',[1,2,3])

#Access the first item : index 0
array_one[0]

Complexity for accessing elements

Constant Time (O(1)): Accessing an element in an array by its index is a constant time operation. This is because arrays are stored in contiguous memory locations, and calculating the memory address of a specific element based on its index can be done very quickly.
The memory address of an element at index i can be calculated efficiently using a formula like base_address + (i * element_size). Here:

• base_address is the starting memory address of the array.
• i is the index of the element you want to access.
• element_size is the size of each element in bytes (determined by the data type).

Removing Elements from the Array

• Elements can be removed from the Python array by using built-in remove() function
• remove() method removes only one element at a time. It only removes the first occurance of the searched element.
• To remove elements in a given range, pop() function is used.
• By default, pop() removes the last element. To remove an element from a specific index, index of the elements are passed as argument.

import array as arr
# creating an integer data type array
array_one = arr.array('i',[1,2,3])

# Remove the number 3
array_one.remove(3)

# Remove or pop the item at index 2
array_one.pop(2)

Complexity for Removing Elements

Fixed-Size Arrays:

• Generally it is not possible to remove elements after creation.
• Attempting removal might result in errors.

Dynamic Arrays:

1. Removing from the End :

• Amortized Constant Time (O(1) amortized): In many dynamic arrays, removing the last element often involves updating a pointer or index, which is a constant time operation.
• However, if the array needs to be shrunk due to frequent removals, the overall cost becomes amortized constant.

2. Removing from the Beginning or Middle:

• Linear Time (O(n)) Worst Case: Removing from the beginning or middle requires shifting remaining elements to fill the gap created by the removal. In the worst case (e.g., removing from the beginning of a large array), all elements need to be shifted, leading to linear time complexity.

Slicing of an Array

• Slicing an array is for extracting a sub-array from an existing array.
• It allows to create a new array containing a specific portion of the original array, without modifying the original itself.
• sliced_array = original_array[start:end:step]
• start (optional): This specifies the index of the first element to include in the slice (inclusive). Defaults to 0 (beginning of the array) if not provided.
• end (optional): This specifies the index of the element after the last element to include in the slice (exclusive). If not provided, the slice goes up to the end of the array.
• step (optional): This specifies the step size for including elements. Defaults to 1 (includes every element). A step of 2 would include every other element, and so on.

import array as arr
# creating an integer data type array
array_one = arr.array('i',[1,2,3])

# Slicing and creating an new array with 2 and 3
sliced_array = array_one[1,3]

Complexity for Slicing Elements

Slicing of the array incudes copying the sliced values internally. The number of iterations in the worst case (copying all elements in the slice) is directly proportional to the number of elements retrieved (k).

Searching Element in an Array

• index() function is used to search for an element in an array. It returns the index of the first occurance of the value searched.

import array as arr
# creating an integer data type array
array_one = arr.array('i',[1,2,3])

# Search for index of 2 by passing the value 2 to the index() function
index = array_one.index(2)

# ==> Returns 1, as value 2 is at 1st index in array_one named array

Complexity for Searching Elements

1. Linear Search (Unsorted Arrays):

• Time Complexity: O(n) (worst case, average)
• Linear search iterates through each element in the array one by one, comparing it to the target element.
• In the worst case (target element is not present or at the end), the entire array needs to be scanned, resulting in O(n) complexity.

2. Binary Search (Sorted Arrays):

• Time Complexity: O(log n) (best, average, worst case)

#Updating Elements in a Array

• Accessing by Index and Assigning a New Value:
  This is the most common and straightforward approach. You use the element’s index to access it and then assign a new value:

import array as arr
# creating an integer data type array
array_one = arr.array('i',[1,2,3])

# Updating 0th index value with 3
array_one[0] = 3

• Using a Loop to Update Multiple Elements:
  Iterate through the array using a loop and update elements based on conditions or calculations:

import array as arr
# creating an integer data type array
array_one = arr.array('i',[1,2,3])

# Double the value of each element
for i in range(len(array_one)):
  my_array[i] *= 2

A loop iterates through each element’s index (i) using range(len(array_one)).
Inside the loop, you can access the element using array_one[i] and modify it as needed.

• Using List Comprehension (Python) for Conditional Updates:
  List comprehension provides a concise way to create a new array with updated elements based on conditions.

import array as arr
# creating an integer data type array
array_one = arr.array('i',[1,2,3])

# Update elements greater than 2 to 0
updated_array = [x if x <= 2 else 0 for x in array_one]

# ==> Returns [1,2,0]

Complexity for Updating Elements

Updating elements in arrays by index and assignment is typically a constant time operation (O(1)) due to efficient memory access and assignment.

Different Operations on Python Arrays

Counting Elements in a Array:

• len() function:
  Returns the total number of elements in the fuction.
  Takes an array as argument.
• count() function:
  Returns the number of occurances of a number or value
  array_name.count(number) returns the frequency of numbers.

Extending Elements in a Array:

• extend() function:
  Extend method takes an iterable (list of items) as an argument and joins them.
  It works only with iterables of same data type.

Adding Elements to theArray:

• insert() function:
  array_name.insert(index, value) takes index at which to insert the value as first argument and the value to insert as second argument.
• append() function:
  array_name.append(value) function adds the value to the end of the array. To add at a specific location, use the array_name.insert(index, value) function.

Remove Values from an Array:

• remove() function:
  array_name.remove(value) function takes the value to remove as argument and removes the first occurance of the value.
• pop() function:
  array_name.pop(index) function takes the index as argument and removes the elment at that index.
• clear() function:
  array_name.clear() function clears all the elments in the array.

Copy Values from an Array:

Shallow Copy:

• copy() function:
  copied_list = original_list.copy() makes a shallow copy of the array.
  Both original_list and copied_list references to the same underlying data in the memory.
  Changes made to the copied array/list will also be reflected in the original because they both point to the same data.
• Slicing:
  Slicing an array using [:] creates a new array object.
  Both original_list and copied_list references to the same underlying data in the memory.

Deep Copy:

• The deepcopy() function from the copy module is used.

import copy
copied_list = copy.deepcopy(original_list)