Updated April 15, 2023
Introduction to C++ linked list
Linked List is the part of the data structure and most important as well. In C++ linked list is implemented by using structure and pointers. The basic working of the link is the same in all programming languages like it is the collection of many nodes together, and nodes contain data and address of the next node. Here we are using pointers to implement this.
Syntax
We use structure to create a linked list. this structure contains data and a pointer to the next node. We are creating a structure using the struct keyword here; data can be anything, and we are dining the pointer using the ‘*’ symbol. For better understanding, see the syntax below;
struct node // structure name
{
int data; // your data
node *next; // your pointer
};By the above syntax, now we have some understanding of how to create a simple linked list in C++ using structure.
How linked list work in C++?
As of now, we know that the linked list is a data structure and used to store data. We can use a linked list where data is dynamic, and we do not know the number of data or records because they can change according to inputs. So, in this case, we can go for it because we are not able to predicate data. If we talk in more detail linked list contains many nodes. This node further contains data and pointer to the next node; all nodes are connected. We have different types of linked lists available. The linked list data structure is often used to manipulate data like delete operation, update specific records, etc. They are not very much recommended for searching operations because they do not contain index mapping with them as we have in the array. So they will take some time because it has to traverse the whole linked list to search for an input inside any number of nodes. Now we will discuss the types of the linked list, which are as follows see below;
1. Singly Linked list
Singly linked list is also a collection of different nodes. Nodes are further divided into two parts: data and another one is the address to the nest node. We also have the head and tail of the linked list. The singly linked list is also created by using the structure in C++, which will hold the data and pointer to the same structure. Head is the first node in the linked list, and its address is required to access our complete linked list. The tail represents the last node if the linked list does not store the address as it is the last one, so it will point to NULL. We can see one diagram below for a better understating of it.
2. Circular linked list
As the name suggests, this linked list data structure formed a circle. The means all nodes are connected; there is no NULL reference, and it formed a circle. By using a circular linked list, we can start traversing from any node. In a circular linked list, the last node pointer will point to the first node. This linked list provides basic operations like delete, insert, and search.
- insertion: If you want to insert a row in the circular linked list, so we can insert it at the end, at the start of a linked list, or we can add it between the nodes as well.
- Deleting: While deleting any data from a circular linked list data structure, first we delete it, and then we try to free the allocated memory from it. For this operation, we maintain current and previous pointer in our program.
- Searching or Traversing: We traverse in the linked list through every node till we reached the NULL reference, but this the case with a singly linked list. But in the circular linked list, we traverse until we reached the first node.
3. Doubly linked list
A doubly linked list is also a data structure that is made up of with the collection of nodes that are connected. But here, this node is divided into three parts one is data, the pointer to the next node, and one more extra pointer, which is the address to the previous pointer. In this, we have a head and tail. We would only be required to have a pointer of the first node traverse to the whole linked list. Still, the tail will point to NULL, but we can traverse in both directions because it contains the previous node pointer as well.
Points to remember;
- It maintains data and address to the node by which they are connected. By this only we can access them easily.
Example of C++ linked list
In this example, we create a singly linked list with five nodes and print the value at the end.
Code:
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node* next;
};
int main()
{
Node* one = NULL;
Node* two = NULL;
Node* three = NULL;
Node* four = NULL;
Node* five = NULL;
one = new Node();
two = new Node();
three = new Node();
four = new Node();
five = new Node();
one->data = 10;
one->next = two;
two->data = 20;
two->next = three;
three->data = 30;
three->next = four;
four->data = 50;
four->next = five;
five->data = 80;
five->next = NULL;
std::cout << "linked list got created" << std::endl;
while (one != NULL) {
std::cout << "Data inside linked list is ::" << std::endl;
cout << one->data << " ::";
one = one->next;
}
return 0;
}Output:
Conclusion
By using a linked list data structure, we can handle the dynamic data very easily. Also, by using the Linked list data structure, we can make the manipulation very fast because it works on the concept of nodes. But sometimes, it is not feasible with data search operations. We have a different type of linked list that can be used depending upon the requirement.
Recommended Articles
This is a guide to C++ linked list. Here we discuss How linked list works in C++ and Example along with code and output. You may also have a look at the following articles to learn more –
