- Insert in Linked List
- Delete node in Linked List based on position
- Display Nodes in Linked List
- Count Nodes in Linked List
/* Singly Linked List Example - All Operations Example Program Using Functions in C*/
/* Data Structure Programs,C Linked List Examples */
/* Singly Linked List Example - Insert,Delete,Display and Count Operations*/
#include <stdio.h>
#include <malloc.h>
#include <stdlib.h>
struct node {
int value;
struct node *next;
};
void insert();
void display();
void delete();
int count();
typedef struct node DATA_NODE;
DATA_NODE *head_node, *first_node, *temp_node = 0, *prev_node, next_node;
int data;
int main() {
int option = 0;
printf("Singly Linked List Example - All Operations\n");
while (option < 5) {
printf("\nOptions\n");
printf("1 : Insert into Linked List \n");
printf("2 : Delete from Linked List \n");
printf("3 : Display Linked List\n");
printf("4 : Count Linked List\n");
printf("Others : Exit()\n");
printf("Enter your option:");
scanf("%d", &option);
switch (option) {
case 1:
insert();
break;
case 2:
delete();
break;
case 3:
display();
break;
case 4:
count();
break;
default:
break;
}
}
return 0;
}
void insert() {
printf("\nEnter Element for Insert Linked List : \n");
scanf("%d", &data);
temp_node = (DATA_NODE *) malloc(sizeof (DATA_NODE));
temp_node->value = data;
if (first_node == 0) {
first_node = temp_node;
} else {
head_node->next = temp_node;
}
temp_node->next = 0;
head_node = temp_node;
fflush(stdin);
}
void delete() {
int countvalue, pos, i = 0;
countvalue = count();
temp_node = first_node;
printf("\nDisplay Linked List : \n");
printf("\nEnter Position for Delete Element : \n");
scanf("%d", &pos);
if (pos > 0 && pos <= countvalue) {
if (pos == 1) {
temp_node = temp_node -> next;
first_node = temp_node;
printf("\nDeleted Successfully \n\n");
} else {
while (temp_node != 0) {
if (i == (pos - 1)) {
prev_node->next = temp_node->next;
if(i == (countvalue - 1))
{
head_node = prev_node;
}
printf("\nDeleted Successfully \n\n");
break;
} else {
i++;
prev_node = temp_node;
temp_node = temp_node -> next;
}
}
}
} else
printf("\nInvalid Position \n\n");
}
void display() {
int count = 0;
temp_node = first_node;
printf("\nDisplay Linked List : \n");
while (temp_node != 0) {
printf("# %d # ", temp_node->value);
count++;
temp_node = temp_node -> next;
}
printf("\nNo Of Items In Linked List : %d\n", count);
}
int count() {
int count = 0;
temp_node = first_node;
while (temp_node != 0) {
count++;
temp_node = temp_node -> next;
}
printf("\nNo Of Items In Linked List : %d\n", count);
return count;
}
Singly Linked List Example - All Operations
Options
1 : Insert into Linked List
2 : Delete from Linked List
3 : Display Linked List
4 : Count Linked List
Others : Exit()
Enter your option:1
Enter Element for Insert Linked List :
100
Options
1 : Insert into Linked List
2 : Delete from Linked List
3 : Display Linked List
4 : Count Linked List
Others : Exit()
Enter your option:1
Enter Element for Insert Linked List :
200
Options
1 : Insert into Linked List
2 : Delete from Linked List
3 : Display Linked List
4 : Count Linked List
Others : Exit()
Enter your option:1
Enter Element for Insert Linked List :
300
Options
1 : Insert into Linked List
2 : Delete from Linked List
3 : Display Linked List
4 : Count Linked List
Others : Exit()
Enter your option:1
Enter Element for Insert Linked List :
400
Options
1 : Insert into Linked List
2 : Delete from Linked List
3 : Display Linked List
4 : Count Linked List
Others : Exit()
Enter your option:1
Enter Element for Insert Linked List :
500
Options
1 : Insert into Linked List
2 : Delete from Linked List
3 : Display Linked List
4 : Count Linked List
Others : Exit()
Enter your option:3
Display Linked List :
# 100 # # 200 # # 300 # # 400 # # 500 #
No Of Items In Linked List : 5
Options
1 : Insert into Linked List
2 : Delete from Linked List
3 : Display Linked List
4 : Count Linked List
Others : Exit()
Enter your option:4
No Of Items In Linked List : 5
Options
1 : Insert into Linked List
2 : Delete from Linked List
3 : Display Linked List
4 : Count Linked List
Others : Exit()
Enter your option:2
No Of Items In Linked List : 5
Display Linked List :
Enter Position for Delete Element :
3
Deleted Successfully
Options
1 : Insert into Linked List
2 : Delete from Linked List
3 : Display Linked List
4 : Count Linked List
Others : Exit()
Enter your option:3
Display Linked List :
# 100 # # 200 # # 400 # # 500 #
No Of Items In Linked List : 4
Options
1 : Insert into Linked List
2 : Delete from Linked List
3 : Display Linked List
4 : Count Linked List
Others : Exit()
Enter your option:2
No Of Items In Linked List : 4
Display Linked List :
Enter Position for Delete Element :
6
Invalid Position
Options
1 : Insert into Linked List
2 : Delete from Linked List
3 : Display Linked List
4 : Count Linked List
Others : Exit()
Enter your option:
5
------------------
(program exited with code: 0)
Press any key to continue . . .
A singly linked list is a type of linked list that is unidirectional, i.e., it can be traversed in only one direction from the head to the last node (tail).
Each element in a linked list is called a node. A single node contains data and a pointer to the next node, which helps to maintain the structure of the list.
The head is a pointer that points to the first node of the list and, hence, helps us traverse the list.
The last node (also referred to as the tail) points to NULL, which helps us in determining when the list ends.
Common singly linked list operations
1. Search for a node in the ist
You can determine and retrieve a specific node from the front, end, or anywhere in the list.
The worst-case Time Complexity for retrieving a node from anywhere in the list is O(n).
2. Add a node to the list
You can add a node at the front, end, or anywhere in the linked list.
The worst-case Time Complexities for performing these operations are:
- Add an item to the front of the list: O(1)
- Add an item to the end of the list: O(n)
- Add an item anywhere in the list: O(n)
3. Remove a node from the list
You can remove a node from the front, end, or anywhere in the list.
The worst-case Time Complexities for performing this operation are:
- Remove an item from the front of the list: O(1)
- Remove an item from the end of the list: O(n)
- Remove an item from anywhere in the list: O(n)
A singly linked list, along with the functions mentioned above, is implemented in the code snippet below.
#include <iostream>
using namespace std;
// Making a node struct containing a data int and a pointer
// to another node
struct Node {
int data;
Node *next;
};
class LinkedList
{
// Head pointer
Node* head;
public:
// default constructor. Initializing head pointer
LinkedList()
{
head = NULL;
}
// inserting elements (At start of the list)
void insert(int val)
{
// make a new node
Node* new_node = new Node;
new_node->data = val;
new_node->next = NULL;
// If list is empty, make the new node, the head
if (head == NULL)
head = new_node;
// else, make the new_node the head and its next, the previous
// head
else
{
new_node->next = head;
head = new_node;
}
}
// loop over the list. return true if element found
bool search(int val)
{
Node* temp = head;
while(temp != NULL)
{
if (temp->data == val)
return true;
temp = temp->next;
}
return false;
}
void remove(int val)
{
// If the head is to be deleted
if (head->data == val)
{
delete head;
head = head->next;
return;
}
// If there is only one element in the list
if (head->next == NULL)
{
// If the head is to be deleted. Assign null to the head
if (head->data == val)
{
delete head;
head = NULL;
return;
}
// else print, value not found
cout << "Value not found!" << endl;
return;
}
// Else loop over the list and search for the node to delete
Node* temp = head;
while(temp->next!= NULL)
{
// When node is found, delete the node and modify the pointers
if (temp->next->data == val)
{
Node* temp_ptr = temp->next->next;
delete temp->next;
temp->next = temp_ptr;
return;
}
temp = temp->next;
}
// Else, the value was neve in the list
cout << "Value not found" << endl;
}
void display()
{
Node* temp = head;
while(temp != NULL)
{
cout << temp->data << " ";
temp = temp->next;
}
cout << endl;
}
};
int main() {
LinkedList l;
// inserting elements
l.insert(6);
l.insert(9);
l.insert(1);
l.insert(3);
l.insert(7);
cout << "Current Linked List: ";
l.display();
cout << "Deleting 1: ";
l.remove(1);
l.display();
cout << "Deleting 13: ";
l.remove(13);
cout << "Searching for 7: ";
cout << l.search(7) << endl;
cout << "Searching for 13: ";
cout << l.search(13) << endl;
}
Video liên quan