Linked Lists

Linked Lists Linked Lists are another useful data structure. It has great advantage over Array data structure. In comparison to array it is more advantageous in the following senseIn Array as a programmer we have to specify the size/capacity of that array. This restriction is dangerous whenever we need to maintain extra record beyond specified size. Also in case of less record then size. In this case a lot of memory cells are wasted. If array is full, it is never possible to further store extra records in this array.

IN LINKED REQUIRED: • • • • •

•

LISTS

FOLLOWING

STEPS

ARE

Creation of memory [using malloc ()]. Collection the base address returned by malloc () into a temporary pointer variable. Storing own data into the information part of the node. Now store data into the node.  Store ‘NULL’ into the next part of the node. If head contains ‘Null’ then Head=temp prev info next Else c_node-> next=temp And at last store temp into c_node.

IMPORTANT TERMS: Node: The components which form the list. Temp: Contains the temporary address which is pointer variable. Head: Contains the address of first node. C_node: Contains the address of current node. Next: Contains the address of next node. If there is only one node in the list then it holds ‘NULL’.

Representation of a Linked List

Operations on a linked list:        

Creation of a linked list Display Traversing Insertion Deletion Searching Concatenation Merging

Types of linked lists: 1. 2. 3. 4.

Singly Linked List Doubly Linked List Circular Linked List Circular Doubly Linked List

1. Singly Linked List: /*Code to Create a Singly Linked List:*/ #include<stdio.h> #include Void main() { Char ch; Struct node { Int info; Struct node *next; }; Struct node *head, *temp, *c_node; Int data; Head=NULL; do{

printf(“Enter data into list:\n”); scanf(“%d”,&data); if(head==NULL) { temp=(struct node*)malloc(sizeof(struct node)); temp->info=data; temp->next=NULL; head=temp; c_node=temp; } else { temp=(struct node *)malloc(sizeof(struct node)); temp->info=data; temp->next=NULL; c_node->next=temp; c_node=temp; } printf(“Enter Y to Continue………\n”); }while(ch==’y’||ch==’Y’); printf(“Linked List successfully Created\n”);

/*Code for display*/ c_node=head; while(c_node!=NULL) { printf(“%d\n”,c_node->info); c_node=c_node->next; }

/*Code for Traversal*/

int n; c_node=head; printf(“Enter a Element To search\n ”); scanf(“%d\n,&n”); printf(“The List Elements are at %dth no. \n”,n); while(c_node!=NULL) { printf(“%d\n”,c_node->info); if(c_node->info==n) Break; c_node=c_node->next; }

/*Code for Insertion of a data*/ printf(“Enter Data To Be Inserted\t”); scanf(“%d”,&data);

/*Code for Insertion of Beginning Of Link List*/

a

data

at

the

temp=(struct node *)malloc(sizeof(struct node)); temp->info=data; temp->next=head; head=temp; }

/*Code for Insertion of a data at the End Of Link List*/ temp=(struct node *)malloc(sizeof(struct node)); struct node *cnode=head; while(cnode->next!=NULL) { Cnode=cnode->next; } temp->info=data; temp->next=NULL; cnode->next=temp; }

/*Code for Insert a data at Special Position Of Link List*/ printf(“Enter Data and The Position No. where You want to insert the Data\n”); int i,k; struct node *p; for(i=0,temp=head;k<pos;k++) { temp=temp->next; if(temp==NULL) { printf(“node in the list at less than ONE\n”); return; } } p=(struct node *)malloc(sizeof(struct node)); p->info=data; p->next=pos->next; pos->next=p; }

/*Code for Delete a data at the Beginning of Link List*/ struct node *ptr; ptr=head; head=head->next; printf(“U have Deleted %d This\n”,ptr->info); free(ptr); }

/*Code for Delete a data at the Beginning of Link List*/ struct node *add,*pnode; add=head; pnode=NULL; while(add->next!=NULL) { pnode=ptr; add=add->next; } pnode->next=NULL; free(add); }

/*Code for Delete a position of Link List*/

data

from

specified

