Linked list memory allocation

Choosing the right way to store your data is one big task to do. There are many data structures out there and not a single data structure is best for every problem. The best you can do is identify the usage of every data structure and determine which one is the most effective for a specific case.

Linked list has always been a nightmare for me and my peers when learning about data structures. It sometimes bothered me why even this data structure exists since we have already had the simple array. Well, if you think as I did, then you havent fundamentally understand it. So, we will jump straight in and answer the million-dollar question: what on earth is a linked list?

What is Linked List?

The linked list is categorized as a linear data structure. A Linear data structure has data elements arranged sequentially and each member element is connected to its previous and next element. We may not realize but the well-known array or list is also categorized as a linear data structure. Linear data structures are best used for storing sequential data [ordered data].

Dynamic Programming

But what is the problem with the simple array? Array declaration is needed before the compilation because the compiler needs to know how much memory space is needed to be set aside for every variable. Hence, when we declare the array size at the beginning, we cant change the array size while the code is running. The naive solution would be picking a big number for the array size, but this would be inefficient and a waste of memory.

This is where dynamic memory allocation comes in! Firstly, we need to understand that there are 2 types of memory allocation, static and dynamic. Elements in static memory are allocated in the stack such that the declared variables are stored in the respective order contiguously. On the other hand, elements in dynamic memory are allocated in the heap. Different from a stack, in heap, you have no idea where the memory has been allocated, for each request you make, a randomly selected block of memory will be assigned to store the value.

Luckily, in C, they provide the most useful function for dynamic memory allocation, malloc[ ]. Here is the syntax of this function.

void *malloc [size_t size]

This function reserves the size of required bytes for the requested variable/ structure and returns the allocated address in the heap. If the requested size of memory isnt available, the function will return NULL. There are some other functions that support dynamic memory allocation, i.e. calloc[ ] and realloc[ ], but we will not discuss deeper into those functions.

Structure of Linked List

A linked list is a data structure that is based on dynamic memory allocation. Basically, Linked List is made of nodes and links. We can create a simple structure that consists of a container to store the value and the pointer to the next node.

In the ListNode structure, the int item is declared to store the value in the node while struct _listnode *next is declared to store the address of the next node. If it is the last node, then the next will point to NULL.

Nice! Now, we can track the second node by the first node, as well as the third node by the second node. But how do we keep track of the first node? Without the address of the first node, the second and third nodes wont be accessible. Therefore, we will introduce the head pointer. The head pointer is not a node, instead, it is a pointer that stores the address of the first green block which is the first node.

Linked List Example

We have finally defined the structure of Linked List and how it works. Now, lets start the coding part. I will guide you through a simple code.

Here is the result of the Linked List after executing the code.

As you can see from the code, Linked List relies heavily on the malloc[] function to allocate some memory for new nodes dynamically. The reason why we need to use the temporary variable is that we dont want to change the address stored in the head pointer. Subsequently, after this code executes, the head pointer will still point to the first node whereas the temporary pointer will point to the last node.

Linked List in Python

BONUS: Linked List can also be created in other programming languages, such as Python, Java, and etc. Although Python doesnt have pointer or structures, Classes can help Python programmers to make Linked List.

We can create 2 classes. The first one is the ListNode class that is used for storing the value and the next pointer. The second one is the LinkedList class that is used similarly as the head pointer in C. So, here is a simple code for applying Linked List in Python.

Final Words

Linked list is one of the most important data structures in Computer Science. It is the basic foundation to create other data structures such as Stack and Queue. The structure of a linked list is also not limited to the simple linked list [the one we discuss in this article]. There are more complicated types of Linked List, including Doubly Linked List and Circular Linked List, in order to suit the needs accordingly.

Start learning different data structures to help you choose the right data structure[or even the combination of them!] for tackling a specific problem.

Regards,

Juan Samuel Sugianto