Chapter: Programming and Data Structures - Linear Data structures- List

| Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail |

Singly Linked List

If position of ai is simply a pointer to the cell holding ai, then o Position 1 will be the address in the header

SINGLY LINKED LIST

 

Figure 2.1: A singly linked list

 


Let us follow a convention that position i is a pointer to the cell holding the pointer to the cell containing ai, (for i = 1, 2,..., n). Thus,

o  Position 1 is a pointer to the header

o  End (L) is a pointer to the last cell of list L

 

If position of ai is simply a pointer to the cell holding ai, then o Position 1 will be the address in the header

 

o end (L) will be a null pointer Insert (x, p, L) : See Figure

 

Delete (x, L) : See Figure

 

Insertion in a singly linked list


Deletion in a singly linked list


Singly Linked List

 

#include <stdio.h> #include <malloc.h> struct node

{

 

int data;

 

struct node *next; };

 

struct node *create_node(int); void insert_node_first();

 

void insert_node_last(); void insert_node_pos(); void delete_pos();

 

void search();

void display();

struct node *p;

 

void main()

 

{

int ch;

 

char ans='Y';

 

while(ans=='Y'||ans=='y')

{

 

printf("\n---------------------------------\n");

printf("\nOperations on singly linked list\n");

 

printf("\n---------------------------------\n");

printf("\n1.Insert node at first");

 

printf("\n2.Insert node at last"); printf("\n3.Insert node at position"); printf("\n4.Delete Node from any Position"); printf("\n5.Search Element in the linked list"); printf("\n6.Display List from Beginning to end"); printf("\n7.Exit\n");

 

printf("\nEnter your choice"); scanf("%d",&ch);

 

switch(ch)

 

{

case 1:

 

printf("\n...Inserting node at first...\n"); insert_node_first();

 

break; case 2:

 

printf("\n...Inserting node at last...\n"); insert_node_last();

 

break; case 3:

 

printf("\n...Inserting node at position...\n"); insert_node_pos();

 

break; case 4:

 

printf("\n...Deleting Node from any Position...\n"); delete_pos();

 

break; case 5:

 

printf("\n...Searching Element in the List...\n"); search();

 

break; case 6:

 

printf("\n...Displaying List From Beginning to End...\n");

display();   

break;        

case 7:        

exit(0);       

printf("\n...Exiting...\n");        

break;        

default:      

printf("\n...Invalid Choice...\n");      

break;        

}                

printf("\nYOU WANT TO CONTINUE (Y/N)");         

scanf(" %c",&ans);       

}                

}                

struct node *create_node(int ele)      

{                

struct node *temp;        

temp=(struct node*)malloc(sizeof(struct node)); 

temp->data =ele; 

temp->next = NULL;    

return temp;        

}                

void insert_node_first()

{                

int     ele;   

struct node *temp;        

printf("\nEnter the value for the node:");   

scanf("%d",&ele);

temp=create_node(ele); 

if(p==NULL)       

{                

p=temp;     

}                

else            

{                

temp->next=p;    

p=temp;     

}                

printf("\n----INSERTED----");

}                

void insert_node_last() 

                  

display();   

break;        

case 7:        

exit(0);       

printf("\n...Exiting...\n");        

break;        

default:      

printf("\n...Invalid Choice...\n");      

break;        

}                

printf("\nYOU WANT TO CONTINUE (Y/N)");         

scanf(" %c",&ans);       

}                

}                

struct node *create_node(int ele)      

{                

struct node *temp;        

temp=(struct node*)malloc(sizeof(struct node)); 

temp->data =ele; 

temp->next = NULL;    

return temp;        

}                

void insert_node_first()

{                 

int     ele;   

struct node *temp;        

printf("\nEnter the value for the node:");   

scanf("%d",&ele);

temp=create_node(ele); 

if(p==NULL)       

{                

p=temp;     

}                

else            

{                

temp->next=p;    

p=temp;     

}                

printf("\n----INSERTED----");

}                

void insert_node_last() 

display();   

break;        

case 7:        

exit(0);       

printf("\n...Exiting...\n");        

break;        

default:      

printf("\n...Invalid Choice...\n");      

break;        

}                

printf("\nYOU WANT TO CONTINUE (Y/N)");         

scanf(" %c",&ans);       

}                

}                

struct node *create_node(int ele)      

{                

struct node *temp;        

temp=(struct node*)malloc(sizeof(struct node)); 

temp->data =ele; 

temp->next = NULL;    

return temp;        

}                

