An In-Depth Understanding of Memory and Pointers in C/

...

/

Linked Lists vs Arrays from a Memory Point of View

Linked Lists vs Arrays from a Memory Point of View

Learn key differences in the memory representation of linked lists and arrays.

We'll cover the following...

Introduction

We reiterate that the purpose of this chapter isn’t to teach data structures. The purpose is to practice memory allocations, pointer manipulation, and correct memory management. It just so happens that implementing linked lists is a perfect way to achieve our goal.

Now we’ll discuss a few differences between arrays and lists from a memory point of view. It’s by no means a general comparison between the two data structures. We’re focused on the memory aspect.

Contiguity

Arrays are continuous

We allocate arrays as a contiguous memory block. This behavior is good news because the allocation code is simple, and the cache spatial locality principle is respected.

Let’s quickly allocate an array and print the addresses of each element.

Press + to interact
#include <stdio.h>
#include <stdlib.h>
int main() 
{
	int* arr = calloc(5, sizeof(int));
	for(int i = 0; i < 5; i++)
	{
		printf("&(arr[%d]) = %u\n", i, (arr + i));
	}
  	return 0;
}

Here’s a possible output:

&(arr[0]) = 14721040
&(arr[1]) = 14721044
&(arr[2]) = 14721048
&(arr[3]) = 14721052
&(arr[4]) = 14721056

As we can see, the first address is 14721040, the second is 14721040 + 4 = 14721044, and so on. All the elements are in the same memory area, one after the other.

When we want to read arr[0], we’ll bring arr[0] inside the cache to speed up further accesses. We’ll also bring the adjacent elements arr[1], arr[2], and so on. How many elements we bring depends on the configuration of the cache. Later, when we access arr[2] and arr[3] for the first time, they’ll already be in the cache, and we won’t have to go to the RAM to read ...