Linked List is a linear data structure where each element is a separate object called node. Each node contains the data and a pointer to the next node.
What is a Linked List?
Ever imagined having a list that can grow and shrink as per your need? Well, we have the answer for you.
Let's say you have a list of 10 elements, and you put those elements in an array. That's fine for now, but what if you want to add more elements to the list (array)? You will have to create a new array with a new size and copy all the elements from the old array to the new one because the size of the array is fixed and their address in memory is in a continuous block. This is a very costly operation. So, what if you could just add the new elements to the list without having to create a new array? This is the case where Linked List comes into play.
Let me introduce Linked List to you. Linked List does not store the data in a continuous block of memory. Instead, it stores the data in nodes connected to each other like a chain. As the nodes are not in a continuous block of memory, the size of the Linked List can grow and shrink as per the need. Each node contains the data and a pointer (memory address) to the next node.
Structure of a Linked List
A Linked List is a collection of nodes. The entry point or the starting node of a Linked List is called the head. The last node of a Linked List points to NULL. The following image shows the structure of a Linked List.
Types of Linked List
To make things more interesting, there are different types of Linked List. Let's have a look at them.
Singly Linked List
Singly Linked List is like a 1-way street, where you can move in only one direction. Here in a Singly Linked List, each node contains the data and a pointer to the next node only. The last node points to NULL. That means the end is the true end. The following image shows the structure of a Singly Linked List.
Doubly Linked List
Let's say you want some flexibility in your Linked List. You want to move in both the directions. Well, Doubly Linked List is the answer to your question. In a Doubly Linked List, each node contains the data and two pointers - one to the next node and one to the previous node. The prev
pointer of the head points to NULL and the next
pointer of the last node points to NULL. The following image shows the structure of a Doubly Linked List.
Besides these two types of Linked List, there is another type of Linked List called Circular Linked List.
Circular Linked List
In a Circular Linked List, you can move in any direction and also you can move from the last node to the first node, and vice versa if it's a Doubly Circular Linked List. In a Circular Linked List, the last node points to the first node.
Doubly Circular Linked List is the same as Circular Linked List, but the last node points to the first node and the first node points to the last node. The following image shows the structure of a Circular Linked List.
Implementation of Linked List
Let's have a look at the implementation of Linked List in C++. We will be using the Singly Linked List for this. The node of the Linked List is defined as follows.
struct Node {
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = NULL;
}
};
The data
variable stores the data of the node and the next
variable stores the pointer to the next node in the Linked List. The constructor of the Node
structure initializes the data
variable with the data passed to it and next
variable with NULL.
The Linked List class is defined as follows.
class LinkedList {
public:
Node* head;
LinkedList() {
head = NULL;
}
};
Here, the head
variable stores the pointer to the first node of the Linked List. The constructor of the LinkedList
class initializes the head
variable with NULL.
But, you want a working Linked List, right? So, let's create a basic Linked List with some nodes. The following code creates a Linked List with 3 nodes.
#include <iostream>
using namespace std;
struct Node {
int data;
Node* next;
Node(int data) {
this->data = data;
this->next = NULL;
}
};
class LinkedList {
public:
Node* head;
LinkedList() {
head = NULL;
}
};
int main() {
LinkedList* list = new LinkedList();
list->head = new Node(1);
list->head->next = new Node(2);
list->head->next->next = new Node(3);
// print the Linked List
Node* temp = list->head;
while (temp != NULL) {
cout << temp->data << " ";
temp = temp->next;
}
return 0;
}
Wait, what's happening here? Let's break it down in steps.
- In the
main
function, we created a new Linked Listlist
and initialized thehead
variable with NULL. - Then, we created a new node with data 1 by calling the constructor of the
Node
structure and assigned it to thehead
variable of the Linked List. - Then, we created a new node with data 2 by calling the constructor of the
Node
structure and assigned it to thenext
variable of the first node,list->head->next
. - Then, we created a new node with data 3 by calling the constructor of the
Node
structure and assigned it to thenext
variable of the second node,list->head->next->next
.
Now, the Linked List looks like this.
Operations on Linked List
Now that you have a basic idea of Linked List, let's have a look at some operations that can be performed on a Linked List.
The operations on Linked List are described in the artcle Linked List - Operations.
References
- "Linked list - Wikipedia" En, https://en.wikipedia.org/wiki/Linked_list.
- "Linked List Data Structure - GeeksforGeeks" Geeksforgeeks, 18 Jun. 2002, https://www.geeksforgeeks.org/data-structures/linked-list/.
- "Linked List Operations: Traverse, Insert and Delete" Programiz, https://www.programiz.com/dsa/linked-list-operations.