void insert_node_first()

{                

int     ele;   

struct node *temp;        

printf("\nEnter the value for the node:");   

scanf("%d",&ele);

temp=create_node(ele); 

if(p==NULL)       

{                

p=temp;     

}                

else            

{                

temp->next=p;    

p=temp;     

}                

printf("\n----INSERTED----");

}                

void insert_node_last() 

display();   

break;        

case 7:        

exit(0);       

printf("\n...Exiting...\n");        

break;        

default:      

printf("\n...Invalid Choice...\n");      

break;        

}                

printf("\nYOU WANT TO CONTINUE (Y/N)");         

scanf(" %c",&ans);       

}                

}                

struct node *create_node(int ele)      

{                

struct node *temp;        

temp=(struct node*)malloc(sizeof(struct node)); 

temp->data =ele; 

temp->next = NULL;    

return temp;        

}                

void insert_node_first()

{                

int     ele;   

struct node *temp;        

printf("\nEnter the value for the node:");   

scanf("%d",&ele);

temp=create_node(ele); 

if(p==NULL)       

{                

p=temp;     

}                

else            

{                

temp->next=p;    

p=temp;     

}                

printf("\n----INSERTED----");

}                

void insert_node_last() 

{                

int     ele;   

struct node *temp,*r;    

printf("\nEnter the value for the Node:");  

scanf("%d",&ele);

temp=create_node(ele); 

if(p==NULL)       

{                

p=temp;     

}                

else            

{                

r=p;  

while(r->next!=NULL)  

{                

r=r->next;  

}                

r->next=temp;     

}                

printf("\n----INSERTED----");

}                

void insert_node_pos() 

{                

int pos,ele,i;         

struct node *temp,*r,*t;

printf("\nEnter the value for the Node:");  

scanf("%d",&ele);

temp=create_node(ele); 

printf("\nEnter the position ");         

scanf("%d",&pos);        

if(pos==1) 

{                

if(p==NULL)       

{                

p=temp;     

}                

}                

else            

{                

r=p;  

for(i=1;i<pos;i++)         

{                

t=r;   

r=r->next;  

}                

{                

int     ele;   

struct node *temp,*r;    

printf("\nEnter the value for the Node:");  

scanf("%d",&ele);

temp=create_node(ele); 

if(p==NULL)       

{                

p=temp;     

}                

else            

{                

r=p;  

while(r->next!=NULL)  

{                

r=r->next;  

}                

r->next=temp;     

}                

printf("\n----INSERTED----");

}                

void insert_node_pos() 

{                

int pos,ele,i;         

struct node *temp,*r,*t;

printf("\nEnter the value for the Node:");  

scanf("%d",&ele);

temp=create_node(ele); 

printf("\nEnter the position ");         

scanf("%d",&pos);        

if(pos==1) 

{                

if(p==NULL)       

{                

p=temp;     

}                

}                

else            

{                

r=p;  

for(i=1;i<pos;i++)         

{                

t=r;   

r=r->next;  

}                

t->next=temp; temp->next=r;

 

}

printf("\nInserted");

 

}

 

void delete_pos()

{

 

int pos,i;

 

struct node *r,*t; if(p==NULL)

{

 

printf(":No node to delete\n");

}

 

else

{

 

printf("\nEnter the position of value to be deleted:"); scanf("%d",&pos);

 

if(pos==1)

{

 

p=p->next; printf("\nElement deleted");

 

}

else

 

{

r=p;

 

for(i=1;i<pos;i++)

{

 

t=r; r=r->next;

 

}

 

t->next=r->next; free(r);

}

 

}

}

 

void search()

{

 

struct node *r; int ele; if(p==NULL)

{

 

printf(":No nodes in the list\n");

}

 

else

{

 

printf("\nEnter the value to search");

 

scanf("%d",&ele);

r=p;

 

while(r!=NULL)

{

 

if(r->data==ele)

{

 

printf("found");

return;

 

}

else

 

{

r=r->next;

 

}

printf("not found");

 

}

}}

 

void display()

 

{

 

struct node *r; if(p==NULL)

{

 

printf(":No nodes in the list to display\n");

}

 

else

{

 

r=p;

while(r!=NULL)

 

{

 

printf("%d\t",r->data); r=r->next;

}

 

}

}


Study Material, Lecturing Notes, Assignment, Reference, Wiki description explanation, brief detail


Copyright © 2018-2020 BrainKart.com; All Rights Reserved. Developed by Therithal info, Chennai.