It’s always never too late to learn new skills. Let’s take some time and look at this fundamental and useful data structure in our daily lives. What is a linked list in C++? It’s a type of data structure that uses pointers for its implementation. It will be very wise for you to also look at pointers since they will give you a deeper understanding of the Linked List. Nevertheless, I will try as much as possible to make this simple and understandable.
We can also define a Linked List as a linear dynamic data structure where objects referred to as Nodes are stored randomly in the memory. That means the nodes are not stored in a contiguous memory location like arrays. These elements are linked to one another using pointers.
The linked list contains two parts; the actual data of the element is stored on the first part, while the second part, called the link, has a pointer that points to the next node in the list. Each item holds information needed to go to the next item.
Uses of Linked List
- It is possible to store values of primitive data types in the singly linked list.
- Linked list assists in the utilization of space since it’s not in a contiguous memory location hence the node can reside anywhere in the memory and linked together.
- We cannot have an empty node in the linked list.
- It’s not limited to the memory size, and no need for the first declaration.
Need for Linked List
- The array size is fixed; its size must be known early enough.
- Inserting a new element in an array is expensive. These elements are stored in a contiguous memory hence inserting an element needs shifting all its predecessors.
- Increasing the size of an array is expensive. This means at run time, it’s almost impossible to expand the size of the array.
A linked list has the following advantages
- It’s easy to add or remove elements from the middle of the list
- No need to define the linked list initial size at the time of declaration.
- The access time of a linked list is less.
Linked List has some disadvantages
- There is no random access – elements in a linked list are accessed sequentially starting from the beginning of the first node. It’s impossible to do a binary search.
- It uses more memory, as we need extra space for pointers.
Creating a Linked List
The first node in a Linked List is called the “head,” while the last is called the “tail.” In that case, we start the list traversing from the head to the tail. The last node does not point to any other node but points to null.
Example:
Struct Node
{
int data;
Struct Node *next;
};
From the above example, linked list functionality is achieved by using structures and pointers. The struct Node has two parts: the “int,” which represents the actual data part that holds integer value, and the “Node,” which holds the pointer called “next.” The pointer contains the address of the next node.
From this scenario, you can note that having access to the first node gives us access to any other node in the linked list and easily access the next node, but there is no way for us to access the previous node in a singly linked list.
Let’s now create the linked list. In the first part, we will create a node, also known as a structure.
#include <bits/stdc++.h>
using namespace std;
class Node {
public:
int data;
Node * next;
};
The second part will be to keep track of the first node. If we access the first node, then we have full access to the entire linked list. We will be creating a linked list with three nodes. The first is the head, and the last is the tail. At first, we make sure all nodes point to NULL since we will add pointers as we input the data.
int main() {
Node * head = NULL;
Node * second = NULL;
Node * tail = NULL;
head = new Node();
second = new Node();
tail = new Node();
}
The third stage will be now to put data values and pointers of each node. But remember the tail points to NULL; hence we will not put data values to this.
head->data = 1; head->next = second; second-> data = 2; second-> next = tail; tail-> data = 3; tail-> next = NULL;
Our linked list is now fully completed. Let’s have the full code below of creating the linked list before we can now start traversing from the head.
#include <iostream>
using namespace std;
struct node{
int data;
Node *next;
};
int main() {
Node * head = NULL;
Node * second = NULL;
Node * tail = NULL;
head = new Node();
second = new Node();
tail = new Node();
head->data = 1;
head->next = second;
second-> data = 2;
second-> next = tail;
tail-> data = 3;
tail-> next = NULL;
}
We may need to print out the linked list items. This can be achieved using two methods. First, you can create a temporary node and point it to the head.
void print_list(Node * p)
{ while (p != NULL) {
cout << p->data << " ";
p = n->next;
}
}
print_list(head);
The second way is to use the current pointer. This current pointer will keep track of the node we are printing. After printing the current node, we set the current pointer to point to the next node and again print. This process will be iterative until we reach the end of the linked list, where the next will be NULL.
Example:
Class LinkList{
public:
LinkList() {
head = null;
tail = null;
}
void create_node(int value) {
node *temp = new Node;
temp->data = value;
temp->next = null;
if (head == null) {
head = temp;
tail = temp;
}
else
{
tail->next = temp;
tail = temp;
}
}
void printLinkList() {
Node * current = head;
while (current != null) {
cout << current->value << endl;
current = current->next;
}
}
private:
Node *head;
Node *tail;};
Linked List operations
We can perform different manipulations in a Linked list just like any other data structure, but we cannot do random access in a linked list. That means to access a node in a linked list, we have to transverse from the start: There are various operations that we can perform in a linked list, such as Insertion and deletion. Let’s start by looking at insertion.
Insertion
This is simply inserting a new node item in the linked list. When we insert in a linked list, we must modify the next pointers of the previous node and the next node of the newly inserted item. There are different positions where we can insert a new data item in a linked list. These positions include:
Insertion at the start
While inserting a node at the start, we will have to do three steps. The first step will be to create a new item and set its value. Since this will be our first item as the head, we will then link this new item to point to the current head, and lastly, we will set the newly inserted item as the head of the list.
Let’s illustrate a list 4->6->8->10->12; we need to insert a new item 2 to be the head. Our new list will be 2->4->6->8->10->12.
Example of code to achieve this;
struct Node{
int data;
struct Node *next
};
Void pushNode(struct Node** head, int value){
struct Node* new_Node = new Node;
New_Node->data = value;
New_Node->next = (*head);
(*head) = new_Node;
}
In the above code, we started by creating a linked list node. Then we used the method “void pushNode” to insert a new node at the beginning of the list. We went ahead and using “New_Node-> data = value;” assigned data to the node. Using “New_Node-> next = (*head);” we set the new node as the head, and lastly, we moved the head to the new node.
Insertion at the end
This will involve inserting a new list at the end of the list. This means that the newly inserted item will be the tail.
Let’s an example of a list 4->6->8->10->12. We want to insert a new node 14 to be the head. Our new list will be 4->6->8->10->12->14. We will add the new item to null, so if the list is empty, then the new node becomes the first item.
Example of code to achieve this;
void append(struct Node** head, int node_data){
struct Node* new_node = new Node;
new_node->data = node_data;
new_node->next = NULL;
if (*head == NULL){
*head = new_node;
return
}
while (last->next != NULL){
last = last->next;
last->next = new_node;
return;
}
In the above code, we started by inserting a node at the end of the linked list using the method “void append(),” we then created, allocated, and assigned data to the node. Lastly, we set the next pointer of the new node to null. We also made sure to check if the linked list is empty. If it’s empty, we make the new node the last node. Else we transverse to the last node and change the last node.
Insertion at a particular position
This might be a little hard. In this case, we do not want to disturb the head nor the tail. We aim to insert a new item between any two consecutive nodes. We will be inserting a new item between the previous and the current.
To achieve this, we can follow two steps. The first step will be to passing the address of the new node in the next field of the previous, and then in the next field of the new node, we pass the address of the current node.
Example of code to achieve this;
void insertPosition(int position, int data){
Node *prev = new Node;
Node *current = new Node;
Node *temp = new Node;
curr = head;
for(int k = 1; k < position; k++) {
prev = current;
current = current->next;
}
temp->data = data;
prev->next = temp;
temp->next = current;
}
We can also achieve the same using the if statement:
void insertPosition(struct Node* prev, int node_Data)
{
if (prev == NULL)
{
cout<<"previous node cannot be NULL";
return;
}
struct Node* new_Node =new Node;
new_node->data = node_Data;
new_node->next = prev->next;
prev->next = new_node;
}
In the above code, we use the method “void insertPosition()” to insert a new node after a particular node. The previous node should not be empty, and we check this using the if statement. We then create, allocate, and assign data to the new node and make the new node next to the previous node and move the next of the previous node as the new node.
Deletion
As we can add an item to the linked list, we can also delete an item from the linked list. The basic rule of deletion is to declare a temporary pointer that will point to the node that is to be deleted. After deletion, we then adjust the pointers ‘next pointer and other pointers’ to keep the list intact. This is a little simpler to implement.
We also have three operations on deleting the linked list items, which include:
Deletion at the start
To achieve this, we will take the item after the head item and save it. We then free this head item and set the next item to be the head.
Node* deleteNode(struct Node* head)
{
if (head == NULL)
return NULL;
Node* temp_node = head;
head = head->next;
delete temp_node;
return head;
}
int pop() {
int r = 0;
Node * nextNode = NULL;
nextNode = head->next;
r = head->value;
delete head;
head = nextNode;
int r;
}
We use Node* deleteNode(struct Node* head) to delete the first node in the linked list in the above code. We then move the pointer to the next node and lastly make the next node as the first node “head”.
Deletion at the end
The only difference from deleting the first item is that in this case, we will have to set the last item before the tail as the new tail that will point to null.
int removeLastNode() {
int r = 0;
if (head->next == NULL) {
r = head->value;
delete head;
return r;
}
Node * current = head;
while (current->next->next != NULL) {
current = current->next;
}
r = current->next->value;
delete current->next;
current->next = NULL;
return r;
In the above code, we start by checking the list. If there is only one element in the list, we remove it. If not, we get the second last element to be the last and now remove the last bode.
Deletion at a particular position
In this case, after removing, we will need to change the location of the previous items on where the node will point. To achieve this, we will first loop through to the node before the element to delete and save the element we need to delete in a temporary pointer. We set the previous node to point to the new node after the item we wish to delete, and lastly, delete the temporary pointer holding the node we wish to delete.
Types of Linked List
There are three different types of linked lists. This includes; singly linked list, doubly linked list, and circular linked list.
Singly-linked list
This is a type of linked list that can only be transverse in one direction. It’s unidirectional. Each node contains a pointer to the next node in a linear sequence.
Doubly linked list
In this case, each data part contains two addresses, i.e., prev and next. The prev points to the previous node while the next points to the next node. With a doubly-linked list, it is possible to navigate both front and back. A good example is in browsers to implement backward and forward, or even the undo and redo functionality.
Circular linked list
In a circular linked list, the last node holds the pointer “address” to the first node. i.e., the tail has an address to the head hence forming a circular chain. A good example of this is a multiplayer game. The pointer moves forward as a player chance ends until all players have had a chance to play and then loops back to the first player and so on.
Application of Linked List
- It can be used when implementing queues and stacks
- A linked list can be used to store mathematical polynomial
- On implementation of graphs as adjacency lists
- When we require dynamic allocation of memory
Conclusion
Linked lists are data structures that store items in a non-contiguous memory allocation. They contain the node part and the pointer part. The node holds the actual data value while the pointer holds the address to the next node in the linked list. The last first element in the list is referred to as the head, while the last element in the linked list is referred to as the tail. The tails always point to null except for the circular linked list where it points to the head.
The linked list supports various operations such as insertion, deletion, and transversal. You can always insert or delete a new item in the linked list at the begging, at the end of the linked list, or at the specific position you may wish two.
We have three types of the linked lists, which include: singly, doubly, and circular. So far, we have managed to cover these concepts, and I hope this tutorial helps you understand the linked list in C++ in more depth.
