When it comes to dynamically storing data items, linked lists are similar to an array. An array is a linear data structure that stores all of the data items, allowing us to transfer the elements of the array in a continuous operation. Whereas data elements in the linked list are not kept in continuous memory locations when they are stored. There is the starting point in the linked list which is called the head and the ending point is called the tail of the linked list in C++ programming language. In a linked list, there are nodes that store data objects in it. The node has two parts: the part contains the data object in itself and the second part contain the pointer toward the node after it. The final node of the linked list contains the null pointer.
We are using a linked list when we have an array to store the data because in arrays we have to tell the length of the array during the declaration of the array. But in linked lists sizing is not a problem anymore. The length of the linked list will expand as the program requires but the list is constrained by the capacity of memory that is available. The linked list can perform multiple operations in C++ language which are: insertion, deletion, traversal, search and sort operations. To understand these operations of the link list, let us implement the example and understand how a linked list works in C++ programming language. We also explore how these operations work in the linked list.
Example:
Let us now begin to develop the C++ programming language’s linked list example. Launch the compiler and begin writing code to put the example into practice. We must include the header file after running the translator to make it simple and easy to access the built-in methods, classes, and other components that we wish to include in the C++ programming language program.
#include <stdlib.h>
using namespace std;
The “iostream” package is the first fundamental package in C++ and is used by all programs because it allows users to provide input and view output. The second standard library header “stdlib.h” provides dependable and effective routines for the allocation of memory dynamically to C++ programmers. The “#” sign instructs the interpreter to fetch the packages, followed by the “including” keyword, telling it to incorporate the library. Finally, the library name is written in the “<>” tokens. The last sentence, “using namespace std,” is necessary to provide context for the code.
Initializing the Struct
Next, we will create the structure of the name “Node” so that we formed the node of the linked list. After creating the node, we will declare the parts of the node in the structure. The first part of the node is where we store the data elements. So, we have declared an integer-type variable “info” to store the data elements. The next part is a pointer variable “followNode” that will move the pointer toward the next follownode in the linked list. The details are as follows:
{
int info;
struct Node* followNode;
};
Inserting Data Elements in the Linked List
We have created multiple functions so that we can insert the data elements in the linked list which we want to create in C++ programming language.
beg_insert() Function:
We have created a user-defined function in C++ programming language which is the beg_insert() function. As the name suggests, we will use this function to insert the data at the beginning of the linked list. The function beg_insert() takes two arguments which are “head_info” which is the pointer to the head pointer of the linked list and the second argument is “new_info” which is the date of the new follownode that is to be inserted. Next, the function has created a “cur_node” of type “Node” by using the malloc() function. The “cur node” is then initialized with the “new info” parameter and its pointer is set to the connected list’s head. Using the “head info” reference, the linked list’s head is initially listed to the “cur node”.
{
struct Node* cur_node = (struct Node*)malloc(sizeof(struct Node));
cur_node->info = new_info;
cur_node->followNode = (*head_info);
(*head_info) = cur_node;
}
mid_insert() function:
Now, we have created another function to enter the data elements in the middle of the liked list which is the mid_insert() function. In the mid() function, we have to take two arguments which are “pre_node” which is the pointer of the “Node” type, and “new_info” which is the variable that stores the new data in itself of integer type. We have used the “if” statement to check the “pre_node if it is null or not in the function body, we have declared a “cur_node” and stored the “new_info” in it. Then we created a “next” pointer of the “new_info” which points towards the next node of the “pre_node”.
{
if (pre_node == NULL)
{
cout << "The Previous Node Can't be NULL";
return;
}
struct Node* cur_node = (struct Node*)malloc(sizeof(struct Node));
cur_node->info = new_info;
cur_node->followNode = pre_node->followNode;
pre_node->followNode = cur_node;
}
end_insert() Function:
We have created this function so that we can enter the data elements at the end of the linked list. We have declared the same arguments as we have declared in the beg_insert() function. This function first checks if the list is empty or not. Put the “new info” at the beginning of the list and return it if the list was also null. If it is not null, the procedure will proceed through the list until it hits the “last node” node. The “new info” is then added as the “last node” node at the end of the list.
{
struct Node* cur_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last_node = *head_info;
cur_node->info = new_info;
cur_node->followNode = NULL;
if (*head_info == NULL)
{
*head_info = cur_node;
return;
}
while (last_node->followNode != NULL)
{
last_node = last_node->followNode;
last_node->followNode = cur_node;
return;
}
}
Taking a Node Out of a Linked List
To remove the present nodes from the linked list, we have now built a new method called delete node(). It first determines whether the head node itself has the new_key that needs to be erased. If so, the head reference to the followNode is updated. Using a loop, it will locate the node that contains the new_key to be destroyed. When a node is discovered, the “pre” node updates the followNode pointer of the node which will be destroyed so that it can be deleted without being seen. Finally, the free() function is used to release the storage.
{
struct Node *temp_var = *head_info, *pre;
if (temp_var != NULL && temp_var->info == new_key)
{
*head_info = temp_var->followNode;
free(temp_var);
return;
}
while (temp_var != NULL && temp_var->info != new_key)
{
pre = temp_var;
temp_var = temp_var->followNode;
}
if (temp_var == NULL)
{
return;
}
pre->followNode = temp_var->followNode;
free(temp_var);
}
Search the Node in the Linked List
The function search() takes two arguments, which are the pointer to the “head_info” of the linked list and the “new_key” which is to be searched. The function traverses the linked list and checks if the current node’s data matches the “new_key”. If the “current” node’s data matches the “new_key”, the function returns true. If the “current” node’s data does not match the “new_key”, the function moves to the followNode. If the “current” node becomes NULL, the function returns false.
{
struct Node* current = *head_info;
while (current != NULL)
{
if (current->info == new_key)
{
return true;
}
current = current->followNode;
}
return false;
}
Sorting the Node’s Components in the Linked List
In C++ programming, the sort() method is used to arrange the members in the linked list in increasing order. First, it is determined whether the “head info” reference is NULL. If so, we return. After that, the list is repeated several times till the loop’s termination. Checking if any further information is present on the “current” node then on the “index” node comes next. If so, we exchange the data between the two nodes. The “index” node is then transferred to the followNode. The procedure is then repeated up until the completion of the list.
{
struct Node *current = *head_info, *index = NULL;
int temp_var;
if (head_info == NULL)
{
return;
}
else
{
while (current != NULL)
{
index = current->followNode;
while (index != NULL)
{
if (current->info > index->info)
{
temp_var = current->info;
current->info = index->info;
index->info = temp_var;
}
index = index->followNode;
}
current = current->followNode;
}
}
}
Display the Node in the Linked List
The function display() takes a pointer to the head of the linked list as a parameter. After that, it goes through the list and shows every node’s information. When it gets to the completion of the list, it stops.
{
while (node != NULL)
{G
cout << node->info << " ";
node = node->followNode;
}
}
Calling the Functions in main() Function
We have written the main() function so that we can start writing the driver’s code of the program in the main() function body. First, the “head_val” pointer is initialized to NULL of the “Node” type. Then, we called the insert functions which we have created globally and we defined each function of insert and passed the value in it. To display the linked list on the user’s console window, we have called a user-defined display() function. call the sort() so that we can array the data in the linked list. To delete the node from the linked list, we have called the delete_node() function and passed the data elements which we want to delete. If we want to find any element of the node, we have called the search() function and passed the element in it.
{
struct Node* head_val = NULL;
beg_insert(&head_val, 34);
beg_insert(&head_val, 10);
end_insert(&head_val, 48);
mid_insert(head_val->followNode, 72);
cout << "*---Implementation of Linked List in C++---*" << endl;
cout << "\nThe Input Linked list is: ";
display(head_val);
sort(&head_val);
cout << "\n\nAfter Sorting the Input List: ";
display(head_val);
cout << "\nAfter deleting an element: ";
delete_node(&head_val, 48);
display(head_val);
beg_insert(&head_val, 63);
beg_insert(&head_val, 84);
end_insert(&head_val, 11);
mid_insert(head_val->followNode, 100);
cout << "\n\nThe Updated Linked list is: ";
display(head_val);
sort(&head_val);
cout << "\nAfter Sorting the Input List: ";
display(head_val);
int find_data;
cout << "\n\nEnter the element which you want to find? ";
cin >> find_data;
if (search(&head_val, find_data))
{
cout << "The element " << find_data << " is found...";
}
else
{
cout << "The element " << find_data << " is not found...";
}
}
Shown Below is the C++ programming language outcome of the scenario from the above compilation.
Conclusion
The linked list in the C++ programming language and the distinction between an array and a linked list were both covered in this article. We have talked about the linked list’s various operations. We first constructed a linked list scenario, then we constructed each operation in the illustration with a comprehensive description of each line of C++ code.
