Linked List Part 2 || Simple Linked List || Detailed Explanation || Implementation in C

Simple Linked List (or whatever you want to call it linear or singly linked list) is a dat a structure where we store set of data linearly in a way very much different from an array.
Arrays have a continuous set of memory occupied so the data or each element can be accessed easily by the index of array.
To make it clearer :
Let me say an array starts at address 0x32552, representing index 0 of the array.
The indexes in an array are like 0,1,2,3,..., n-1
Where n is the size of array.
So index 1 will be at 0x32553, index two will be at 0x32554, and similarly index n-1 will be (0x32552 + n-1), 
But linked list is NOT like that. The nodes of linked list are scattered randomly in the memory as we dynamically allocate memory for each node. You can see the discrete memory addresses in this image

We need something different kind of variable to store the memory address of these nodes. For this we will make use of concept of pointers in C language.
NOTE : DISCUSSION OF POINTERS WILL MAKE OUR POST TOO LONG AND OFF TOPIC SO TO UNDERSTAND THE CONTENT AHEAD PLEASE MAKE SURE THAT YOU UNDERSTAND POINTERS.
Telling about pointers in short they are  variable that store memory address of another variable.
Along with pointers we also need variable to store data. There has to be a pointer for each node and a data variable for each node.
Making many different variables will be a tedious task so we will take advantages of structures in C language ( C++ has concept of classes to achieve the same thing) 
We will create our own structure data type called Node and this data type will have properties like 
1. pointer variable called nextAdd to store address of next node in liked list
2. variable named data to store data for our current node

Every time we create a variable of struct Node it will also have the above to properties
( If you are famaliar with classes then every time we create object of class or instance of class then the object holds the propwrties of the class) 
Structure has similar concept NOT EXACTLY SAME and is implemented in an slightly different way. 
BEFORE YOU MOVE AHEAD IT WOULD BE BETTER TO BRUSH UP YOUR KNOWLEDGE ON STRUCTURES so that you understand the implementation in better way.
Now, we will use structures to create our custom data type which will have these properties :

int data; // to store interger data.
struct Node *nextAdd; // to sore address of the next node
  

Let's create a structure with these properties defined in it : 

struct Node{
  int data;
  struct Node *nextAdd;
};

We have named out printing function as traverse because wht it basically does is traversing through the loop

We will initialize the struct Node in main function by using dynamic memory allocation malloc() :

  // creating node variables of Node data type
  struct Node *head; // head => zero position
  struct Node *one;
  struct Node *two;
  struct Node *three;
  struct Node *four; // last node
  
  // allocating dynamic memory to nodes in heap
  head = (struct Node*) malloc(sizeof(struct Node));
  one = (struct Node*) malloc(sizeof(struct Node));
  two = (struct Node*) malloc(sizeof(struct Node));
  three = (struct Node*) malloc(sizeof(struct Node));
  four = (struct Node*) malloc(sizeof(struct Node));
  
  // setting values and linking them
  head -> data = 2;
  head -> nextAdd = one;
  
  one -> data = 8;
  one -> nextAdd = two;
  
  two -> data = 3;
  two -> nextAdd = three;
  
  three -> data = 6;
  three -> nextAdd = four;
  
  four -> data = 10;
  four -> nextAdd = NULL;

Here we first declare pointer variables head, one, two, three, and four of type struct Node * which represent the nodes of our linked list. 

Then we dynamically allocate memory for these nodes

 by using malloc function. We dynamically allocated size of Struct node for each node variable using sizeof() function.

Because the nodes are pointers we access their structure variables and assign a value for data of each node and link the Node head with Node one by initializing head->nextAdd with the required next node i.e., one in this case. Similarly we initialize nextAdd of nodes one, two and three with their respective next nodes. As the four is the last node we initialize four->nextAdd = NULL;

It's time to create a function now to print the complete linked list :

To print the linked list we need to give the  address of the first node to our function and then our function will automatically find the address of the next node and its next node and so on...

If function has the address of head node then it can also access the  data variable of structure and thus we need to pass only one parameter for the function i.e., struct Node *pointer

The logic for function will go line this :

Pseudo Code
while (pointer->nextAdd) != NULL { printf(pointer->data) // re-assign pointer to next node pointer = pointer->nextAdd; }

    

void traverse(struct Node *pointer){
  printf("head -> ");
  while(pointer != NULL){
    printf("[%d] -> ",pointer -> data);
    pointer = pointer -> nextAdd;
  }
  printf("NULL");
}

We call our function traverse() because our function because it basically does traversal through the linked list starting from the first node and prints data value in each node.

 printf("head -> "); and -> being printed to make the output look like a linked list. 

While calling this main function we will pass "head" as the argument because we need to pass the 1st node to the fuction as parameter which is the head.

traverse(head);

Here is the complete set of code for creating a linked list and traversing through it in C language :

#include <stdio.h>
#include <stdlib.h>



struct Node{
  int data;
  struct Node *nextAdd;
};

/*
  SAMPLE LINKED LIST :
  
 
egAddr.   101        285        121        662        358
        |2|285| -> |8|121| -> |3|662| -> |6|358| -> |10|NULL| -> NULL
  names   head       one        two        three      four              
  
  */

// traversing through linked list
void traverse(struct Node *pointer){
  printf("head -> ");
  while(pointer != NULL){
    printf("[%d] -> ",pointer -> data);
    pointer = pointer -> nextAdd;
  }
  printf("NULL");
}

int main()
{
  // creating node varianles of Node data type
  struct Node *head; // head => zero position
  struct Node *one;
  struct Node *two;
  struct Node *three;
  struct Node *four; // last node
  
  // allocating dynamic memory to nodes in heap
  head = (struct Node*) malloc(sizeof(struct Node));
  one = (struct Node*) malloc(sizeof(struct Node));
  two = (struct Node*) malloc(sizeof(struct Node));
  three = (struct Node*) malloc(sizeof(struct Node));
  four = (struct Node*) malloc(sizeof(struct Node));
  
  // setting values and linking them
  head -> data = 2;
  head -> nextAdd = one;
  
  one -> data = 8;
  one -> nextAdd = two;
  
  two -> data = 3;
  two -> nextAdd = three;
  
  three -> data = 6;
  three -> nextAdd = four;
  
  four -> data = 10;
  four -> nextAdd = NULL;
  
  traverse(head);
  return 0;
}
  
  
 

Output
head -> [2] -> [8] -> [3] -> [6] -> [10] -> NULL

Let's meet in the next post to discuss some operations on linked list, till then...

#KeepLearningKeepGrowing