English
Menu

Array vs Linked List: Access, Insertion, Cache and Complexity

An array stores elements of the same type next to each other in memory with no gaps, so the position of any element can be computed from its index and read or written in constant time. A linked list is a data structure in which each element holds a value and a pointer to the next element, and the elements are linked by following those pointers, so they can sit in separate places in memory. An array reads fast, but inserting or deleting in the middle means shifting the elements behind it. A linked list can insert or delete just by changing pointers once the position is known, but reading the i-th element means walking from the head. The basic rule: use an array when you mostly read by index, and a linked list when you often insert or delete at known positions.

AspectArrayLinked list
Memory layoutElements sit next to each other in one contiguous blockElements are scattered and linked by pointers
Reading the i-th elementO(1): the address is start address + i × element sizeO(n): follow the pointers i times from the head
Searching for a valueO(n) linear search if unsorted; O(log n) with binary search if sortedO(n) even if sorted; binary search cannot be used because there is no way to jump to the middle
Inserting or deleting in the middleO(n): the elements behind it are shifted one by oneO(1) if the position (the preceding element) is known; only pointers change
Appending at the endO(1) if there is free space; a dynamic array that doubles its capacity occasionally copies everything but is O(1) on average (amortized)O(1) if a pointer to the last element is kept
ResizingA fixed-size array's size is set when it is created; growing it means allocating a new block and copyingSpace is allocated per element, so it grows only as much as needed
Memory useOnly the elements themselves (a dynamic array keeps some spare capacity)Extra space for a pointer per element (two in a doubly linked list)
Cache friendlinessGood: elements are contiguous, so sequential reads make good use of caches and prefetchingPoor: elements tend to be scattered, so even the same O(n) traversal can be much slower than with an array
Typical usesTables read and written by index, matrices and images, data to sort or binary-search, implementations of stacks and queuesSequences with frequent insertion and deletion, chaining in hash tables, free-space management

Figures are typical orders of magnitude and vary by process generation and product.

When to use which

Array
When elements are mostly read and written by index or read in order from the start. Because caches work well with them, arrays (including dynamic arrays) are faster in many situations on today's computers.
Linked list
When there are many insertions and deletions in the middle and you already hold a pointer to the position. Because elements are relinked without moving, it is also used when element addresses must not change.

FAQ

Linked-list insertion is O(1), so why are arrays sometimes faster in practice?

For two reasons. First, if the insertion point has to be found from the head, that search costs O(n), so the whole operation is O(n), the same as an array, even though the insertion itself is O(1). Second, shifting array elements is a copy of contiguous memory that makes good use of caches and is very fast, whereas walking a linked list reads scattered addresses one element at a time and often misses the cache. Time complexity describes how cost grows as data grows; actual speed should be measured.

How do singly and doubly linked lists differ?

In a singly linked list each element has only a pointer to the next element, so it can be walked only from front to back. A doubly linked list also has a pointer to the previous element, so it can be walked backward too, and given a pointer to an element, that element can be deleted in O(1). In return, each element has one more pointer, and more pointers must be updated.

What is a dynamic array?

An array that can change size: when it runs out of capacity, it allocates a larger block and copies everything over. If the capacity doubles each time, the total number of copies is only about equal to the number of elements, so appending at the end is O(1) on average. Reading by index is O(1), just as with an ordinary array.

Check your understanding

Compared with an array, which is a correct description of a linked list (a list in which each element holds a pointer to the next element)?

  1. AIf the element just before the insertion point is known, a new element can be inserted just by changing pointers without moving other elements, but reading the i-th element requires following the list from the front
  2. BThe position of the i-th element can be computed, so any element can be read in constant time, O(1)
  3. CThe elements are stored contiguously in memory, so caches and prefetching work well when reading them in order
Show answer and explanation

Answer: A. If the element just before the insertion point is known, a new element can be inserted just by changing pointers without moving other elements, but reading the i-th element requires following the list from the front

In a linked list, once the position is known, insertion and deletion only require rewriting the neighboring pointers, which takes O(1). Reading the i-th element, however, requires following i pointers from the front, which takes O(n). An array can compute the address of the i-th element from its start address and element size, so it reads any element in O(1), but inserting in the middle takes O(n) to shift the following elements. Also, because array elements are contiguous, caches and prefetching work well, whereas the nodes of a linked list tend to be scattered in memory, so even an O(n) traversal can be much slower.

A dynamic array, when an element is added while it is full, allocates a new area with twice the capacity and copies all elements into it. If 1,000 elements are added one at a time to an empty array of capacity 1, how many element copies are made in total?

  1. A10
  2. B1,023
  3. C499,500
Show answer and explanation

Answer: B. 1,023

The capacity doubles each time it fills up, going 1, 2, 4, …, 512, and each time all current elements are copied, so the total number of copies is 1 + 2 + 4 + … + 512 = 1,023. For 1,000 additions that is about one copy per element, so the cost per addition is constant on average: amortized O(1). If the capacity grew by only 1 each time, the copies would total 1 + 2 + … + 999 = 499,500, which is O(n²). 10 is the number of reallocations, not the number of elements copied.

Which correctly compares chaining (linking the elements at the same position into a linked list) and open addressing (finding another free position within the table) as ways to resolve hash table collisions? The load factor is the number of stored elements divided by the table size.

  1. AChaining can store elements even when the load factor exceeds 1, but open addressing cannot store more elements than the table size, and its number of probes rises sharply as the load factor approaches 1
  2. BOpen addressing has no collisions, so a search always takes one probe regardless of the load factor
  3. CWith chaining, the search cost stays the same however high the load factor becomes
Show answer and explanation

Answer: A. Chaining can store elements even when the load factor exceeds 1, but open addressing cannot store more elements than the table size, and its number of probes rises sharply as the load factor approaches 1

Chaining links elements at the same position into lists, so it can store more elements than the table size, but the average list length grows in proportion to the load factor and so does the search cost. Open addressing stores everything inside the table, so it can hold at most as many elements as the table size, and the number of probes to find a free slot rises sharply as the load factor approaches 1. With either method, it is usual to enlarge the table and reinsert all elements (rehash) once the load factor exceeds a chosen limit, such as about 0.5 to 0.75. Collisions also occur in open addressing; it handles them by looking for a free position.

  1. For a hash table with many elements kept at a load factor of about 0.5, which is the most appropriate reason that open addressing with linear probing tends to be faster than chaining (linking elements with linked lists)?
  2. Which is a prerequisite for using binary search, which compares the target with the middle element and halves the search range each time?

Practice Data Structures and Algorithms questions

Key terms explained

Array
A data structure that stores values of the same type in sequence and identifies each element by an index. Because the elements are stored contiguously in memory, the position of any element can be computed from its index, so any element can be read or written in constant time. Some languages start indices at 0, while some notations start them at 1.
Linked list
A data structure in which each element holds a value and a pointer to the next element, and the elements are linked by following the pointers. Once the position is known, insertion and deletion are O(1) pointer changes, but reading the i-th element requires walking from the front, O(n). The elements tend to be scattered in memory, so caches work less well than with arrays.
Pointer
A variable whose value is the memory address of a variable, an array element, a function or other object. In C it is declared as in int *p; &x yields the address of x, and *p reads or writes the object p points to. Adding an integer to a pointer advances it in units of the size of the pointed-to type. In most expressions an array name is converted to a pointer to its first element, so a[i] means the same as *(a + i). A pointer value that points nowhere is called a null pointer.
Time complexity (Big-O notation)
A description of how the work (time complexity) or memory (space complexity) an algorithm needs grows with the number of data items n. It is written in Big-O notation, such as O(n), O(n log n) or O(n²), dropping constant factors and lower-order terms.
Binary search
A search method for sorted data that compares the target with the middle element and halves the search range each time. It finds a value among n items in at most ⌊log₂ n⌋ + 1 comparisons, so its complexity is O(log n). The data must be sorted.
Hash table
A data structure that computes a storage position from a key with a hash function, allowing search, insertion and deletion in O(1) on average. Collisions, where different keys map to the same position, are handled by chaining or open addressing.
Spatial locality
The tendency to access addresses near one just accessed, as when reading an array in order. It is why caches fetch data a whole cache line at a time.

Related comparisons