Linked list

Singly Linked list

In a singly linked list, we omit the prev pointer in each element
Address of the head node give us access of the complete list

Array VS linked list

How to create a linked list

Implement in C :
1.create a node first:

struct Node
{
    int data;
    struct Node* next;   
}* head;            

2.Put your element in the list:

void Put(int x)
{
    struct Node* temp =(struct Node*)malloc(sizeof(struct Node));  //create a node
    temp->data=x;  //put in the data
    temp->next=head;  //make next node as head
    head=temp;  //let head point to the next node
}

3.Traverse the linked list
psudocode first:

node* temp=A
while( temp -> link != NULL)
{
   temp=temp -> link;
   print" temp ->data
}

In C code:

void Display()
{
    struct Node* temp=head;
    printf("Current list is ");
    while(temp !=NULL)  //traverse
    {
        printf("%d",temp->data);
        temp=temp->next;
    }
    printf("\n");
}

4.Free memory
psudocode first:

node = head              
while node != null:     
    temp = node         
    node = node.next    
    free temp          
head = null 

In C code:

void Free(struct Node*head)
{
    struct Node*temp;
    while(head != NULL)  
    {
        temp=head;  
        head=head->next;  
        free(temp);  
    }
    head=NULL;  
}

View complete C code of create linked list here.

Inserting into a linked list

LIST -Insert (L, x)
next [x ]←head [L]
if head [L]≠NIL 
then prev [head [L ]]←x 
head [L]←x 
prev [x]←NIL

Implement in C:

void Insert(int data,int n)
{
    struct Node* temp1=(struct Node*)malloc(sizeof(struct Node));
    temp1->data=data;
    temp1->next=NULL;
    if(n == 1)  
    {
        temp1->next=head;  
        head=temp1;  
        return;
    }
    struct Node* temp2=(struct Node*)malloc(sizeof(struct Node));
    temp2=head;
    int i;
    for(i=0; i<n-2; i++)  
    {
        temp2 = temp2->next;
    }
    temp1->next = temp2->next;
    temp2->next = temp1;
}

View complete C code of insertion here.

Searching a linked list

List _ Search(L,  k)
x ←head[L]
   while x≠NIL and key[x]≠k
   do x←next[x]
return x

It takesΘ(n) time in the worst case.
**Implement in C: **

void Search(int n)
{
    while(head != NULL)
    {
        if(head ->data == n)
        {
            printf("element found\n");
            return;
        }
        head =head->next;
    }
    printf("element don't exist in this list");
}

View complete C code of Search particular element in linked list here.

Delete

Delete at nth position :

void Delete(int n)
{
    struct Node* temp1=head;  
    if(n==1)
    {
        head=temp1->next;   
        free(temp1);  
        return;
    }
    int i;
    for(i=0; i<n-2; i++)
    {
        temp1=temp1->next;  
    }
    struct Node*temp2 = temp1-> next;  
    temp1->next = temp2->next;  
    free(temp2);   
}

**View complete Delete code here. **

Sort linked list

We use merge sort to sort linked list
1.Split your list into two parts

void split(struct node* Node,struct node **front,struct node **back)
{
    struct node* a;
    struct node* b;
    if(Node==NULL || Node->next==NULL)
    {
        *front=Node;
        *back=NULL;
    }
    else
    {
        a=Node;
        b=Node->next;
        while(b != NULL)
        {
            b=b->next;
            if(b!= NULL)
            {
                a=a->next;
                b=b->next;
            }
        }
        *front=Node;
        *back =a->next;
        a->next= NULL;
    }
}

struct node* merge(struct node *a,struct node *b)
{
    struct node* list=NULL;
    if(a==NULL)
    {
        return b;
    }
    else if(b==NULL)
    {
        return a;
    }
    if(a->data > b->data)
    {
        list=b;
        list->next=merge(a,b->next);
    }
    else
    {
        list=a;
        list->next=merge(a->next,b);
    }
    return list;
}
void mergesort(struct node** Node)
{
    head=*Node;
    struct node* a=NULL;
    struct node* b=NULL;

    if(head==NULL || head->next== NULL)
    {
        return;
    }
    split(head,&a,&b);
    mergesort(&a);
    mergesort(&b);
    *Node=merge(a,b);
}

Complete code here