Linked List in C++
What is Linked List Data Structure?
A linear dynamic data structure used to store data elements is known as a linked list. It has several connected nodes, and each node keeps the data and address of the next node. Every node is interconnected using pointers.
Linked list elements using pointers are shown as:
![Linked List in C++](https://static.tutorialandexample.com/cpp/linked-list-in-cpp1.png)
Elements of Linked List
There are two elements in a linked list:
- Data: the value stored in Linked List.
- Next: it contains the address of the next node.
- In a linked list, the first node is called the head, and the last is called the tail. The last node has a null next pointer as no memory location is assigned in that node.
- Data elements in the linked list do not need to store in contagious locations. Nodes can be scattered in memory. We can access nodes at any time, as each node contains the address of the next node.
- Insertion and deletion can be quickly done in the linked list. There is no limit to the data amount in it. It can contain numerous amount of data items. We can add as many data items as possible unRAM is RAM available.
- The linked list saves space for memory as there is no specified number of data items, making it simple to insert and delete from the linked list. Storing the pointer to the next node takes space in the linked list.
Operations in Linked List
We can perform basic operations in a linked list. They are as follows:
- Creating: create the first node
- Insertion: adding a new element
- Deletion: deleting an element
- Search: finding a node
- Traverse: traversing through each node
- Sort: sorting the list in a particular order
1. Creation
In an empty list create operation is used to create the first node (head). After creation, we can insert more nodes into it.
![Linked List in C++](https://static.tutorialandexample.com/cpp/linked-list-in-cpp2.png)
2. Insertion
It adds an element to the linked list. While adding a new data item, we must change the pointers of the previous node and the nodes of the new item being added. The position at which the data item must be inserted must be known.
We can add a new data item in a linked list at three places.
a. At the beginning
Inserting a node at the beginning of the linked list inserts the node making it the head node, and the previous head node becomes the second node of the linked list.
![Linked List in C++](https://static.tutorialandexample.com/cpp/linked-list-in-cpp3.png)
b. At a particular position
It inserts the node at any position specified by the user.
![Linked List in C++](https://static.tutorialandexample.com/cpp/linked-list-in-cpp4.png)
c. At the end
It inserts the node at the end of the linked list, making it the last node (tail).
![Linked List in C++](https://static.tutorialandexample.com/cpp/linked-list-in-cpp5.png)
3. Deletion
This operation deletes the node from the linked list. We must update the pointers to maintain the linked list for deleting the node.
The nodes can be deleted from three positions in a linked list.
a. From beginning
It deletes a node from the beginning of a linked list which means deleting the first node. The second node becomes the head of the linked list by deleting the first node.
![Linked List in C++](https://static.tutorialandexample.com/cpp/linked-list-in-cpp6.png)
b. From any position
It deletes a node at a particular position that the user specifies.
![Linked List in C++](https://static.tutorialandexample.com/cpp/linked-list-in-cpp7.png)
c. From the end
It deletes the linked list’s last node, making the previous one the last node (tail).
![Linked List in C++](https://static.tutorialandexample.com/cpp/linked-list-in-cpp8.png)
4. Searching
This operation is used to find any node in the linked list. We can search for any item using a loop.
- First, make the head node the current node
- Run a loop from the current node till the last node
- Check for the required item in each iteration by comparing it with the current node
- If the result matches, return the position of the item; otherwise, iterate again
5. Sorting
We can sort the linked list in ascending order using a simple sorting algorithm (bubble sort).
- First, make the head node the current node and another node for sorting.
- If the head node is null, it will return
- Else run a loop from the current node till the last node
- The next node will be stored in another node made earlier
- Check if the current node is greater than the next node
- If it is more significant, swap it with the extra node made earlier
- Iterate until the last node is the greatest of all the nodes
6. Traverse
This operation traverses through each node and prints the value of each node from head to tail in a linked list.
C++ Program to implement all the operations in a linked list
CODE
// Linked list operations in C++
#include <stdlib.h>
#include <iostream>
using namespace std;
// Create a node
struct Node {
int data;
struct Node* next;
};
void insertAtBeginning(struct Node** head, int new_data) {
// Allocate memory to a node
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
//Insert the data
new_node->data = new_data;
new_node->next = (*head);
// Move head to the new node
(*head) = new_node;
}
// Insert a node after a node
void insertAtPos(struct Node* prev_node, int new_data) {
if (prev_node == NULL) {
cout << "the given previous node cannot be NULL";
return;
}
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = prev_node->next;
prev_node->next = new_node;
}
// Insert at the end
void insertAtEnd(struct Node** head, int new_data) {
struct Node* new_node = (struct Node*)malloc(sizeof(struct Node));
struct Node* last = *head; /* used in step 5*/
new_node->data = new_data;
new_node->next = NULL;
if (*head == NULL) {
*head = new_node;
return;
}
while (last->next != NULL) last = last->next;
last->next = new_node;
return;
}
// Delete a node
void deleteNode(struct Node** head, int key) {
struct Node *temp = *head, *prev;
if (temp != NULL && temp->data == key) {
*head = temp->next;
free(temp);
return;
}
// Find the key to be deleted
while (temp != NULL && temp->data != key) {
prev = temp;
temp = temp->next;
}
// If the key is not present
if (temp == NULL) return;
// Remove the node
prev->next = temp->next;
free(temp);
}
// Search a node
bool search(struct Node** head_ref, int key) {
struct Node* current = *head_ref;
while (current != NULL) {
if (current->data == key) return true;
current = current->next;
}
return false;
}
// Sort the linked list
void sort(struct Node** head_ref) {
struct Node *current = *head_ref, *index = NULL;
int temp;
if (head_ref == NULL) {
return;
} else {
while (current != NULL) {
// index points to the node next to current
index = current->next;
while (index != NULL) {
if (current->data > index->data) {
temp = current->data;
current->data = index->data;
index->data = temp;
}
index = index->next;
}
current = current->next;
}
}
}
// Print the linked list
void printList(struct Node* node) {
while (node != NULL) {
cout << node->data << " ";
node = node->next;
}
}
// Driver program
int main() {
struct Node* h = NULL;
cout<<"INSERTING AT END :";
insertAtEnd(&h, 1);
printList(h);
cout<<"\nINSERTING 6 AT BEGINNING: ";
insertAtBeginning(&h, 6);
printList(h);
cout<<"\nNSERTING 10 AT BEGINNING: ";
insertAtBeginning(&h, 10);
printList(h);
cout<<"\nINSERTING 3 AT END: ";
insertAtEnd(&h, 3);
printList(h);
cout<<"\nINSERTING 2 AT NEXT NODE: ";
insertAtPos(h->next, 2);
cout << "\n\nLINKED LIST: ";
printList(h);
cout<<"\n\nDELETION: ";
cout<<"\nDELETING 3RD NODE";
cout << "\nLINKED LIST AFTER DELETION: ";
deleteNode(&h, 3);
printList(h);
cout<<"\n\nSEARCHING";
cout<<"\nSEARCHING 3 IN THE LIST";
int item_to_find = 3;
if (search(&h, item_to_find)) {
cout << endl << item_to_find << " is found";
}
else
{
cout << endl << item_to_find << " is not found";
}
cout<"\n\nSORTIG THE LINKED LIST";
sort(&h);
cout << "\nSORTED LIST: ";
printList(h);
}
OUTPUT
![Linked List in C++](https://static.tutorialandexample.com/cpp/linked-list-in-cpp9.png)
Types of Linked Lists
There are mainly three types of linked lists:
- Singly linked list
- Doubly linked list
- Circular linked list
1. Singly Linked List
A singly linked list is referred to as a linked list in which we can traverse it from one direction and is thus also known as a unidirectional linked list. When talking about a linked list, it simply means a singly linked list.
![Linked List in C++](https://static.tutorialandexample.com/cpp/linked-list-in-cpp10.png)
It can be represented as:
struct node
{
int data;
struct node *n; //next node
}
2. Doubly Linked List
It contains two pointers. The doubly linked list is a data structure with three parts, data, and two addresses. A doubly linked list is a list with three parts in a single node: one data part, a pointer to the previous node, and one pointer to the next node.
In a doubly linked list, there are two address parts: one stores the next node’s address, and the other stores the previous node’s address.
![Linked List in C++](https://static.tutorialandexample.com/cpp/linked-list-in-cpp11.png)
It can be represented as:
struct node
{
int data;
struct node *n; //next node
struct node *p; //previous node
}
3. Circular Linked List
A circular linked list is a singly list in which the last node is connected to the first node. It does not have any starting and ending nodes. The circular list can be traversed in any direction.
![Linked List in C++](https://static.tutorialandexample.com/cpp/linked-list-in-cpp12.png)
It can be represented as:
struct node
{
int data;
struct node *n; //next node
}
Advantages of Implementing Linked List
- It is a dynamic data structure; thus, no size is fixed.
- Operations like insertions and deletion are accessible in the linked list.
- There is efficient memory usage because of no fixed size.
- Stack and queue can both be implemented using a linked list.
Disadvantages of Implementing Linked List
- Each node takes more memory than the array for the data part and the pointer variable.
- We cannot traverse the linked list randomly. We need to access all the nodes for traversing a single node.