Managing Non-linear Data Structures with Pointers in C

Whenever we’re working with data that is not arranged in a sequential or linear manner, a good idea is to use structures such as trees, graphs and linked lists given that their size and structure can vary dynamically based on program inputs and operations. But if these structures are non-linear how would we link them? I mean, how would we reference one to the other? In linear structures that is easy, all we have to do is use an index to connect them. But how does that go with non-linear structures? The answer is: pointers!?

In C, pointers are structures that keep addresses as references. They are really useful in helping us allocate memory dinamically. In a nutshell, pointers will basically point (sic) ?to the address where a given variable in the heap memory is. Each structure of our program, in this case, will have a pointer that tells us where this given structure is located. It feels awkward, right? At first glance, it is. But it is important to understand the role that pointers play here: they need to keep the address of a structure as? reference otherwise the structure would get lost in the heap memory. Remember we are talking about non-linear structures, they don't follow a logic order such as linear structures (arrays, strings, matrices, vectors and others). If a linked list, for example, did not use pointers the purpose of the linked list would lose its fundamental mechanism - which is linking nodes together. Without pointers, there would be no mechanism to store or reference these memory addresses, making it impossible to manage dynamic memory allocation. To better understand how it works, see diagram below: there will always be an initial Pointer which will point to the first structure on our program. The first structure, then, will hold another pointer as a reference to the next structure, and so on.

How would we do all these in C? Let’s take the implementation of a linked list as an example.

The code defines a structure example with two float members (`x` and y) and a pointer to the next structure, allowing the creation of a linked list. A global pointer pointerList is initialized to NULL to act as the head of the linked list.

The add function dynamically allocates memory for a new node, sets its x and y values, points its next to the current head of the list, and updates pointerList to point to this new node. In the main function, add is called three times to add nodes with values (1, 5), (2, 7), and (5, 3). The x values of the nodes are printed, starting from the head and traversing through the next pointers, resulting in the output of the x values of the nodes in reverse order of their addition: 5, 2, and 1.

The linked list is built by each add operation inserting a new node at the beginning, updating pointerList to the new node, ensuring the new node points to the previous head, thus maintaining the linked structure.

Let’s highlight the importance of pointers in non-linear structures:

• Dynamic Memory Allocation: Pointers enable dynamic memory allocation, allowing structures to be created and resized as needed during program execution. This is essential for creating flexible data structures whose sizes are not known at compile time, such as linked lists and trees.

• Efficient Memory Usage: Pointers enable efficient memory usage by allowing data structures to be allocated only when needed and deallocated when no longer required. This helps in optimizing memory usage, especially in resource-constrained environments.

• Indirection: Pointers provide a level of indirection, allowing access to complex data structures indirectly through references rather than directly accessing the structure itself. This facilitates manipulation and traversal of data structures without having to copy or move large amounts of data.

• Passing by Reference: In C, function parameters are passed by value by default, meaning a copy of the data is passed to the function. Pointers allow passing parameters by reference, enabling functions to modify the original data directly, including structures, without creating copies.

• Dynamic Data Structures: Pointers are essential for implementing dynamic data structures like linked lists, trees, and graphs, where the structure of the data changes frequently during program execution. Pointers enable linking nodes in linked lists, traversing tree structures, and connecting vertices in graphs.

• Memory Management: Pointers allow explicit memory management, including allocation and deallocation of memory blocks. This level of control is crucial for preventing memory leaks and managing memory efficiently, especially in long-running programs.

Summing up, pointers are the heroes when it comes to handling non-linear data structures in C. They let us dynamically allocate and manage memory, which is crucial for structures like linked lists, trees and graphs. Pointers keep track of where everything is stored in memory, making it possible to link nodes in a list, traverse trees, and connect parts of a graph. Without pointers, we’d lose the ability to efficiently manage and use these dynamic structures, making our programs far less flexible and efficient. So, while they might seem tricky at first, pointers are what make working with complex, non-linear data in C possible.