Singly linked list using C

By Arjun Tyagi

In C programming Singly linked list is a linear data structure that has two parts one is the data part and the other is the link part that stores the address of the next node.

Linked List:

A linked list is a linear data structure that stores data. It is defined as a collection of objects called nodes. It has two parts one is data and the other is the link part. The link part stores the address of the next node.

 

 

                               

 

                                         Note: Head pointer stores address of the first element of a linked list

 

Why Linked-List:

                  To store data we already have an array data structure so why are we using a linked list?

When we use an array we have to allocate the space at compile-time and in contrast, Space is allocated in a linked list at run time. When we delete an element from an array its space gets wasted while in a linked list the memory gets free. In a linked list, each node points to the next one such that data can exist at scattered (non-contiguous) addresses, this allows for a dynamic size that can change at runtime.

 

Declaring a node:

struct node{
            int data;
            struct node* next;// stores address of next node//
};

 

Time and space complexity:

In a linked list we only have the address of starting element so we have to traverse from starting to the nth node. The time complexity is big-oh(n) or O(n).

We have 2 parts in a node so space will increase linearly that's why the space complexity is also big-oh(n) or O(n).

 

code C

#include 
#include 

struct node{
    int data;
    struct node* next;
};                    //declaring a node data-type//

struct node* head;

void insertion(int data){
    struct node* newnode=(struct node*) malloc(sizeof(struct node));//allocating memory for a node//
    newnode->data=data;
    newnode->next=NULL;
    
    if(head==NULL){  //list is empty //
        head=newnode;
       
    }
    else{
        struct node* temp=head;
        while(temp->next!=NULL){
            temp=temp->next; //traversing to the last element//
        }
        temp->next=newnode; //Storing the address of new node in previous node link part//
        
    }

}



void print(){
    struct node* temp=head;
    while(temp!=NULL){
        if(temp->next==NULL)
        printf("%d",temp->data);
        else
        printf("%d->",temp->data);
        temp=temp->next;
    }
}
int main() {
    
    insertion(1);
    insertion(2);
    insertion(3);
    insertion(4);
    
    print();
  // your code goes here
  return 0;
}

Output:

   

 

Explanation: