Creation and Traversal

Linked List Data Structure: Creation and Traversal in C Language

Here are some important points we learned about linked lists:

1. They are stored in non-contiguous memory locations.
2. Insertion and deletion in a linked list are more efficient compared to arrays.
3. Each element, called a node, holds both a value and a pointer to the next element.

We can now move on to coding them. I've attached the snippet below for your reference. Follow it while understanding the concepts.

Understanding the snippet below:

1. An element in a linked list is defined as a struct Node. It is designed to hold integer data and a pointer of data type struct Node*, as it needs to point to another struct Node.

2. We’ll create the linked list as illustrated below.

Figure 1: Illustration of the below implemented linked list.

3. We will always create individual nodes and link them to the next node via the arrow operator ‘→’.

4. First, we’ll define a structure Node and create two of its members: an int variable data to store the current node's value and a struct Node* pointer variable next to point to the next node.

5. Now, we can move on to our main() function and start creating these nodes. We’ll name the first node head and define a pointer to the head node with struct Node* head. Similarly, we will create pointers for the other nodes. Request the memory location for each of these nodes from the heap via malloc using the snippet below.

head = (struct Node *)malloc(sizeof(struct Node));

6. Link these nodes using the arrow operator and call the traversal function.

7. Create a void function linkedlistTraversal and pass the pointer to the head node into it.

8. In the linkedlistTraversal function, run a while loop while the pointer doesn’t point to NULL. Inside the loop, print the data of the current node and then update the pointer to point to the next node.

#include <stdio.h>
#include <stdlib.h>
 
struct Node
{
    int data;
    struct Node *next;
};
 
void linkedListTraversal(struct Node *ptr)
{
    while (ptr != NULL)
    {
        printf("Element: %d\n", ptr->data);
        ptr = ptr->next;
    }
}
 
int main()
{
    struct Node *head;
    struct Node *second;
    struct Node *third;
    struct Node *fourth;
 
    // Allocate memory for nodes in the linked list in Heap
    head = (struct Node *)malloc(sizeof(struct Node));
    second = (struct Node *)malloc(sizeof(struct Node));
    third = (struct Node *)malloc(sizeof(struct Node));
    fourth = (struct Node *)malloc(sizeof(struct Node));
 
    // Link first and second nodes
    head->data = 7;
    head->next = second;
 
    // Link second and third nodes
    second->data = 11;
    second->next = third;
 
    // Link third and fourth nodes
    third->data = 41;
    third->next = fourth;
 
    // Terminate the list at the third node
    fourth->data = 66;
    fourth->next = NULL;
 
    linkedListTraversal(head);
    return 0;
}

Code Snippet 1: Creating and traversing in a linked list Let’s check if it works all fine. Refer to the output below.

Element: 7
Element: 11
Element: 41
Element: 66
PS D:\Code>

Figure 2: Output of the above program

So, this was successfully creating and traversing through the linked list. We have more things to learn ahead, but before that, make sure you feel confident about the things we have covered so far.