struct node *ptr,*temp; int i,pos; printf(“Enter Position to Delete\n”); scanf(“%d”,&pos); ptr=head; for(i=1;i<=pos;i++) { temp=ptr; ptf=ptr->next; } printf(“The NUMBER Which U have deleted is %d”,ptf->info); temp->next=ptf->next; free(ptr); }

/*Code for Searching a data in SINGLY Linked List*/ (In particular Function body) void search() { printf(“Which Data do U wanna SEARCH:\n”); scanf(“%d”,&data); struct node *cnode=head; int i=0,flag=0; while(cnode!=NULL) { i++; if(cnode->info==data) { flag=1; printf(“UR DATA FOUND ON NODE NO %d”,i); BREAK;

} cnode=cnode->next; } if(flag==0) printf(“SORRY DATA NOT FOUND\N”);; }

/*Code for CONCATENATION two linked lists*/ void concat(struct node *head1,struct node *head2) { struct node *cnode; cnode=head1; while(cnode->next!=NULL) { printf(“%d”,cnode->info); cnode=cnode->next; } while(cnode!=NULL) { printf(“%d”,cnode->info); cnode=cnode->next; } }

/*Code for SORTING a Singly Linked List*/ void sort(struct node *head) { struct node *temp,*cnode,*curr; int c=0; cnode=head; while(cnode!=NULL)

{ c++; cnode=cnode->next; } temp=head; for(i=0;inext; for(j=i+1;jinfo>curr->info) { t=temp->info; temp->info=curr->info; curr->info=t; } temp=temp->next; } curr=curr->next; }

}

2. CIRCULAR LINKED

/*Creation of a Circular Linked List*/ #include<stdio.h> #include struct node { int num; struct node *next; }*head,*temp,*rear; void main() { printf(“Enter Data to fill Circular Linked List:\n”); scanf(“%d”,&data); if(head==NULL) { temp=(struct node *)malloc(sizeof(struct node));

temp->num=data; temp->next=head; head=temp; rear=temp; } else { temp=(struct node *)malloc(sizeof(struct node)); temp->num=data; temp->next=head; rear->next=temp; rear=temp; } }

/*Inserting a node at the beginning in a Circular Linked List*/ void insert_beg() { struct node *temp; temp=(struct node *)malloc(sizeof(struct node)); printf(“Enter a Number to INSERT it at the beginning of CCL:”); scanf(“%d”,&temp->info); temp->next=head; head=temp; rear->next=head; }

/*Inserting node at a given Position in a Circular Linked List*/ Void main() { int n; printf(“Enter Position Number:”); scanf(“%d”,&n); n--; specifiedpos(n); } void specifiedpos(int j) { int c=0,k=j-2; struct node *num,*prev; printf(“Linked List Upto %d element=”,j); do{ printf(“%d”,head->info); head=head->next; if(k==c)prv=head; c++; }while(c<j);

num=(struct node *)malloc(sizeof(struct node)); printf(“Enter a Element:”); scanf(“%d”,&num->info); num->next=head; prv->next=num; head=temp; }

/*Deleting the 1st node from a Circular Linked List*/ void del_beg() { struct node *cnode; cnode=temp; temp=head=head->next; free(cnode); rear->next=head; c--; }

/*Deleting the Last node from a Circular Linked List*/ void del_end() { int k=0; while(k++<(c-2)) { head=head->next; } free(rear); rear=head; rear->next=temp; head=temp; c--; }

/*Deleting a node from specified position in a CLL*/ prinft(“Enter a position no:\n”); scanf(“%d”,&n); del_spe(); } void del_spe(int x) { struct node *prv,*temp1; int k=0,p; p=x-2; while(k++<x) {

head=head->next; if(k==x) prv=head; if(k==(x+1))temp1=head; } c--; prv->next=head; head=temp; free(temp1); }

/*Code For Displaying A Circular Linked List*/ 1st Method void show() { printf(“Linked List Elements are:”); do{ printf(“%d”,head->info); head=head->next; if(rear->next==head)Break; }while(1); head=temp; }

2nd Method

