As clear from the name, linked list is data structure that have linked elements. Linked list consist of nodes that connect to each other. Each node has two parts, one is the data part and the other is the next pointer that points to the next node.
Types of Linked Lists
There can be three types of linked list:
- Singly linked list
- Doubly linked list
- Circular linked list
Singly Linked List
This is the most basic form of linked lists. In this linked list, each node points to a single node only in the forward direction. The first node is head. The head of a linked list can help access all other nodes of it. The last node of the linked list does not point to any node and stores NULL address. The below diagram shows a singly linked list containing 4 nodes.
The following code creates and displays a linked list. The struct node creates nodes containing a data item of type int and a reference pointer. Note that the code initializes the head as NULL.
The function insert() having return type void, creates the linked list by inserting integer values as data. It takes an integer value data_val as its parameter. The next pointer points to the head. It creates a new node with a data_val and pointer pointing to head. After first iteration of insert(4) call, the linked list consists of a single node having data value 4 with its pointer pointing to NULL.
The function display() that displays the linked list has return type void. It creates a pointer ptr of node type. It starts at the head of the linked list and until the pointer points to NULL address, it keeps printing the data items of the linked list.
#include <iostream>
using namespace std;
struct node {
int data;
struct node *next;
};
struct node* head = NULL;
void insert(int data_val) {
struct node* new_node = (struct node*) malloc(sizeof(struct node));
new_node->data = data_val;
new_node->next = head;
head = new_node;
}
void display() {
struct node* ptr;
ptr = head;
while (ptr != NULL) {
cout<< ptr->data <<" ";
ptr = ptr->next;
}
}
int main() {
insert(4);
insert(9);
insert(3);
insert(5);
insert(2);
insert(1);
cout<<"This is the C++ linked list: ";
display();
return 0;
}
The output of the above code after compilation is:
Doubly Linked List
Doubly linked list is a linked list in which nodes point in both forward and backward direction. Each node in a doubly linked list has two pointers. One pointer points to the node present before and the other points to the node present after. In this way, a programmer can traverse both forwards and backwards from a node in a double linked list. The first node is head. The first pointer of head points to NULL and the second pointer points to the second node. Similarly the last node points to both NULL and second last node. The diagram below shows a doubly linked list having four nodes.
The node of double linked list has two pointers. The code for defining a node of doubly linked list is:
struct node {
int data;
struct node *next;
struct node *prev;
};
The pointer *next points to the next node and pointer *prev points to the previous node.
The below code shows how to create a doubly linked list. The code contains displayList() function that print the doubly linked list in both forward and reverse directions. The push() function creates a node and allocates memory for it. It then assigns value to the node’s attributes.
#include <iostream>
using namespace std;
struct node {
int data;
node* next;
node* prev;
};
void push(node** ptr, int data_val)
{
node* new_node = new node();
new_node->data = data_val;
new_node->next = (*ptr);
new_node->prev = NULL;
if ((*ptr) != NULL)
(*ptr)->prev = new_node;
(*ptr) = new_node;
}
void displayList(node* new_node)
{
node* last;
cout << endl << "DLL in forward"
<< " direction is:" << endl;
while (new_node != NULL) {
cout << " " << new_node->data << " ";
last = new_node;
new_node = new_node->next;
}
cout << endl << "DLL in reverse"
<< " direction is:" << endl;
while (last != NULL) {
cout << " " << last->data << " ";
last = last->prev;
}
}
// Driver Program
int main()
{
node* head = NULL;
push(&head, 5);
push(&head, 8);
push(&head, 3);
push(&head, 4);
cout << "The doubly linked list is: ";
displayList(head);
return 0;
}
The output of the above code after compilation is:
Circular Linked List
Circular linked list is the linked list in which the last node points to the head. No node in a circular linked list points to NULL. So, there is beginning or end in a circular linked list. While traversing a circular linked list, the traversal can start at any node of the circular linked. Like doubly linked list, traversal can be both in forward or backward direction. The traversal stops when it finds the node from where the traversal started. The diagram below shows a circular linked list having 4 nodes.
A circular linked list can be of two types:
- Singly Circular Linked List
- Doubly Circular Linked List
Singly Circular Linked List
In Singly Circular Linked List, the traversal is only in one direction i.e. forward direction. The code for defining a singly circular linked list is:
struct node {
int data;
node* next;
};
It is same as that of the singly linked list.
For example, the below code shows how to create and display a singly circular linked list.
#include <iostream>
using namespace std;
struct node {
int data;
node* next;
};
void push(node** head_ptr, int data_val)
{
node* ptr = new node();
node* temp = *head_ptr;
ptr->data = data_val;
ptr->next = *head_ptr;
if (*head_ptr != NULL) {
while (temp->next != *head_ptr) {
temp = temp->next;
}
temp->next = ptr;
}
else
ptr->next = ptr;
*head_ptr = ptr;
}
void displayList(node* head)
{
node* temp = head;
if (head != NULL) {
do {
cout << temp->data << " ";
temp = temp->next;
} while (temp != head);
}
}
// Driver Program
int main()
{
node* head = NULL;
push(&head, 4);
push(&head, 1);
push(&head, 9);
push(&head, 5);
push(&head, 3);
cout << "The Circular Linked List is:" << endl;
displayList(head);
return 0;
}
The output of the above code after compilation is:
Doubly Circular Linked List
In Doubly Circular Linked List, the traversal is in two directions i.e. forward and reverse direction. The code for defining a doubly circular linked list is:
struct node {
int data;
struct node* next;
struct node* prev;
};
It is same as that of the doubly linked list.
For example, the below code shows how to create and traverse a doubly linked list.
#include <iostream>
#include <string>
using namespace std;
struct node {
int data;
struct node* next;
struct node* prev;
};
void insert(struct node** start,
int data_val)
{
if (*start == NULL) {
struct node* new_node = new node;
new_node->data = data_val;
new_node->next
= new_node->prev = new_node;
*start = new_node;
return;
}
struct node* last = (*start)->prev;
struct node* new_node = new node;
new_node->data = data_val;
new_node->next = *start;
new_node->prev = last;
last->next = (*start)->prev
= new_node;
*start = new_node;
}
void displayList(struct node* start)
{
struct node* temp = start;
cout << endl
<< "Traversed in forward direction is: " << endl;
while (temp->next != start) {
cout << temp->data << " ";
temp = temp->next;
}
cout << temp->data;
cout << endl
<< "Traversed in reverse direction is: " << endl;
node* last = start->prev;
temp = last;
while (temp->prev != last) {
cout << temp->data << " ";
temp = temp->prev;
}
cout << temp->data;
}
// Driver Program
int main()
{
struct node* head = NULL;
insert(&head, 8);
insert(&head, 4);
insert(&head, 5);
insert(&head, 7);
cout << "The circular doubly linked list is: ";
displayList(head);
return 0;
}
The output of the above code after compilation is: