The singly linked list appears complex but is a quick fix to arrays and their computations. While arrays are good to use as a beginner, they take up a lot of memory use and are more efficient as static structures in C programming. A dynamic approach to lists lies in the simply linked list.
Singly linked lists operate with list elements stored in nodes. As the name implies, a singly linked list has a connection/link to another element in a list. This means that while it is also linear like an array, a singly linked list can form connections between elements at different locations.
A basic node in a linked list
What this type of dynamic linear data structure offers is the forward-only traversal of nodes that contain data and links to the next data address in memory, and terminates when the last entry is null (has no next address to point to). What it prevents is the need to reshuffle as much as occurs in the insertion and deletion of arrays.
The singly linked list is one of the more popular data structures, and each node tends to take the form below:
struct node
{
int data;
struct node *next_node;
} node;
The above takes some type of data and then the link to the next node which is of the same structure as the node itself. The single link ( struct node *next_node) is to an address that contains the data of the next node and the link or pointer to the next nodes own next nodes address. It is a recursive data type that results in a linear array with memory allocations in each node being uniform until the last node. The very first node of the list is determined by a pointer to its head node.
The space allocation of each new node that will be added to the list takes the casted form of:
void int(node *head)
{
int data;
node new_node;
new_node = (struct *node)malloc(sizeof(struct node));
// Or just:
new_node = malloc(sizeof(struct node));
}
Because a linked list only goes in one direction, its time complexity at worst is N elements. Having an array perform that would be a more complex working under the hood.
Why this structure is better than an array — Basics of how it works
While concise, an array does too much work on the RAM or memory of a computer. Basic operations on lists become heavier when the size of the project increases. The memory block in the heap allocated to an array is contiguous, meanwhile, a singly linked list can store related data in memory that is not traversed by virtue of being right next to each other.
An array on the other hand selects consecutive blocks of memory in the heap. However, when arrays have elements deleted or inserted, which is clean and specific, it results in the total movement of all elements before or after it to new memory locations so that there is no gap and they remain continuous. It makes for slow computing when there are large data sets to be worked on.
The non-contiguous memory allocation of singly linked lists
For instance, in deletion of a linked list element, this is what happens internally:
next_node = temp->next;
temp->next = next_node->next;
free(next_node);
Even when deleted, the list still goes on without restarting again to replace it and move things up.
Singly linked lists work by having each node (element of the linked list) containing its own data and the address of the next node it is linked to. This helps link the list in a forward only traversal, seeing as the links only point to the next and never the previous node. With arrays, forward and backward traversal is possible. When choosing the data structure to use it is good to keep this in mind.
Nodes carry the address of the next node in the previous node
Below is an example of forward traversal that would take us to the next node.
node.data -> 45;
node.next_node -> next_node;
The last node of a singly linked list has its address as NULL. That way the list stops on that last node.
node.data -> 666;
node.next_node -> NULL;
To have a look at how this works, you can look at this code.
Next time we will look at the movement you can get with this list type.