Singly Linked list is a special data structure, which is a collection of zero or more nodes. The node is a combination of data + link.
Data: It is used to store some value. It can be an Integer variable or a structure.
Link: It is used to hold the information of the next node.
Together with “Data + Link” is called as a node.
There are 4 different types of Linked List:
- Singly Linked List
- Doubly Linked List
- Circular Singly Linked List
- Circular Doubly Lined List.
Today we shall discuss about Singly Linked List.
A Singly Linked List is a collection of zero or more nodes where each node has 2 or more elements. One contains data and other contains the link to the next node.
Below is the example of of SLL:
From the above image we can infer following below points:
- The list has 5 elements.
- In the data section it holds the value 10, 20, 30, 40, 50.
- In the link field, it holds the address of the next node.
- The variable “first” holds the address of the first node.
- The “link field” of the last element has “NULL”, to suggest that it is the end of the list.
Below are the operations that can be performed on a SLL.
- Insert element in front.
- Delete element from front end.
- Search an element.
- Display all the data.
-
Insert element in front:
To insert an element in the front we follow below steps:
- Take a temp node by allocating the memory.
- Assign the value
- Assign the next pointer of the temp node to the head pointer
- Make the head pointer point to temp node making it as head pointer.
Below image shows the process
-
Delete element from front end:
Deleting the element from the front end is simple.
- First take a temp node.
- Move the temp node to the next of first node.
- Delete the first node.
- Now make the temp node as the head, thus deleting the element from first.
Below image shows the process
3. Display all the data:
To display all the node data, take a temp node, and iterate through all the elements present in the list. We take temp node because we don’t want to miss the head pointer.
Below is the code for SLL where the element is inserted at front end and deleted from front end.
Single Linked List implementation in C
#include<stdio.h> #include<stdlib.h> // declare a structure for linked list struct node { int data; struct node *next; } ; typedef struct node* node; // Insert the element at first node insert_front (int value, node first_node) { //take a temp node and allocate memory node temp_node = (node) malloc(sizeof(node)); // assign the given value in the data section temp_node->data = value; //since we are inserting the value at first, the temp_node should point to the first_node now. temp_node->next = first_node; //since temp_node is first now, we shall return the value. return temp_node; } node delete_front(node first_node) { node temp_node; // check if the first_node is null or not if(first_node == NULL) { printf("List is empty\n"); return first_node; } // take a temp_node pointer and assign it to the first_node temp_node = first_node; // now transffer the temp_node to the next node. temp_node = temp_node->next; printf("The deleted value is %d\n", first_node->data); //free first_node free(first_node); //return temp_node return temp_node; } void display(node first_node) { node temp_node; if(first_node == NULL) { printf("The list is empty\n"); return; } printf("The contents of the list are:\n"); // point temp_node to first_node temp_node = first_node; // display the data till temp_node is null while (temp_node != NULL) { printf("%d\n",temp_node->data); temp_node = temp_node->next; } } int main() { node first_node = NULL; int choice = 0; int value = 0; for( ; ; ) { printf("1. Insert front \n2. Delete Front \n3. Display \n4. Exit\n"); scanf("%d", &choice); switch(choice) { case 1: printf("Enter the value to be inserted\n"); scanf("%d", &value); first_node = insert_front(value, first_node); break; case 2: first_node = delete_front(first_node); break; case 3: display(first_node); break; case 4: exit(0); } } }
Output:
1. Insert front 2. Delete Front 3. Display 4. Exit 1 Enter the value to be inserted 10 1. Insert front 2. Delete Front 3. Display 4. Exit 1 Enter the value to be inserted 20 1. Insert front 2. Delete Front 3. Display 4. Exit 1 Enter the value to be inserted 30 1. Insert front 2. Delete Front 3. Display 4. Exit 3 The contents of the list are: 30 20 10 1. Insert front 2. Delete Front 3. Display 4. Exit 2 The deleted value is 30 1. Insert front 2. Delete Front 3. Display 4. Exit 3 The contents of the list are: 20 10 1. Insert front 2. Delete Front 3. Display 4. Exit 4
Further Reading: