Practice: Get Element at Position
Practice generic linked lists by writing functions operating on them.
We'll cover the following
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 i
th 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).
Get hands-on with 1200+ tech skills courses.