Arrays

Data structures

At a glance

An array stores a fixed number of elements of one type in an indexed sequence. In C#, int[] holds integers and values[0] accesses the first item. Indexing is O(1) because the runtime can calculate where an element is stored.

Operation	Typical cost	Why
Read or replace by index	`O(1)`	Direct indexed access
Search an unsorted array	`O(n)`	It may need to inspect every item
Insert in the middle	`O(n)`	Values must be shifted or copied
Visit all elements	`O(n)`	Every item is processed

Inspect array indexes

Try it yourself

Value

Indexes start at 0.

An index allows direct access to an element without scanning from the beginning.

Step by step

Allocate storage. new int[4] makes room for four integer values, initially set to zero.
Store a value. values[2] = 9 replaces the third item, not the second.
Read a value. values[2] returns 9 in constant time.
Traverse. A loop visits each item in order when the operation requires processing the entire collection.

int[] values = { 4, 8, 12, 16 };
Console.WriteLine(values[2]); // 12
values[1] = 10;
foreach (int value in values)
    Console.WriteLine(value);

#include <array>
#include <iostream>
std::array<int, 4> values{4, 8, 12, 16};
std::cout << values[2] << '\n'; // 12
values[1] = 10;
for (int value : values) std::cout << value << '\n';

Fixed arrays versus dynamic lists

A C# array has a fixed Length. List<int> can grow, but occasionally needs to allocate a larger backing array and copy its contents. Appending to a list is typically amortized O(1), not guaranteed constant time on each individual append.

When to use an array

Choose an array when the number of items is fixed or known, you need fast indexed access, or you are passing numeric data to an algorithm. Choose a list when its length must change often.

Arrays and dynamic lists are different

A fixed-length array stores elements in indexed positions. A dynamic list such as C# List<T> usually uses a resizable backing array, so it can append efficiently most of the time while occasionally reallocating a larger buffer. That does not make inserting at the beginning cheap, because subsequent elements still need to shift.

Index versus search

Knowing the index makes direct access constant-time in the usual model. Finding an arbitrary value may require scanning all elements, which is O(n). A sorted array can support binary search, but inserting into the middle can still cost O(n) because elements must move.

Practical choice

Arrays are useful when element count is fixed and predictable. Use a resizable list when the number of items changes. In performance-sensitive code, measure allocations and remember that collection APIs and memory layout influence real behavior.