Linked list

Before marching on to this topic you need to learn pointers and dynamic memory allocation.

Why Linked list?

• Provides dynamic memory allocation.

• Insertion and deletion operations are easier.For insertion at beginning of array we have to move all the n elements.For deletion at beginning of array we need to shift all n elements in front by 1 position.

• Provides efficient memory utilization.

& much more………

What is a singly linked list?

A data structure comprising of nodes which store data and a pointer to the next node.

A node comprises of the following fields.

Data field where data is stored.

Next pointer : This pointer points to the next node of the list.

head is a pointer pointing to the 1st node. 
next pointer of the last node points to NULL.

Lets say we have an organization in which some employees work and you have to store their details.You should also be able to add,delete and modify employee details.For better understanding,I have taken only employee id in employee details.Here we will treat a employee as node.

Building a singly linked list

1.  Declare a node structure

typedef struct node
{
        int id;
        struct node* next;                     //for storing address of next node
}node;

Note:Members of structure can be accessed via pointer using ->

2.  Create a linked list

node* create()
{
    node* head;
    head=(node*)malloc(sizeof(node));         /*allocating memory to node 
                                                and head is pointing to it  */
   
    printf("\nEnter employee id ");
    scanf("%d",&head->id);

    head->next=NULL;
    return head;
}

3.  Append a node to a linked list

node* append(node* head)
{
    node* curr = (node*)malloc(sizeof(node));  //allocate memory for current node

    node* prev=head;

    printf("\nEnter employee id ");
    scanf("%d",&curr->id);

    while(prev->next!=NULL)                    //traverse the list and go to the last node
        prev=prev->next;

    prev->next=curr;                          /*establish the link between last node
                                               (pointed by prev) and curr node   */

    curr->next=NULL;

    return head;
}

4.  Modify a node of a linked list

node* modify(node* head)
{
    node* curr=head;
    int eid,found=0;

    printf("\nEnter Eid of employee whose data is to be modified ");
    scanf("%d",&eid);

    while(curr!=NULL)                        //traverse list in search of eid
    {
           if(curr->id==eid)
           {
              found = 1;
              break;
           }
           else
              curr=curr->next;
    }
    if(found == 1)                           //eid is found
    {
            printf("\nEnter employee id ");
            scanf("%d",&curr->id);
    }
    else
            printf("\nEmployee id not found");

    return head;
}

5.  Delete node from a linked list

node* del(node* head)
{
    node *prev,*curr=head,*last;
    int eid;

    printf("\nEnter employee id to be deleted ");
    scanf("%d",&eid);

    if(curr==NULL)
           return NULL;

    else if(curr->id==eid && curr->next==NULL)               //only 1 node
           head = NULL;

    else if(curr->id==eid && curr->next!=NULL)               //1st node
           head = head->next;

    else
    {
           while(curr!=NULL)                                 //search eid
           {
                if(curr->id==eid)
                    break;
                else
                {
                    prev=curr;
                    curr=curr->next;
                }
           }

           if(curr!=NULL)                    //if eid found
                prev->next=curr->next;       //establish the link between prev & node ahead of curr
    }

    if(curr!=NULL)                           //if eid found
           free(curr);
    else
           printf("\nEmployee id not found");

    return head;
}

Here curr  = points to the node to be deleted

prev = points to the node just previous to the current node

Suppose we have

We have to delete node pointed by curr,so we need to establish link between node 1 and node 3.

How?

curr->next stores address of node 3.If we assign curr->next(i.e address of node 3) to prev->next then prev->next would point to node 3 and hence link would be established between node 1 and node 3.Then we would free memory pointed to by curr.

Diagram after deletion of node 2.

6.  Display linked list

void display(node* head)
{
    node* curr=head;

    if(curr==NULL)
         printf("\nList is empty");
    else
    {
         printf("\n");
         while(curr!=NULL)
         {
              printf("%d---",curr->id);
              curr=curr->next;
         }
    }
}

More

Reverse a linked list

Merge linked lists

Doubly linked list

Circular linked list