Singly Linked List Operations:
1) Insert at beginning2) Insert at end
3) Insert after the given key node
4) Insert before the given key node
5) Insert at specified position
6) Delete from the beginning
7) Delete from the end
8) Delete the specified key node
#include<stdio.h>
#include<malloc.h>
#include<stdlib.h>
struct node
{
int data;
struct node *link;
};
typedef struct node * NODE;
NODE getnode()
{
NODE x;
x = (NODE)malloc(sizeof(struct node));
if(x == NULL)
{
printf("\nInsufficient
memory");
exit(0);
}
x->link = NULL;
return x;
}
NODE create_list(NODE first)
{
int i, n;
printf("\nCreating the list: ");
printf("\nEnter the number of nodes: ");
scanf("%d", &n);
/*Number of nodes 0*/
if(n==0)
return first;
printf("\nEnter the VALUES for nodes: ");
for(i=1; i<=n; i++)
first= insert_at_end(first);
return first;
}
NODE insert_at_front(NODE first)
{
int val;
NODE temp;
temp = getnode();
printf("\nEnter the value: ");
scanf("%d", &val);
temp->data = val;
/*Case 1: List is empty.*/
if(first == NULL)
return temp;
/*Case 2: List has nodes.*/
temp->link = first;
return temp;
}
NODE insert_at_end(NODE first)
{
int val;
NODE temp, cur;
temp = getnode();
printf("\nEnter the value: ");
scanf("%d", &val);
temp->data = val;
/*Case 1: List is empty*/
if(first == NULL)
return temp;
/*Case 2: List has nodes: Traverse till the
end of the list*/
cur = first;
while(cur->link!=NULL)
{
cur = cur->link;
}
/*Set the link field of last node to point
to temp node*/
cur->link = temp;
return first;
}
NODE insert_after(NODE first)
{
int val, key;
NODE temp, cur;
temp
= getnode();
printf("\nEnter the value to be inserted: ");
scanf("%d", &val);
temp->data = val;
/*Case 1: List is empty.*/
if(first == NULL)
return temp;
printf("\nEnter the key after which node to be inserted:");
scanf("%d", &key);
/*Case 2: List has nodes. Traverse till key
node is found. */
cur = first;
while(cur != NULL)
{
if( cur->data == key)
{
temp->link
= cur->link;
cur->link
= temp;
return
first;
}
cur = cur->link;
}
/*End of list. Key is not found*/
printf("\nKey element not found");
return first;
}
NODE insert_before(NODE first)
{
int val, key;
NODE temp, cur, prev;
temp = getnode();
printf("\nEnter the value to be inserted: ");
scanf("%d", &val);
temp->data = val;
/*Case 1: List is empty. */
if(first == NULL)
return temp;
printf("\nEnter the key before which node to
inserted:");
scanf("%d", &key);
/*Case 2: If the first node itself is the
key node*/
if(first->data == key)
{
temp->link = first;
return temp;
}
/*Case
3: Otherwise*/
prev = NULL;
cur = first;
while(cur != NULL)
{
if( cur->data == key)
{
prev->link =
temp;
temp->link =
cur;
return first;
}
prev = cur;
cur = cur->link;
}
printf("\nKey element not found");
return first;
}
NODE insert_at_pos(NODE first)
{
int val, pos, i;
NODE temp, cur, prev;
temp = getnode();
printf("\nEnter the value to be inserted: ");
scanf("%d", &val);
temp->data = val;
/*Case 1: List is
empty*/
if(first == NULL)
return temp;
printf("\nEnter the position where node to
inserted:");
scanf("%d", &pos);
/*Case 2: First position*/
if(pos == 1)
{
temp->link = first;
return temp;
}
/*Case 3: Any other position*/
prev = NULL;
cur = first;
for(i =1; cur != NULL && i<pos; i++)
{
prev = cur;
cur = cur->link;
}
if(cur==NULL)
{
printf("\nThere
are less than %d elements", pos);
return first;
}
else
{
prev->link = temp;
temp->link = cur;
return first;
}
}
NODE delete_at_front(NODE first)
{
NODE temp;
/*Case 1: List is empty. Nothing to delete.
*/
if(first == NULL)
{
printf("\nList is empty. Cannot
delete.");
return NULL;
}
/*Case 2: List has only one node. Deleting
this node makes list empty. */
if(first->link ==NULL)
{
printf("\nItem that got deleted is
%d", first->data);
free(first);
return NULL;
}
/*Case 3: List has more than one node.
Delete the front node. Update the first pointer. */
temp = first;
first = first->link;
temp->link=NULL;
printf("\nItem that got deleted is %d",
temp->data);
free(temp);
return first;
}
NODE delete_at_midle(NODE first)
{
int val, key;
NODE prev, cur;
prev =NULL;
/*Case 1: List is empty. Nothing to delete. */
if(first==NULL)
{
printf("\nList empty cannot
delete");
return NULL;
}
printf("\nEnter the key:");
scanf("%d", &key);
/*Case 2: First
node is the key node. */
if(first->link==NULL && first->data == key)
{
printf("\nItem that got deleted is
%d", first->data);
free(first);
return NULL;
}
/*Case 3: traverse till key node is found.
Delete that node. */
cur = first;
while(cur != NULL)
{
if( cur->data == key)
{
prev->link =
cur->link;
printf("\nItem
that got deleted is %d", cur->data);
free(cur);
return first;
}
prev = cur;
cur = cur->link;
}
printf("\nKey element not found");
return first;
}
NODE delete_at_end(NODE first)
{
NODE cur, prev;
/*Case 1: List is empty. */
if(first==NULL)
{
printf("\nList is empty. Cannot delete.");
return NULL;
}
/*Case 2: List has only one node. Deleting
that node makes list empty. */
if(first->link ==NULL)
{
printf("\nItem that got deleted is
%d", first->data);
free(first);
return NULL;
}
/*Case
3: List having more than one node. Delete the last node. Update the link of
last but one node. */
prev =NULL;
cur = first;
while(cur->link!=NULL)
{
prev = cur;
cur = cur->link;
}
prev->link =NULL;
printf("\nItem that got deleted is %d",
cur->data);
free(cur);
return first;
}
void display(NODE first)
{
NODE cur;
cur = first;
printf("\nContents are:");
if(cur == NULL)
printf("\nList is empty. Nothing to
display.");
else
{
while(cur!=NULL)
{
printf("%d ", cur->data);
cur =
cur->link;
}
}
}
void main()
{
int ch;
NODE first = NULL;
while(1)
{
printf("\n\n~~MENU~~");
printf("\n1.Create a list(any
insertion)");
printf("\n2.Insert at front");
printf("\n3.Insert after a given
key");
printf("\n4.Insert before a
given key");
printf("\n5.Insert at pos");
printf("\n6.Insert at end");
printf("\n7.Delete from front");
printf("\n8.Delete from middle using
key");
printf("\n9.Delete from end");
printf("\n10.exit");
printf("\nEnter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1: first
= create_list(first);
display(first);
break;
case 2: first = insert_at_front(first);
display(first);
break;
case 3: first = insert_after(first);
display(first);
break;
case 4: first = insert_before(first);
display(first);
break;
case 5: first = insert_at_pos(first);
display(first);
break;
case 6: first = insert_at_end(first);
display(first);
break;
case 7: first = delete_at_front(first);
display(first);
break;
case 8: first = delete_at_midle(first);
display(first);
break;
case 9: first = delete_at_end(first);
display(first);
break;
case 10: exit(0);
}
}
}
Output:
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 1
Creating the list:
Enter the number of nodes: 3
Enter the VALUES for nodes:
Enter the value: 11
Enter the value: 12
Enter the value: 13
Contents are: 11 12
13
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 2
Enter the value: 14
Contents are: 14 11 12
13
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 6
Enter the value: 15
Contents are: 14 11
12 13 15
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 3
Enter the value to be inserted: 66
Enter the key after which node
to be inserted: 13
Contents are: 14 11
12 13 66 15
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 4
Enter the value to be inserted: 88
Enter the key before which node
to be inserted: 12
Contents are: 14 11 88 12 13 66 15
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 5
Enter the value to be inserted: 99
Enter the position where node to
be inserted: 5
Contents are: 14 11
88 12 99 13 66 15
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 7
Item that got deleted is 14
Contents are: 11 88
12 99 13 66 15
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 9
Item that got deleted is 15
Contents are: 11 88
12 99 13
66
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 8
Enter the key: 99
Item that got deleted is 99
Contents are: 11 88 12 13 66
~~MENU~~
1.Create a list(any insertion)
2.Insert at front
3.Insert after a given key
4.Insert before a given key
5.Insert at pos
6.Insert at end
7.Delete from front
8.Delete from middle using key
9.Delete from end
10.exit
Enter your choice: 10
No comments:
Post a Comment