Data Structures and Algorithms

Linked Lists vs Arrays

This section will be easier to understand if you are familiar with the memory hierarchy on modern processors.

Performance considerations

Array based implementations of collections will generally show slightly better performance than linked list implementations. This will only be in the constant factor: scanning both arrays and linked lists is basically an O(n) operation. However, a number of factors contribute to slightly better performance of arrays:
  1. The address of the next element in an array may be calculated from a current address and an element size - both held in registers:
    (next)address := (current)address + size
    Both addresses may use a single register. Since no memory accesses are required, this is a single-cycle operation on a modern RISC processor.
  2. Using arrays, information is stored in consecutive memory locations: this allows the long cache lines of modern processors to be used effectively. The part of the cache line which is "pre-fetched" by accessing the current element of an array contains part of the next array element. Thus no part of the cache or the CPU<->memory bandwidth is "wasted" by not being used. In contrast, with linked list implementations:

Back to the Table of Contents
© John Morris, 1998