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