Arrays, lists and linked lists

Big O figures here are explained in the Big O noteBig O notationHow run time or memory grows as the input grows.Opens in a new tab.

Array (System.Array, for example int[])

A fixed-size collection of elements of the same type, stored in a contiguous block of memory.

• Access (by index): O(1)
• Search (linear): O(n)
• Insertion or deletion at an arbitrary position (requires shifting): O(n)

Use it when the size of the collection is known in advance and fast indexed access is required, for example to store matrices and buffers.

List (System.Collections.Generic.List<T>)

A dynamic array that can grow or shrink in size. Internally it uses an array and resizes it when its capacity is exceeded.

• Access (by index): O(1)
• Search (linear): O(n)
• Add (at the end, amortized): O(1), and O(n) in the worst case when a resize is needed
• Insert or delete (at an arbitrary position): O(n)

Use it as a general-purpose collection when the number of elements is not fixed or changes often. It suits a list of items where order matters and indexed access is needed.

Linked list (System.Collections.Generic.LinkedList<T>)

A collection of nodes, where each node holds data and references (links) to the next node and, in a doubly linked list, the previous one. LinkedList<T> is a doubly linked list. Elements are not stored contiguously.

• Access (by index, or by searching for a value): O(n)
• Add or remove (at the beginning or end): O(1)
• Add or remove (at a known node): O(1), if you have a reference to the LinkedListNode<T>
• Add or remove (in the middle, by index): O(n), to find the node

Use it when you need frequent insertions or deletions at the beginning, the end, or the middle (with a known node), and indexed access is not a priority. For example, to implement stacks or queuesStack and QueueLast in, first out and first in, first out.Opens in a new tab, or to keep an ordered list with efficient add and remove at arbitrary known positions.