Coders Packet

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.

 

 

                                Linked list

 

                                         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:

    output

 

Explanation:

                                      exp1

 

 

                                    exp 2

           

 

Download Complete Code

Comments

No comments yet