What is the difference between an array and a list?

Array - a fixed-size data structure, where elements of the same type are stored in contiguous memory cells. Access to elements is by index, which provides fast access O(1). Resizing requires creating a new array and copying elements.

Linked list - a variable-size data structure consisting of nodes, where each node contains data and a reference to the next node. Elements can be of different types. Access to elements is sequential O(n). Adding/removing elements at the beginning or end is fast (O(1)), in the middle - slower (O(n)).

Key differences:

Characteristic	Array	Linked list
Size	Fixed	Dynamic
Memory	Contiguous cells	Linked nodes
Access to elements	By index O(1)	Sequential O(n)
Adding/removing	Slow O(n) (in the middle)	Fast O(1) (at the beginning/end)
Data types	Usually of one type	Can be of different types