Linked List as an abstract data type

Declaring Linked List

Each node requires two data types, an int, char, float etc data type to store the value and a pointer to the next node to store the address of the node to which this node is pointing to.

struct Node{
    int data;
    struct Node *next;
}*first=NULL,*second=NULL,*third=NULL;

Initialising First Node and Array to Linked List Conversion

Initialising first node and converting array a to a linked list.

void create(int a[],int n){
    struct Node *last,*t;
    int i;
    first = (struct Node*)malloc(sizeof(struct Node));
    first->data=a[0];
    first->next=NULL;
    last = first;
    for(i=1;i<n;i++){
        t=(struct Node*)malloc(sizeof(struct Node));
        t->data=a[i];
        t->next=NULL;
        last->next=t;
        last=t;
    }

}
void create2(int a[],int n){
    struct Node *last,*t;
    int i;
    second = (struct Node*)malloc(sizeof(struct Node));
    second->data=a[0];
    second->next=NULL;
    last = second;
    for(i=1;i<n;i++){
        t=(struct Node*)malloc(sizeof(struct Node));
        t->data=a[i];
        t->next=NULL;
        last->next=t;
        last=t;
    }

}

Displaying values of Linked List

Printing or displaying values of linked list till the last node is null.

void display(struct Node *p){
    while(p!=NULL){
        printf("%d",p->data);
        p=p->next;
    }
}

Recursively displaying values of Linked List

void Rdisplay(struct Node *p){
    if(p!=NULL){
        printf("%d",p->data);
        Rdisplay(p->next);
    }
}

Reverse display values in Linked List

void reverseDisplay(struct Node *p){
    if(p!=NULL){
        reverseDisplay(p->next);
        printf("%d",p->data);
    }
}

Counting number of Nodes in Linked List

int count(struct Node *p){
    if (p==NULL) return 0;
    return 1+count(p->next);
}

Sum up all the values of Linked List

int sum(struct Node *p){
    if (p==NULL) return 0;
    return sum(p->next)+p->data;
}

Max value node in Linked List

int max(struct Node *p){
    int max = INT32_MIN;
    while (p!=NULL)
    {
      if(p->data>max){
          max=p->data;
      }
    }
    return max;
    
}

Recursively finding max value node in Linked List

int Rmax(struct Node *p){
    int x=0;
    if(p==NULL) return INT32_MIN;
    x=Rmax(p->next);
    if(x>p->data) return x;
    else return p->data;
}

Linearly searching node in Linked List

struct Node* Lsearch(struct Node *p,int key){
    struct Node *q;
    while(p!=NULL){
        if(key == p->data){
            q->next = p->next;
            p->next=first;
            first=p;

            return p;
        }
        q=p;
        p=p->next;
    }
    return NULL;
}

Recursively linear search in Linked List


struct Node* RLsearch(struct Node *p, int key){
    if(p==NULL) return NULL;
     if(key==p->data){
            printf("Found");
            return p;
        }
        return RLsearch(p->next,key);
    }

Inserting a node in Linked List


void insert(struct Node *p, int pos, int key){
    struct Node *t;
    int i;
    if(pos < 0 || pos > count(p)) return;
    t = (struct Node*)malloc(sizeof(struct Node));
    t->data=key;
    if (pos == 0)
    {
       t->next = first;
       first = t;
    }
    else{
        for(i=0;i<pos-1;i++) p=p->next;
        t->next = p->next;
        p->next =t;
    }
    


}

Inserting a node in sorted Linked List

void sortedInsert(struct Node *p, int key){
    struct Node *t,*q;
    t=(struct Node *)malloc(sizeof(struct Node));
    t->data=key;
    if(p==NULL){
        first = t;
    }
    else{

    while(p->data<key && p!=NULL){
        q=p;
         p=p->next;
        }
        if(p==first){
            t->next = first;
            first =t;
        }else{

         t->next = q->next;
        q->next = t;
        }
    

}
}

Appending a node in a Linked List

void append(struct Node *p, int key){
    struct Node *t;
    t=(struct Node*)malloc(sizeof(struct Node));
    t->data=key;
    t->next=NULL;
    if(first==NULL){
        first = last = NULL;
    }
    else{
        last->next = t; 
        last = t;
    }
}

Deleting a node from the Linked List


int delete(struct Node *p, int pos){
    int i,x=-1;
    struct Node *q=NULL;
    if(pos<1 || pos>count(p)) return -1;
  else{  if(pos==1){
        first = p->next;
        x=p->data;
        free(p);
    }
    else{
        for(i=0;i<pos-1;i++){
            q=p;
            p=p->next; 
        }
        if(p!=NULL){
        q->next = p->next;
        x=p->data;
        free(p);
        }

    }
    return x;
}

}

Check if the Linked List is sorted

int checkSorted(struct Node* p){
    struct Node *q;
    while(p!=NULL){
        q=p;
        p=p->next;
        if(p!=NULL){
        if(p->data < q->data){
            return 0;
        }
        }
        
    }
    return 1;
}

Remove duplicates from the Linked List

void removedup(struct Node *p){
    struct Node *q;
    q=p->next;
    while(q!=NULL){
        if(p->data!=q->data){
            p=q;
            q=q->next;
        }
        else
        {
            p->next = q->next;
            free(q);
            q=p->next;
            
        }
    }
}

Reversing a Linked List using Array

Adding all the node values in an array. Reverse the array. Now change the values of the linked list.

void reverseElem(struct Node *p){
    int a[20],i=0;
    while(p!=NULL){
        a[i]=p->data;
        i++;
        p=p->next;
    }
    p=first;
    i--;
    while(p!=NULL){
        p->data=a[i--];
        p=p->next;
}
}

Reversing a Linked List using pointers

void reversePointers(struct Node *p){
    struct Node *q=NULL,*r=NULL;
    while(p!=NULL){
        r=q;
        q=p;
        p=p->next;
        q->next = r;
    }
    first=q;
}

Recursively reversing a Linked List using pointers

void recReverse(struct Node *q, struct Node *p){
    if(p!=NULL){
        recReverse(p,p->next);
        p->next = q;
    }
    else{
        first=q;
    }

}

Concatenating two Linked Lists

void concat(struct Node *p, struct Node *q){
    third = p;
    while(p->next!=NULL){
        p=p->next;
    }
    p->next=q;
}

Merging two Linked Lists


void merge(struct Node*p, struct Node *q){
    struct Node *last;
    if(p->data<q->data){
        third=last=p;
        p=p->next;
        third->next=NULL;
    }
    else{
        third=last=q;
        q=q->next;
        third->next=NULL;
    }
    while(p && q){
        if(p->data < q->data){
            last->next=p;
            last=p;
            p=p->next;
            last->next=NULL;
            
            }
        else{
            last->next=q;
            last=q;
            q=q->next;
            last->next=NULL;
            

        }

    }
    if(p) last->next = p;
    else if(q) last->next = q;
}

Check if the Linked List is looping or is a circular linked list

int isLoop(struct Node *f){
    struct Node *p,*q;
    p=q=f;
    do{
        p=p->next;
        q=q->next;
        q=q?q->next:NULL;
    }
    while (p && q && p!=q);
    return p==q?1:0;
    
}

LEAVE A REPLY