void show2() { node *p=head; while(p->next=head) { printf(“%d”,p->info); p=p->next; } }

3. DOUBLY LINKED LIST

In doubly linked list, each structure type node contains 3 parts: Info, Next & Prv. ‘Prv’ contains the address of just previous node. ‘Next’ contains the address of just next node and ‘Info’ contains the information (variable).

/*Creation of Doubly Linked List*/

void create() { do{ temp=(struct node *)malloc(sizeof(struct node)); printf(“\nEnter Ur Data”); scanf(“%d”,&temp->info); if(front==NULL) { temp->next=NULL; temp->prv=NULL; rear=front=temp; cnode=temp; } else { temp->next=NULL; temp->prv=cnode; cnode->next=temp; cnode=cnode->next; rear=temp; } printf(“\nEnter Y to Continue:”); ch=getche(); }while(ch==’y’||ch==’Y’); }

/*Insertion At Front*/ void insert_beg(int data) { node *ptr; prt=(node *)malloc(sizeof(node)); ptr->info=data; ptr->prv=NULL; ptr->next=front; front->prv=ptr; front=ptr; }

/*Insertion at the End*/ void insert_end(int data) { node *ptr; ptr=(node *)malloc(sizeof(node)); ptr->info=data; ptr->next=NULL; ptr->prv=rear; rear->next=ptr; rear=ptr; }

/*Deletion of a Node from specified position in Doubly Linked List*/ (i) First Method void del_spe() { struct node *case1,*yahoo,*ali,*ptr; int data,c=0; printf(“\nEnter Position of node”); scanf(“%d”,&data); case1=front; if(data==0) { ptr=front; free(ptr); front=front->next; front->prv=NULL; } else { while(case1!=NULL) { c++; if(c==(data-1)) { ptr=case1; } if(c==data) { yahoo=case1; free(yahoo); } if(c==(data+1)) ali=case1; case1=case1->next; } ptr->next=ali; } } (ii) Second Method cnode=front; while(cnode!=NULL) { if(cnode->info==data)Break; node=node->next; } cnode->next->prv=cnode->prv; cnode->prv->next=cnode->next;

free(cnode);

/*Searching data in Doubly Linked List*/ fnode=front; rnode=rear; flag=0,f=0,l=0,data=10; while(fnode!=NULL||rnode!=NULL) { f++; l++; if(fnode->info==data) { printf(“Data found At %d from starting”,f); flag=1; break; } if(rnode->info==data) { printf(“Data is found At %d from last”,l); flag=1; break; } fnode=fnode->next; rnode=rnode->prv; } if(flag==0) printf(“\nTry Again Data Not Found:”); }

4. CIRCULAR DOUBLY LINKED LIST

/*Creation of Circular Doubly Linked List*/ 1st method

#include<stdio.h> #include #include struct node { int info; struct node *left,*right; }*head; head=(struct node *)malloc(sizeof(struct node)); head->left=head->right=head; head->info=0;

2nd method with rear and front concept front=rear=NULL; do{ temp=(struct node *)malloc(sizeof(struct node)); scanf(“%d”,&temp->info); if(front==NULL) { fornt=temp; temp->prv=NULL; temp->next=front; rear=temp; cnode=temp; } else { temp->next=front; temp->prv=cnode; cnode->next=temp; rear=temp; cnode=cnode->next; } printf(“\n Press Y to continue”); ch=getche(); }while(ch==’y’||ch==’Y’);

