One-way chain or single-linked list
- A singly linked list is a collection of elements that are arranged in a specific order.
- The number of elements may vary depending on the program's requirements. In a single linked list, a node is made up of two parts: data and link.
- The data component of the node stores the actual data that the node will represent, while the link part stores the address of the node's immediate successor.
- A one-way chain, also known as a singly linked list, can only be traversed in one direction.
- To put it another way, we may say that each node has only the next pointer, therefore we can't traverse the list backwards.
Consider the following scenario: the student's grades in three marks are maintained in a linked list, as indicated in the image.
 |
| Singly Linked List |
- The links are represented by the arrow in the diagram above.
- The marks earned by the student in each topic are stored in the data section of each node.
- The null pointer in the address part of the last node identifies it as the last node in the list. In the data section of the list, we can have as many elements as we like.
Operations on Singly Linked List
On a singly linked list, you can conduct a variety of actions. The following is a list of all such operations.
- Insertion in singly linked list at beginning.
- Insertion in singly linked list at end.
- Insertion in singly linked list after specific node.
- Deletion and Traversing.
- Deletion at beginning.
- Deletion at the end of the list.
- Deletion after specified node.
- Traversing.
- Searching.
Node Creation
struct node
{
int data;
struct node *next;
};
struct node *head, *ptr;
ptr = (struct node *)malloc(sizeof(struct node *));
Insertion
- Insertion into a singly linked list can take place at several points. The insertion is classified into the following types based on the position of the new node being inserted.
Insertion in singly linked list at beginning
- It's easy to add a new element to a single linked list at the start. Only a few changes to the node linkages are required. The steps below must be followed in order to add a new node to the list at the start.
- Allocate space for the new node and place data in the node's data section. The following statements will accomplish this.
ptr = (struct node *) malloc(sizeof(struct node *));
ptr → data = item
- Make the new node's link component point to the list's existing first node. The following expression will be used to do this.
ptr->next = head;
- Finally, we must make the new node the first node in the list, which may be accomplished with the following statement.
head= ptr ;
Algorithm
- Step 1: IF PTR = NULL
Go to Step 7
[END OF IF]
- Step 2: SET NEW_NODE = PTR
- Step 3: SET PTR = PTR → NEXT
- Step 4: SET NEW_NODE → DATA = VAL
- Step 5: SET NEW_NODE → NEXT = HEAD
- Step 6: SET HEAD = NEW_NODE
- Step 7: EXIT
 |
| Singly Linked List |
C program to insert new data (at the beginning) in singly linked list.
#include<stdio.h>
#include<stdlib.h>
void beginsert(int);
struct node
{
int data;
struct node *next;
};
struct node *head;
void main ()
{
int choice,item;
do
{
printf("\nEnter the item which you want to insert?\n");
scanf("%d",&item);
beginsert(item);
printf("\nPress 0 to insert more ?\n");
scanf("%d",&choice);
}while(choice == 0);
}
void beginsert(int item)
{
struct node *ptr = (struct node *)malloc(sizeof(struct node *));
if(ptr == NULL)
{
printf("\nOVERFLOW\n");
}
else
{
ptr->data = item;
ptr->next = head;
head = ptr;
printf("\nNode inserted\n");
}
}
Expected Output:
Enter the item which you want to insert?
12
Node inserted
Press 0 to insert more ?
0
Enter the item which you want to insert?
23
Node inserted
Press 0 to insert more ?
2
