compact array

Complete

Succeeds: arrays

Summary

Compact array

implements list ADT

Operation	Method	Performance
`get(i)`	direct access	- , any element
`search(v)`	linear search	- , first element - , last element/not found
`insert(i, v)`	shift elements `[i,n−1]` right, place `v` at `i`	- , append to last - , insert at index `0`, shift the other elements
`remove(i)`	shift elements `[i+1,n−1]` left	- , remove last element - , remove first element, shift the other elements

Strengths

direct indexing , elements are contiguous
good if the maximum is known

Limitations

fixed size issue (if too small → overflow, too large → wasted space)
inefficient when the maximum is unknown and if insert and remove are used often

Concept

Data structure

contiguous storage with no gaps
operations must maintain compactness(no empty slots in between)

Variable-sized arrays

overcomes issues with fixed-sized arrays
once full, allocate a new array(2× larger), copy elements
eg. std::vector (C++), list (Python), ArrayList (Java)

the copying of elements into the new array is an amortized operation, it happens so infrequently(ideally) that we can consider it as

Application

Finding min and max

java

List<Integer> A = new ArrayList<>();

...

int min = Integer.MAX_VALUE, max = Integer.MIN_VALUE;
for (int x : A) { // n times
    if (x < min) min = x;
    if (x > max) max = x;
}
System.out.println("Min = " + min + ", Max = " + max);

Naive duplicate detection

java

List<Integer> A = new ArrayList<>();

...

boolean hasDuplicate = false;

for (int i = 0; i < A.size(); i++) { // n times
	for (int j = i + 1; j < A.size(); j++) { // n times
		if (A.get(i).equals(A.get(j))) {
				hasDuplicate = true;
				System.out.println("Duplicate found: " + A.get(i));
		}
	}
}

if (!hasDuplicate) {
	System.out.println("No duplicates found.");
}