A singly linked list is the simplest type of linked list in which every node contains some data and a pointer to the next node of the same data type. By saying that the node contains a pointer to the next node, we mean that the node stores the address of the next node in sequence.
A singly linked list allows traversal of data only in one way
Creating a list
The structure contains an integer data and a link (i.e.) a pointer to the same data structure. The structure pointer first points to the first node. first is declared NULL to indicate that the list is empty initially. cur is the pointer used for list operations which can point to any one of the nodes
struct node {
int data;
struct node *link;
};
struct node *first=NULL, *next, *prev, *cur;
void create()
{
cur=(struct node *)malloc(sizeof(struct node)); printf("Enter the data: ");
scanf("%d",&cur->data);
cur->link=NULL;
first=cur;
}Representation
Inserting a node
At the beginning, To insert at first position, memory is allocated to a new node, it is made to link to first and finally it is made the first node.
void insert_beginning()
{
cur=(struct node *)malloc(sizeof(struct node)); printf("Enter the first element: ");
scanf("%d",&cur->data);
cur->link=first;
first=cur;
}Representation
At the end
To insert at last position, memory is allocated to a new node, its link part is assigned NULL and the last element is made to point to the newly created node.
void insert_end()
{
cur=(struct node *)malloc(sizeof(struct node)); printf("Enter the last element: ");
scanf("%d",&cur->data);
prev=first;
while(prev->link!=NULL)
prev=prev->link;
cur->link=NULL;
prev->link=cur;
}Representation
At any position p
void insert_pos()
{
int pos, c=1;
cur=(struct node *)malloc(sizeof(struct node));
printf("Enter the position: ");
scanf("%d",&pos);
printf("Enter the data: ");
scanf("%d",&cur->data);
next=first;
while(c < pos)
{
prev = next;
next = prev->link;
c++;
}
if(prev==NULL)
printf("\nInvalid position...");
else
{
cur->link=next;
prev->link=cur;
}
}Representation
Deleting a node
Deleting first element
To delete first element, first is assigned to a temporary variable say cur. Then the second node, i.e., first->link is assigned as first and then cur is deleted. free () function is used to free up memory pointed by its argument.
void delete_beginning()
{
cur=first;
first=first->link;
printf("\nDeleted element is %d",cur->data);
free(cur);
}Representation
Deleting element at the end
void delete_end()
{
cur=first;
prev=first;
while(cur->link!=NULL)
{
prev=cur;
cur=cur->link;
}
prev->link=NULL;
printf("\nDeleted element is %d",cur->data);
free(cur);
}Representation
Deleting element at any position p
void delete_pos()
{
int pos, c=1;
printf("Enter the position: ");
scanf("%d",&pos);
cur=first;
prev=first;
while(c<pos)
{
prev = curr;
cur = cur->link;
c++;
}
if(cur==NULL)
printf("\nInvalid position...");
else
{
prev->link=cur->link;
printf("\nDeleted element is %d",cur->data);
free(cur);
}
}Representation
Updating a node
void update()
{
int pos, c=1;
cur=first;
printf("Enter the postion: ");
scanf("%d",&pos);
while(c<pos)
{
cur = cur->link;
c++;
}
printf("Enter the new data: ");
scanf("%d",&cur->data);
}Representation
Searching for a node
void find()
{
int c=1, x;
printf("Enter the element to search: ");
scanf("%d",&x);
cur=first;
while(cur!=NULL)
{
if(cur->data==x)
{
printf("%d found at position %d",x,c);
return;
}
cur=cur->link;
c++;
}
printf("%d not found...",x);
}Representation
Traversing the linked list
void display()
{
cur=first;
printf("Contents of the list: ");
while(cur!=NULL)
{
printf("%d\t",cur->data);
cur=cur->link;
}
} Advantage
It is dynamic memory allocation so that there is no wastage of memory.(memory allocated during run time.
DisAdvantage
Extra space is required to store the address of the successor element.
Views: 0