/*Insertion At beginning*/ void insert_beg() { node *ptr,*temp; int item; prt=(node *0malloc(sizeof(node)); printf(“\nEnter the No:”); scanf(“%d”,&item); ptr->info=item; temp=head->right; head->right=ptr; ptr->left=head;

ptr->right=temp; temp->left=ptr; }

/*Insertion At Last*/ void insert_end() { node *ptr,*temp; int item; ptr=(node *)malloc(sizeof(node)); scanf(“%d”,&ptr->info); temp=head->left; temp->right=ptr; ptr->left=temp; ptr->right=head; head->left=ptr; }

/*Deletion from Beginning*/ void del_beg() { node *temp; if(head->right==head) { return; } else { temp=head->right; printf(“\deleted element is =%d \n”,temp->info); head->right=temp->right; temp->right=temp->left=head; free(temp); } }

/*Delete from Last*/

void del_end() { node *temp; if(head->right==head)return; else { temp=head->left; printf(“\nDeleted element is %d \n”,temp->info); head->left=temp->left; free(temp); }

Header Linked List The Header Linked List is similar to the single linked list but it contains some extra information. This Header list’s 1st node holds that vita information such as the total number of nodes.

In the figure Header node is holding count of total nodes i.e.: 3.

Application of Linked List Addition of two “POLYNOMIALS”:::::::::::::::::::::::::::::::::::::::::::::::::::::::::::: Polynomials are expressions containing number of terms with non zero coefficients and exponents. ex: p=5x³+2x²+10x+6;

Representation of the given equation 5x³+2x²+10x+6

Creation of a POLYNOMIAL ----------------------------------------------------------------void main() { int c,e; struct poly { int coef; int expo; struct poly *next; }*temp,*cnode,*head,*ele,*rear; char ch; printf(“Enter co-efficient\n”); printf(“Enter Exponent\n”); scanf(“%d%d”,&c,&e); temp=(struct poly *)malloc(sizeof(struct poly)); temp->next=NULL; if(head==NULL) {

head=temp; cnode=temp; } else { BY SIR cnode->next=temp; cnode=cnode->next; } printf(“Press Y to continueeeeeee:\n”); ch=getche(); }while(ch==’y’||ch==’Y’); --------------------------------------------------------------------------------------------------------------------------------rear=temp; for(;;) { printf(“Enter co-efficient\n”); ele=(struct node *)malloc(sizeof(struct node)); scanf(“%d”,&coef); if(ele->c==0)Break; printf(“Enter Exponent:\n”); scanf(“%d”,&e); ele->expo=e; if(ele->expo<=0) { printf(“INVALID INPUT\n”); Break; } ele->next=NULL; rear->next=ele; rear=ele; } temp=temp->next; } -----------------------------------------------------------------

BY BOOK

/*Displaying a Polynomial*/ cnode=head; Printf(“\n%dx^%d’,cnode->coef,cnode->expo); cnode=cnode->next; while(cnode!=NULL) { if(cnode->coer>0) printf(“+”); else if(cnode->expo==0) printf(“%d”,cnode->coef); printf(“%dx^%d”,cnode->coef,cnode->expo);

cnode=cnode->next; }

ADDITION

The address of 1st Polynomial is stored in s1 and 2nd Polynomial is stored in s2. t3=polyadd(s1,s3); show(t3); struct poly *polyadd(struct poly *s1,struct poly *s2) { struct poly *s3=0,*p3,*tempo; if(s1==0&&s2==0)return s3; while(s1!==0&&s2!==0) { tempo=(struct poly *)malloc(sizeof(struct poly)); if(s3==0) { s3=tempo; p3=s3; } else { p3->next=tempo; p3=p3->next; } if(s1->expo>s2->expo) { tempo->coef=s1->coef; tempo->expo=s1->expo; s1=s1->next; } else if(s2->expo>s1->expo) { tempo->coef=s2->coef; tempo->expo=s2->expo; s2=s2->next; } else if(s1->expo==s2->expo) { tempo->coef=s1->coef+s2->coef; tempo->expo=s1->expo; s1=s1->next; s2=s2->next; } } while(s1!=0) { tempo=(struct node *)malloc(sizeof(struct poly)); tempo->coef=s1->coef; tempo->expo=s1->expo; if(s3==0)

{ s3=tempo; p3=s3; } else { p3->next=tempo; p3=p3->next; } s1=s1->next; } while(s2!=0) { tempo=(struct poly *)malloc(sizeof(struct node)); tempo->coef=s2->coef; tempo->expo=s2->expo; if(s3==0) { s3=tempo; p3=s3; } else { p3->next=tempo; p3=p3->next; } p3->next=0; return t3; }