TL;DR – A linked list in C++ is a form of data structure. It stores data that is connected by pointers in a consistent pattern.
Contents
What is a Linked List in C++?
There are two types of linked lists: a singly-linked list and a doubly-linked list.
The singly-linked list contains nodes that only point to the next node. The C++ doubly linked list has nodes that can point towards both the next and the previous node.
A node has two parts: the data part and the next part. The data part contains the stored data, and the next part provides the address of the next node.
The first node of a linked list is called the head, and the last node is called the tail. The list starts traversing from the head, while the tail ends the list by pointing at NULL.
Linked List Implementation
Let's create a structure for a single node first. Since a node consists of the data part and the next part, here is how the structure looks:
struct Node {
int data;
struct Node *next;
};As you can see, the struct node comprises of two parts: the int data which represents the data part that holds the integer value, and the node next which represents a node pointer called next.
Creating C++ Linked List
To create a linked list, you have to launch a class. It will include the functions that control the nodes:
#include <bits/stdc++.h>
using namespace std;
int main() {
class Node {
public:
int data;
Node * next;
};
}Let's create three nodes in sequence. Make sure that each node is pointing to NULL at first since the pointers will be added later as you input the data.
#include <cstddef>
using namespace std;
class Node {
public:
int data;
Node * next;
};
int main() {
Node * head = NULL;
Node * second = NULL;
Node * third = NULL;
head = new Node();
second = new Node();
third = new Node();
}Next, let's put data values and pointers into each node. Each node, except the third one, should point to the subsequent nodes. The third node’s tail should point to NULL.
#include <cstddef>
using namespace std;
class Node {
public:
int data;
Node * next;
};
int main() {
Node * head = NULL;
Node * second = NULL;
Node * third = NULL;
head = new Node();
second = new Node();
third = new Node();
head->data = 1;
head->next = second;
second-> data = 2;
second-> next = third;
third-> data = 3;
third-> next = NULL;
}After filling out the data part and the next part in each node, the linked list is now complete. You can start to traverse the list starting from the head.
Linked List Manipulation
After creating a fully functioning linked list, you might want to see its output. Hence, you can display it by printing the values of the nodes.
Basically, you should create a temporary node and point it to the head. Then the pointers will continue until all the values of the nodes are printed:
#include <cstddef>
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node * next;
};
void print_list(Node * n) {
while (n != NULL) {
cout << n->data << " ";
n = n->next;
}
}
int main() {
Node * head = NULL;
Node * second = NULL;
Node * third = NULL;
head = new Node();
second = new Node();
third = new Node();
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
print_list(head);
}Insertion
Aside from displaying the list's output, you can also manipulate it by inserting new nodes into the list. It's pretty easy, and there are three ways you can choose.
Inserting at the Start
Inserting a new node at the start of the list means that the new node will serve as the new head. Since it will push the former head aside, the process uses the push() function.
#include <cstddef>
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node * next;
};
void print_list(Node * n) {
cout << "\nPrinting new list..." << endl;
while (n != NULL) {
cout << n->data << " ";
n = n->next;
}
}
void push(struct Node ** head_ref, int new_data) {
struct Node * new_node = (struct Node * ) malloc(sizeof(struct Node));
new_node->data = new_data;
new_node->next = ( * head_ref);
( * head_ref) = new_node;
}
int main() {
Node * head = NULL;
Node * second = NULL;
Node * third = NULL;
head = new Node();
second = new Node();
third = new Node();
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
print_list(head);
push(&head, 11);
print_list(head);
}As you can see in the code, it inserts the new node as the head. It also fills the data within the node. Moreover, it adjusts the pointer to start from the new head.
Inserting at the End
If you add a new node at the end of the list, it'll become the end of the traversal within the list. In other words, you should set the new node to point at NULL.
#include <cstddef>
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node * next;
};
void print_list(Node * n) {
cout << "\nPrinting new list..." << endl;
while (n != NULL) {
cout << n->data << " ";
n = n->next;
}
}
void append(struct Node ** head_ref, int new_data) {
struct Node * new_node = (struct Node * ) malloc(sizeof(struct Node));
struct Node * last = * head_ref;
new_node->data = new_data;
new_node->next = NULL;
while (last->next != NULL)
last = last->next;
last->next = new_node;
}
int main() {
Node * head = NULL;
Node * second = NULL;
Node * third = NULL;
head = new Node();
second = new Node();
third = new Node();
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
print_list(head);
append(&head, 11);
print_list(head);
}Aside from adjusting the pointer of the new node, don't forget to fill in the data. You should also set the former tail to point to the new node since it becomes the new tail.
Inserting at a Specific Position
The purpose of this method is to put a new node between the head and the tail. You have to fill the data and adjust the pointer of the new node with its previous node.
#include <cstddef>
#include <iostream>
using namespace std;
class Node {
public:
int data;
Node * next;
};
void print_list(Node * n) {
cout << "\nPrinting new list..." << endl;
while (n != NULL) {
cout << n->data << " ";
n = n->next;
}
}
void insertAfter(struct Node * prev_node, int new_data) {
if (prev_node == NULL) {
printf("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;
}
int main() {
Node * head = NULL;
Node * second = NULL;
Node * third = NULL;
head = new Node();
second = new Node();
third = new Node();
head->data = 1;
head->next = second;
second->data = 2;
second->next = third;
third->data = 3;
third->next = NULL;
print_list(head);
insertAfter(second, 11);
print_list(head);
}The pointer of the new node and the previous node swap, which means the previous node will point to the new node, whereas the new node will point to the next node. That way, the traversal process will run on the right track.
Linked List C++: Useful Tips
- When forming a linked list, make sure all the nodes are connected.
- You start creating a linked list by filling data in each node to set pointers between the nodes.