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

	Array	Linked list
Cost of accessing an element	Ο(1)	Ο(n) in average case
Memory requirement	fixed size	no unused memory , extra memory for pointer variables, more flexible
Cost of Inserting element at beginning	Ο(n)	Ο(1)
Inserting element at the end	① Ο(1) if array isn't full. ② Ο(n) if array is full.	Ο(n)
Inserting element at ith element	Ο(n)	Ο(n)

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