What is the difference between an array and a list?

An array has a fixed size determined at creation. A list dynamically changes its size when elements are added or removed.

Access to array elements is done by index in O(1) time. Access to list elements can vary; for example, a singly linked list has access by index in O(n), while an ArrayList on average in O(1).

In an array, elements are stored in contiguous memory locations, which provides better cache performance. In a list, elements can be scattered in memory, linked by pointers.

Insertions and deletions in the middle of an array require shifting all subsequent elements, which can be costly (O(n)). In lists, these operations can be more efficient (e.g., linked lists O(1) if a pointer to the needed element is available, otherwise O(n) for search), but require pointer updates.

Arrays can store primitive types directly. Lists usually store references to objects (wrappers for primitive types).

// Array example
int[] array = new int[5];
array[0] = 10; // Access O(1)

// ArrayList example (Java)
import java.util.ArrayList;
import java.util.List;

List<Integer> list = new ArrayList<>();
list.add(10); // Adding O(1) on average
list.get(0); // Access O(1) on average

# Numpy array example
import numpy as np
array = np.array([1, 2, 3]) # Fixed size

# List example
list_data = [1, 2, 3]
list_data.append(4) # Dynamic size
list_data[0] # Access O(1)

Comparison:

Characteristic	Array	List
Size	Fixed	Dynamic
Index access	O(1)	Varies (often O(1) or O(n))
Memory	Contiguous	May be scattered
Insert/Delete	O(n) in the middle	Varies (can be O(1))
Data types	Primitives and objects	Usually object references