Home | | Programming and Data Structures I | Singly Linked List

Chapter: Programming and Data Structures : Linear Data structures- 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

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

#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("\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");

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;

}

}

}}

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
Programming and Data Structures : Linear Data structures- List : Singly Linked List |