Static and Dynamic Array, List, Tuples

Intro

Array is a DS that stores elements in contiguous memory locations and ****supports index-based access

Subarray → sequence of contiguous values

arr = [2, 3, 6, 1, 5, 4]
subarray = arr[1:4] # [3, 6, 1]

Subsequence → sequence with the order preserved, not necessarily contiguous

subsequence = [arr[i] for i in [1, 3, 4]] # [3, 1, 5]

Static Array

fixed-size container
elements stored sequentially in memory
access only via index
fast reads, inflexible size
used in low-level languages (C, Java)

Dynamic Array

automatically resizes (usually doubles capacity)
flexible size with fast index access
occasional costly resize, but fast on average
most common array type in practice

int arr[] =newint[10];
arr[0] =5;

arr = []
arr.append(5)

List is a DS that is mutable, ordered and a Dynamic Array

nums = [1, 2, 3]
nums.append(4) # O(1)
nums[0] = 10
nums.pop() # O(1)
nums.insert(0, 99) # O(n)
nums.remove(2) # O(n)
nums.sort() # O(n log n)
squares = [x * x for x in range(5) if x % 2 == 0] # list comprehensions 

list_empty = [] # empty list
print(list_empty) # Output: []
list_ints = [1, 2, 3, 4, 5, 5, 4, 3, 2, 1] # list of integers
print(list_ints) # Output: [1, 2, 3, 4, 5, 5, 4, 3, 2, 1]
list_strs = ['emre', 'dot', 'me'] # list of strings
print(list_strs) # Output: ['emre', 'dot', 'me']
list_mixed = [1, 'emre.me', 5.73, True] # list of mixed data types
print(list_mixed) # Output: [1, 'emre.me', 5.73, True]
list_nested = [['emre', 'dot', 'me'], [1], 5.73, True] # nested list
print(list_nested) # Output: [['emre', 'dot', 'me'], [1], 5.73, True]

Tuple is a DS that is ordered, immutable and hashable (if elements are hashable)

t = (1, 2, 3)
coords = {(0, 0): 'origin'}

# tuple unpacking
a, b = (10, 20)
for i, val in enumerate([10, 20, 30]):
	print(i, val)

Usage

when storing and accessing sequential data, temporarily storing objects
with lookup tables and inverse lookup tables because of their indexing property
in dynamic programming to cache answers to subproblems (Knapsack or Coin Change problems)
used by IO routines as buffers

Comparison

Array makes accessing elements is fast as long as you have the index, as opposed to Linked Lists where you have to traverse from the head
Tuples are faster than Lists for read-only data

Advantages

store multiple elements of the same type with one single variable name
accessing elements is fast as long as you have the index, as opposed to linked lists where you have to traverse from the head

Disadvantages

addition and removal of elements into/from the middle of an array is slow because the remaining elements need to be shifted to accommodate the new/missing element
- an exception to this is if the position to be inserted/removed is at the end of the array
for certain languages where the array size is fixed, it cannot alter its size after initialization
- if an insertion causes the total number of elements to exceed the size, a new array has to be allocated and the existing elements have to be copied over. The act of creating a new array and transferring elements over takes O(n) time.

Corner Cases

empty sequence
sequence with 1 or 2 elements or repeated elements
duplicated values in the sequence
be careful about index out of bounds
be mindful about slicing or concatenating arrays in your code, typically, slicing and concatenating arrays would take O(n) time
- use start and end indices to demarcate a subarray/range where possible

Implementation

Time Complexity
Operations	Worst case
	Array	Sorted Array
Access / Set item by index	`O(1)`
Access / Set item if we don’t know the index	`O(n)`	`O(log n)` using Binary Search
Delete item	`O(n)`
append()	`O(1)`
insert()	`O(n)`
extend()	`O(k)`
in	`O(n)`
pop() - last	`O(1)`
pop() - intermediate	`O(n)`
Access slice	`O(n)`
Set slice	`O(k + n)`
Delete slice	`O(n)`
sort()	`O(n log n)`

Space Complexity
	Worst case
Array/List/Tuple	`O(n)`

n is the number of elements in the array

Algorithms

Sorting

Patterns

Problems

Code

Resources

Array Data Structure | Interview Cake

Dynamic Array Data Structure | Interview Cake