Practice: Get Element at Position

Introduction

One of the challenging aspects of implementing a generic linked list is to write a proper allocGenericNode function, which works correctly regardless of the data type.

The other aspect is to figure out how to abstract the concrete handling of data types to keep the linked list functions generic. Our current approach is to pass function pointers as arguments to customize the code behavior for each data type.

After these things are in place, working with generic linked lists is similar to working with regularly linked lists. For this reason, we won’t insist on implementing many functions using generic linked lists, as it would be almost the same work as we did for regular lists.

However, to practice a bit, let’s try to write a function that returns the node’s value field at a given position, getElementAtPosition.

The getElementAtPosition function

This function will receive a generic linked list and an index. It must return the value of the element present at that index if it’s valid. If the index isn’t valid, it should return NULL.

The index 0 corresponds to the first element inside the list.

The function has to be generic, so we must be careful how we return the data. We cannot return a concrete type like int or char* because we don’t know what type to return.

For example, for the input:

list = [1, 2, 3, 4, 5]
position = 3

Executing getElementAtPosition(list, position) must return 4, which is the element with the index 3 inside the list [1, 2, 3, 4, 5] since the index of the first element is 0.

Solution

In the case of an array, it’s easy to return the element at a given position. Since the array is contiguous in memory, we can add an offset to the start address to find the required element.

However, linked lists are not contiguous. To find the ith position, we must iterate over the list and count positions. Notice this being implemented in lines 15, 22, and 23.

We can return the value pointer once we find the correct position (line 17).

As for validating the data, we must check if the list isn’t NULL or if the position isn’t in the range of [0, len(list) - 1]. We check the list and if the position is smaller than 0 in line 7.

Notice that we never explicitly check if the position is bigger than len(list). We could do it, but it isn’t necessary. If the while loop finishes without return, it means the position is outside the list. Then, the code after the while loop can execute only if position > len(list). In this case, we return NULL since such a position isn’t valid (line 26).