Today at work, we came across an interesting bug while debugging some code. We accidentally tried to access a linked list element using an index, as if it were an array. At first, the code seemed fine—it compiled without any errors. This was because the linked list was part of a structure defined as a pointer of pointers. However, the code didn’t work as expected when we ran it.

This experience reminded us how important it is to really understand how the tools we use actually work. Writing code that runs is good, but knowing why it works (or doesn’t) is even more important.

In this blog post, I’ll share what happened, explain the difference between arrays and linked lists, and talk about what we missed and why and how. Hopefully, it will help others avoid the same mistake and better understand these basic data structures.

Let’s start with a simple example.

#include <stdio.h>
#include <stdlib.h>
// Define the structure for a linked list node
struct Node {
int data;
struct Node* next;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to print the linked list
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("Linked list element: %d\n", temp->data);
temp = temp->next;
}
}
// Function to print the addresses of the linked list nodes
void printListAddresses(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("Linked list node address: %p\n", (void*)temp);
temp = temp->next;
}
}
int main() {
/* LINKED LIST*/
// Create linked list nodes
struct Node* head = createNode(1);
void* dummy1 = malloc(3000*sizeof(int)); // Allocate dummy memory block
head->next = createNode(2);
head->next->next = createNode(3);
head->next->next->next = createNode(4);
void* dummy2 = malloc(6000*sizeof(int)); // Allocate another dummy memory block
head->next->next->next->next = createNode(5);
// Print the linked list
printList(head);
// Print the addresses of the linked list nodes
printListAddresses(head);
// Free the allocated memory
struct Node* temp;
while (head != NULL) {
temp = head;
head = head->next;
free(temp);
}
/* ARRAY */
// Create an array of integers
int arr[5] = {1, 2, 3, 4, 5};
// Print the elements of the array
for (int i = 0; i < 5; i++) {
printf("Array element %d: %d\n", i, arr[i]);
}
// Print the addresses of the array elements
for (int i = 0; i < 5; i++) {
printf("Array element address %d: %p\n", i, (void*)&arr[i]);
}
return 0;
}
view raw array-vs-llist.c hosted with ❤ by GitHub

What do you think about the memory allocation at this point after we run this code above? Arrays are stored in consecutive memory addresses, while linked lists organize their elements non-sequentially (it does not have to be, but it also might be). Each node in a linked list includes a pointer that links it to the following node. Let’s see the memory allocation in a visual way:

Let’s talk about accessing the data in those structures…

In C, we all know, accessing an array element by its index is straightforward because arrays are stored in contiguous memory locations. However, linked lists do not store their elements contiguously; each element (node) contains a pointer to the next element. Therefore, you cannot access a linked list element directly by an index like you can with an array.

If you try to access a linked list element using an index (e.g., head[index]), it will result in a compilation error because the head pointer is not an array, and the indexing operator [] is not defined for linked list nodes. To access an element at a specific position in a linked list, you need to traverse the list from the head node to the desired position.

Then why we did not get any compilation error while trying to access linked list elements by index?

Let’s imagine a new structure that contains a pointer to a linked list (head). Here is an example:

#include <stdio.h>
#include <stdlib.h>
// Define the structure for a linked list node
struct Node {
int data;
struct Node* next;
};
// Define the structure that contains a pointer to the linked list
struct SomeClass {
struct Node* head;
};
// Function to create a new node
struct Node* createNode(int data) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = data;
newNode->next = NULL;
return newNode;
}
// Function to print the linked list
void printList(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("Linked list element: %d\n", temp->data);
temp = temp->next;
}
}
// Function to print the addresses of the linked list nodes
void printListAddresses(struct Node* head) {
struct Node* temp = head;
while (temp != NULL) {
printf("Linked list node address: %p\n", (void*)temp);
temp = temp->next;
}
}
int main() {
/* LINKED LIST */
// Create linked list nodes
struct SomeClass myObject;
myObject.head = createNode(1);
void* dummy1 = malloc(3000 * sizeof(int)); // Allocate dummy memory block
myObject.head->next = createNode(2);
myObject.head->next->next = createNode(3);
myObject.head->next->next->next = createNode(4);
void* dummy2 = malloc(6000 * sizeof(int)); // Allocate another dummy memory block
myObject.head->next->next->next->next = createNode(5);
myObject.head[0].data = 100;
myObject.head[1].data = 200;
myObject.head[2].data = 300;
printf("Address of myObject.head[0]: %p\n", &myObject.head[0]);
printf("Address of myObject.head[1]: %p\n", &myObject.head[1]);
printf("Address of myObject.head[2]: %p\n", &myObject.head[2]);
// Print the linked myObject
printList(myObject.head);
// Print the addresses of the linked list nodes
printListAddresses(myObject.head);
// Free the allocated memory
struct Node* temp;
while (myObject.head != NULL) {
temp = myObject.head;
myObject.head = myObject.head->next;
free(temp);
}
/* ARRAY */
// Create an array of integers
int arr[5] = {1, 2, 3, 4, 5};
// Print the elements of the array
for (int i = 0; i < 5; i++) {
printf("Array element %d: %d\n", i, arr[i]);
}
return 0;
}
view raw array-vs-llist_2.c hosted with ❤ by GitHub

As you can see here, everything is almost the same, except new “SomeClass” and its object “myObject”. Since we have a pointer to linked list in “myObject”… it’s easy to get confused about it. As shown in the code, if you try to access the data by index, the compilation will be OK, but your program does not run as expected, it will lead to random values or crashes. Because…

What is the correct way?

To correctly access an element at a specific index in a linked list, you need to traverse the list from the head node to the desired position… something like this:

// Update the data of the linked list nodes
    myObject.head->data = 100;
    myObject.head->next->data = 200;
    myObject.head->next->next->data = 300;

///////// OR /////////

// Function to get the data of the node at a specific index in the linked list
int getNodeDataAtIndex(struct Node* head, int index) {
    struct Node* temp = head;
    int count = 0;
    
    // Traverse the list until the desired index is reached
    while (temp != NULL) {
        if (count == index) {
            return temp->data;
        }
        count++;
        temp = temp->next;
    }
    
    // If the index is out of bounds, return -1 or handle the error as needed
    printf("Index out of bounds\n");
    return -1;
}