DSA-I 4: Singly Linked List – Dynamic Implementation
Operations on Linked List:
append(L, x)
Insert the data element x by creating the node containing the data element x and inserting it in last position.
insert (L, x, pos)
inserts the data element x by creating the node containing the data element x and inserting it in position pos. The links are appropriately changed. If pos equals 1, the node is inserted in first position immediately after the header. If pos is greater than the nodes present in the list, the node is added at the end of the list.
search (L, x)
Searches for the data element x and returns the pointer to the node containing x if x is present or returns NULL.
delete (L, x)
Deletes the node containing the data element x by appropriately modifying the links.
delete (L, pos)
Delete the node at a position given by pos. If the position pos is invalid then display appropriate message.
display (L)
Displays all the data elements in the list
Set A
a) Implement a list library (singlylist.h) for a singly linked list with the above six operations. Write a menu driven driver program to call the operations.
The User-defined header file:
#include<stdio.h>
#include<stdlib.h>
struct node
{
char data;
struct node *next;
}*start;
void create()
{
struct node *temp,*q;
temp=(struct node *)malloc(sizeof(struct node));
printf("\nEnter the character:");
scanf(" %c",&temp->data);
temp->next=NULL;
if(start==NULL)
{
start=temp;
}
else
{
q=start;
while(q->next!=NULL)
{
q=q->next;
}
q->next=temp;
}
}
void delete()
{
struct node *temp,*p;
int pos,t;
printf("\nEnter the position:");
scanf("%d",&pos);
t=1;
temp=start;
if(pos==1)
{
start=start->next;
free(temp);
printf("\nNode Deleted Successfully\n");
return;
}
while(t< pos-1)
{
temp=temp->next;
t++;
}
p=temp->next;
temp->next=p->next;
free(p);
printf("\nNode Deleted Successfully\n");
}
void display()
{
struct node *temp;
printf("The Linked List : \n");
temp=start;
while(temp!=NULL)
{
printf("%c->",temp->data);
temp=temp->next;
}
printf("NULL");
}
Save this above code file as singlylist.h
#include<stdio.h>
#include "singlylist.h"
int main()
{
int ch;
start=NULL;
while(1)
{
printf("\n1.Create\n");
printf("2.Delete\n");
printf("3.Display\n");
printf("4.Exit\n");
printf("Enter your choice: ");
scanf("%d",&ch);
switch(ch)
{
case 1:create(); break;
case 2:delete(); break;
case 3:display(); break;
case 4:exit(0);
}
}
}
Save this file as linkedlist.c and compile and run the linkedlist.c
b) Implement a list library (singlylist.h) for a singly linked list. Create a linked list, reverse it and display reversed linked list.
#include <stdio.h>
#include <stdlib.h>
struct node
{
int num; //Data of the node
struct node *nextptr; //Address of the node
}*stnode;
void createNodeList(int n); //function to create the list
void reverseDispList(); //function to convert the list in reverse
void displayList(); //function to display the list
int main()
{
int n;
printf("\n\n Linked List : Create a singly linked list and print it in reverse order :\n");
printf("------------------------------------------------------------------------------\n");
printf(" Input the number of nodes : ");
scanf("%d", &n);
createNodeList(n);
printf("\n Data entered in the list are : \n");
displayList();
reverseDispList();
printf("\n The list in reverse are : \n");
displayList();
return 0;
}
void createNodeList(int n)
{
struct node *fnNode, *tmp;
int num, i;
stnode = (struct node *)malloc(sizeof(struct node));
if(stnode == NULL) //check whether the stnode is NULL and if so no memory allocation
{
printf(" Memory can not be allocated.");
}
else
{
// reads data for the node through keyboard
printf(" Input data for node 1 : ");
scanf("%d", &num);
stnode-> num = num;
stnode-> nextptr = NULL; //Links the address field to NULL
tmp = stnode;
//Creates n nodes and adds to linked list
for(i=2; i<=n; i++)
{
fnNode = (struct node *)malloc(sizeof(struct node));
if(fnNode == NULL) //check whether the fnnode is NULL and if so no memory allocation
{
printf(" Memory can not be allocated.");
break;
}
else
{
printf(" Input data for node %d : ", i);
scanf(" %d", &num);
fnNode->num = num; // links the num field of fnNode with num
fnNode->nextptr = NULL; // links the address field of fnNode with NULL
tmp->nextptr = fnNode; // links previous node i.e. tmp to the fnNode
tmp = tmp->nextptr;
}
}
}
}
void reverseDispList()
{
struct node *prevNode, *curNode;
if(stnode != NULL)
{
prevNode = stnode;
curNode = stnode->nextptr;
stnode = stnode->nextptr;
prevNode->nextptr = NULL; //convert the first node as last
while(stnode != NULL)
{
stnode = stnode->nextptr;
curNode->nextptr = prevNode;
prevNode = curNode;
curNode = stnode;
}
stnode = prevNode; //convert the last node as head
}
}
void displayList()
{
struct node *tmp;
if(stnode == NULL)
{
printf(" No data found in the list.");
}
else
{
tmp = stnode;
while(tmp != NULL)
{
printf(" Data = %d\n", tmp->num); // prints the data of current node
tmp = tmp->nextptr; // advances the position of current node
}
}
}
Set B
a) There are lists where insertion should ensure the ordering of data elements. Since the elements are in ascending order the search can terminate once equal or greater element is found. Implement a singly linked list of ordered integers(ascending/descending) with insert, search and display operations.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
void insert(struct node **head,int data)
{
struct node *newnode;
newnode=malloc(sizeof(struct node));
newnode->data=data;
newnode->next=NULL;
if(*head==NULL)
*head=newnode;
else
{
struct node *temp=*head,*prev;
while(temp)
{
if(temp->data >=data)
{
if(temp==*head)
{
newnode->next=*head;
*head=newnode;
}
else
{
prev->next=newnode;
newnode->next=temp;
}
break;
}
else
{
prev=temp;
temp=temp->next;
}
}
if(!temp)
prev->next=newnode;
}
}
void display(struct node *temp)
{
if(!temp)
printf("\n\tEmpty list\n");
else
{
while(temp)
{
printf("\t%d ",temp->data);
temp=temp->next;
}
}
}
void search(struct node *head , int data)
{
struct node *temp= head;
int cnt=0;
while(temp && temp->data != data)
{
temp=temp->next;
cnt++;
}
if(temp)
printf("%d is at %d position\n",data,cnt);
else
printf("No data\n");
getchar();getchar();
}
int menu()
{
system("clear");
int ch;
printf("\n\t0.Exit\n\t1.Create list\n\t2.Display list\n\t3.Search node \n\tEnter your choice :");
scanf("%d",&ch);
return ch;
}
main()
{
struct node *head=NULL;
int ch;
while((ch=menu())!=0)
{
if(ch==1)
{
int i,size;
printf("How many nodes you want :");
scanf("%d",&size);
for(i=0;i<size;i++)
insert(&head,random()%100);
}
else
if(ch==2)
{
display(head);
getchar();getchar();
}
else
if(ch==3)
{
int i,node;
printf("Enter node to be searched :");
scanf("%d",&node);
search(head,node);
getchar();getchar();
}
}
}
b) There are lists where new elements are always appended at the end of the list. The list can be implemented as a circular list with the external pointer pointing to the last element of the list. Implement singly linked circular list of integers with append and display operations. The operation append(L, n), appends to the end of the list, n integers either accepted from user or randomly generated.
#include<stdio.h>
#include<stdlib.h>
struct node
{
int data;
struct node *next;
};
void append(struct node **head,int n)
{
struct node *newnode;
newnode=malloc(sizeof(struct node));
newnode->data=n;
if(*head==NULL)
newnode->next=newnode;
else
{
newnode->next=(*head)->next;
(*head)->next=newnode;
}
*head=newnode;
}
void create(struct node ** head, int n)
{
int i,data;
struct node *newnode;
for(i=1;i<=n;i++)
{
printf("Element Append %d\n",i);
scanf("%d",&data);
newnode=malloc(sizeof(struct node));
newnode->data=data;
if(*head==NULL)
newnode->next=newnode;
else
{
newnode->next=(*head)->next;
(*head)->next=newnode;
}
*head=newnode;
}
}
void display(struct node *head)
{
struct node *temp = head;
do
{
printf(" %d ",temp->data);
temp=temp->next;
}while(temp!=head);
printf("\n");
}
main()
{
int n;
struct node *head=NULL;
printf("How many elements you want to Append? \n ");
scanf("%d",&n);
create(&head,n);
printf("Display the elements:\n ");
display(head);
}
No comments:
Post a Comment