Why does memory contiguity (array) guarantee higher speed compared to a linked list?

Memory continuity in arrays provides higher speed compared to linked lists for several reasons:

1. Data locality:

   • Array elements are stored contiguously in memory, which improves CPU cache hits.
   • During sequential traversal of the array, data is loaded into cache in blocks, reducing delays.

2. Simple addressing:

   • Accessing an array element can be done in constant time using the formula: start_address + index * element_size.
   • In a linked list, accessing an element requires traversing links, which involves more operations and does not guarantee locality.

3. Less overhead:

   • Each element in a linked list contains an additional pointer, increasing memory usage and reducing data density.

Example:

// Array
arr := []int{1, 2, 3, 4, 5}
for i := 0; i < len(arr); i++ {
    fmt.Println(arr[i])
}

// Linked list
// To access the 5th element, you need to traverse 4 links

Thus, arrays are more efficient for sequential access operations and when performance is critical due to caching.