### Linked List as an abstract data type

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;
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;
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,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;
}

}``````

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

``````
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;

}``````