A Singly Linked List is a type of data structure where elements (called nodes) are stored in a linear sequence, but each node points to the next one rather than being stored in contiguous memory. Each node in a singly linked list contains two parts:
- Data: The value or information stored in the node.
- Pointer (next): A reference (or pointer) to the next node in the sequence.
struct Node {
int data; // can be any data: int, char, float, arrays, structures, etc.
struct Node* next;
};Example
In a linked list, the entry point and exit point are crucial for managing the list.
- Entry Point:
- The entry point is represented by a pointer called
head, which stores the address of the first node. - From the head, all nodes in the list can be accessed, as each node contains a pointer to the next node in the sequence.
- The entry point is represented by a pointer called
- Exit Point:
- Unlike arrays, linked lists don’t have a fixed size. To know the end of the single linked list, the
nextpointer of the last node is assigned asNULL. - This
NULLvalue signals the exit point, indicating that there are no more nodes to traverse.
- Unlike arrays, linked lists don’t have a fixed size. To know the end of the single linked list, the
Managing nodes in a single linked list
1. Traversing through nodes in a list
To access the nodes in a list, it’s essential to understand how to traverse through it. In a singly linked list, traversal begins from the head node. Each node is checked to determine if it’s the last node by verifying whether the next pointer is NULL. The process continues until the end of the list is reached, where the next pointer of the last node becomes NULL.
struct Node *tmp = head; //assigning head node to a temporary pointer
while (tmp != NULL) {
/* print each node's data */
printf("Data = %d\n", tmp->data);
tmp = tmp->data;
}2. Adding a node
Adding at the end
The new node is added at the end of the list. To do this, the list is traversed until the last node is reached, and the next pointer of the last node is updated to point to the new node. The new node’s next pointer will point to NULL, indicating it is now the last node.
/* Add a node at the end of the list */
void add_tail(struct node **head)
{
struct node *tmp;
struct node *new_node;
int val;
/* Create a new node */
printf("enter a value to insert:");
scanf("%d", &val);
new_node = (struct node*)calloc(1, sizeof(struct node));
new_node->data = val;
/* check if list is empty */
if (*head == NULL)
/* if list is empty new node becomes head */
*head = new_node;
else {
/* traverse till the end and add new node */
tmp = *head;
while (tmp->next != NULL)
tmp = tmp->next;
tmp->next = new_node;
}
}Add at the beginning
In this approach, the new node becomes the first node of the list, and its next pointer will point to the current first node (head). The head pointer is then updated to point to this new node.
/* add at the start/ beginning of the list */
void add_head(struct node **head)
{
struct node *new_node = NULL;
int val;
/ * create a new node */
new_node = (struct node*)calloc(1, sizeof(struct node));
printf("enter a value to insert:");
scanf("%d", &val);
new_node->data = val;
if (*head == NULL)
*head = new_node;
else {
new_node->next = *head;
*head new_node;
}
}
3. Deleting a node
Deleting a node from a singly linked list involves removing an existing node from the list while maintaining the structure. There are three common cases for deletion:
Delete first node
The first node (pointed to by the head) is removed. To do this, the head pointer is updated to point to the second node in the list. The first node is then deallocated or freed.
/* delete first node */
void delete_first_node(struct node **head)
{
struct node *tmp;
if (*head == NULL) {
printf("list empty\n");
return;
}
tmp = *head;
/* move head to second node */
*head = tmp->next;
/* free first node */
free(tmp);
}Delete last node
To delete the last node, the list must be traversed until the second-to-last node is found (since the list is singly linked, there’s no direct reference to the previous node). Once found, the next pointer of the second-to-last node is set to NULL, and the last node is deallocated or freed.
/* delete last node */
void delete_last_node(struct node **head)
{
struct node *tmp;
if (*head == NULL) {
printf("list empty\n");
return;
}
if ((*head)->next == NULL) {
free(*head);
*head = NULL;
return;
}
tmp = *head;
while (tmp->next->next != NULL)
tmp = tmp->next;
free(tmp->next);
tmp->next = NULL;
}Delete a selected node
To delete a node in the middle of the list (or a specific node), first, traverse the list to find the node that precedes the one to be deleted. Update the previous node’s next pointer to point to the node after the one being deleted, effectively bypassing the node to delete. Finally, deallocate the selected node.
void delete_node(struct node **head)
{
int val;
struct node *tmp, *node;
if (head == NULL) {
printf("List empty\n");
return;
}
printf("enter value to delete:");
scanf("%d", &val);
/* if it is first node */
if ((*head)->data == val) {
tmp = (*head)->next;
free(*head);
*head = tmp;
return;
}
/* traverse through list and find the node */
tmp = *head;
while (tmp->next != NULL && tmp->next->data != val) {
tmp = tmp->next;
}
/* if reached end of the list and node not found */
if (tmp->next == NULL) {
printf("node not found with val:%d\n", val);
return;
}
printf("deleting a node\n");
node = tmp->next;
tmp->next = tmp->next->next;
free(node);
}github link for Datastructures application here