**Linked List** is a **linear data structure** that consists of nodes. Each node in the linked list has both **“data”** and **“links”** i.e pointers of the next or previous nodes or both. These nodes are connected to the adjacent nodes using links or pointers.

The nodes in the linked lists need not be stored at contiguous memory locations. This article mainly explains all types of linked lists data structures and also explains the applications and representation of each linked list.

So, the different types of linked lists in data structures are:

- Singly linked list
- Doubly linked list
- Circular linked list
- Doubly circular linked list

Every type of linked list has its properties and is different from another linked list in both its representation and implementation part. The below article explains all types of linked lists in detail.

## Singly Linked List

- The first and most simple type of linked list is a singly linked list. The singly-linked list consists of nodes.
- Each node of the singly linked list consists of a data value and a pointer to the next node.
- The first node of the singly linked list is called as
**head**of the linked list. - The last node of the singly linked list is called the tail of the linked list and it points to null, which indicates the end of the linked list.
- A singly linked list is traversed only in one direction i.e, only unidirectional traversal is possible in the singly linked list which is from the head to the last node or the tail.

The below image clearly explains what the singly linked list looks like:

In the above image, **next** represents the pointer to the next node.

**Representation of singly linked list in C++, Python, and java is as follows:**

**C++ representation:** of a singly linked list.

```
#include <bits/stdc++.h>
using namespace std;
```*// Main class which represents each node in the linked list*
class Node {
public:
int val;
Node* next;
};
*// Driver code*
void print_slist(Node* node) {
while (node != NULL) {
cout << node->val << " ";
node = node->next;
}
}
*// Driver code*
int main() {
*// creating nodes of the linked list*
*// head of the linked list*
Node* head = NULL;
*// second node of the linked list and initializing it to the null value*
Node* second = NULL;
*// third node of the linked list and initializing it to the null value*
Node* third = NULL;
*// fourth node of the linked list and initializing it to the null value*
Node* fourth = NULL;
*// creating the objects of the node class*
*// every node if instantiated using a new keyword*
head = new Node();
second = new Node();
third = new Node();
fourth = new Node();
*// assigning data to all nodes formed*
head->val = 30;
*// creating a link to the head node and the second node*
head->next = second;
*// assigning data to the second node*
second->val = 40;
*// creating a link to the second and the third node*
second->next = third;
*// assigning data to a third node*
third->val = 50;
*// creating a link to the third and the fourth node*
third->next = fourth;
*// assigning data to the fourth node*
fourth->val = 60;
*// making the tail pointer point to null which indicates the end of the linked list*
fourth->next = NULL;
*//printing the formed linked list*
print_slist(head);
return 0;
}

**Output:**

```
30 40 50 60
```

**Python representation:** of the singly linked list.

*# Main class which represents each node in the linked list*
class Node:
*# constructor which is used to allocate given data to the node formed*
def __init__(self, val):
self.val = val
*# initializing the next node pointing to none(null) value*
self.next = None
*# A class that creates the linked list which means it connects the nodes*
class LinkedSList:
*# default constructor created to initialize the object*
def __init__(self):
self.head = None
*# method for printing the elements in a linked list*
def print_SList(self):
temp = self.head
*# traverse till the end of the list*
while (temp):
print (temp.val, end=" ")
temp = temp.next
*# Driver code*
if __name__=='__main__':
*# Initialising a linked list by creating its object*
linked_list = LinkedSList()
*# Initialising the head of the linked list with a value of 30*
linked_list.head = Node(30)
*# second node of the linked list*
second = Node(40)
*# third node of the linked list*
third = Node(50)
*# fourth node of the linked list*
fourth = Node(60)
*# now, we need to create the link between these three nodes*
*# this is achieved by using*
linked_list.head.next = second
*# creating a link between the second and the third node*
second.next = third
*# creating a link between the third and the fourth node*
third.next = fourth
*# print the formed linked list*
linked_list.print_SList()

**Output:**

```
30 40 50 60
```

**Java representation:** of singly linked list.

*// Main class which represents the linked list*
class LinkedList {
*// head node of the linked list*
Node head;
*// class which represents each node in the linked list*
static class Node {
int val;
Node next;
*// constructor which assigns value to the node created*
Node(int k) {
val = k;
next = null;
}
}
public void printSList() {
Node n = head;
while (n != null) {
System.out.print(n.val + " ");
n = n.next;
}
}
*// Driver code*
public static void main(String[] args) {
*// creating an object of the LinkedList class*
LinkedList linked_list = new LinkedList();
*// assigning the value of each node in the linked list*
linked_list.head = new Node(30);
*// assigning data to the second node*
Node second = new Node(40);
*// assigning data to the third node*
Node third = new Node(50);
*// assigning data to the fourth node*
Node fourth = new Node(60);
*// creating a link to the head node and the second node of the linked list*
linked_list.head.next = second;
*// creating a link to the second and the third node*
second.next = third;
*// creating a link to the third and the fourth node*
third.next = fourth;
linked_list.printSList();
}
}

**Output:**

```
30 40 50 60
```

The singly linked list formed by assigning values to the nodes are:

**Applications of a Singly Linked List are as follows:**

- Singly-linked lists are used for the implementation of stacks and queues.
- Singly-linked lists are also used for preventing data collision in hash maps.

## Doubly Linked List

- Doubly linked lists are very similar to singly linked lists but have an extra pointer that points to the previous node.
- Every node in the doubly linked list has three parts i.e, data of the node, a pointer (link) to the next node which has the address of the next node, and the third part is another pointer (link) to the previous node which has the address of the previous node.
- The first node in the doubly linked list is called the
**head**node and the last node is called the**tail**node. The first node’s previous pointer points to the null value and the last node’s next pointer point to the null value. - A doubly linked list is a bi-directional linked list i.e, you can traverse either from head to tail or tail to head. Here pointer to the next node is generally called
**next**and the information to the previous node is called**prev**.

The representation of doubly linked lists is clearly shown in the below image:

**Representation of doubly linked list in C++, Python, and Java is as follows:**

**C++ representation:** of a doubly linked list.

*// class which represents each node in the doubly linked list*
#include <bits/stdc++.h>
using namespace std;
*// A linked list node*
class Node {
public:
int val;
Node* next;
Node* prev;
};
*// Given a reference to the head of a DLL and an int to add the node*
*// function/ method which is used for adding elements to DLL at the end of the list*
void addAtEnd(Node** ref_head, int data) {
*// forms a new node with the given data*
Node* add_node = new Node();
Node* k = *ref_head;
add_node->val = data;
*// since this new node is the last so make the next of this pointing to null*
add_node->next = NULL;
*// If the Linked List is empty, then make the new node as head*
if (*ref_head == NULL){
add_node->prev = NULL;
*ref_head = add_node;
return;
}
*// else we need to traverse till the end of the linked list*
while (k->next != NULL)
k = k->next;
*// Change the next of the last node*
k->next = add_node;
*// Make the last node previous to the new node*
add_node->prev = k;
return;
}
*// function to print elements in the doubly linked list*
void printDList(Node* node) {
while (node != NULL) {
cout << node->val << " ";
node = node->next;
}
}
*// Driver program*
int main() {
*// Creating a doubly linked list*
Node* head = NULL;
*// adding all the nodes of the doubly linked list at the end of the list each time*
addAtEnd(&head, 10);
addAtEnd(&head, 20);
addAtEnd(&head, 30);
addAtEnd(&head, 40);
printDList(head);
return 0;
}

**Output:**

```
10 20 30 40
```

**Python representation:** of a doubly linked list.

*# class which represents each node in the doubly linked list*
class Node:
*# Constructor to create a new node*
def __init__(self, val):
self.val = val
self.next = None
self.prev = None
*# Class to create a Doubly Linked List*
class DoublyLinkedList:
*# Constructor for empty Doubly Linked List*
def __init__(self):
self.head = None
*# method which prints the elements in the Doubly Linked List*
def printDList(self):
temp = self.head
*# traverse till the end of the list*
while (temp):
print (temp.val, end=" ")
temp = temp.next
*# function/ method which is used for adding elements to DLL at the end of the list*
def addAtEnd(self, data):
*# forms a new node with the given data*
add_node = Node(data)
*# since this new node is the last so make the next of this pointing to null*
*# If the Linked List is empty, then make the new node as head*
if self.head is None:
self.head = add_node
return
*# else we need to traverse till the end of the linked list*
k = self.head
while k.next:
k = k.next
*# 6. Change the next or last node*
k.next = add_node
*# 7. Make the last node as previous of the new node*
add_node.prev = k
return
*# Driver code*
*# creating a doubly linked list*
doubly_llist = DoublyLinkedList()
*# adding all the nodes of the doubly linked list at the end of the list each time*
doubly_llist.addAtEnd(10)
doubly_llist.addAtEnd(20)
doubly_llist.addAtEnd(30)
doubly_llist.addAtEnd(40)
doubly_llist.printDList()

**Output:**

```
10 20 30 40
```

**Java representation:** of a doubly linked list.

*// main class which represents a doubly linked list*
public class DoublyLinkedList {
*// head of the doubly linked list*
Node head;
*// class which represents each node in the doubly linked list*
class Node {
int val;
*// pointer to the previous node*
Node prev;
*// pointer to the next node*
Node next;
*// Constructor used to create a node with data initialized to the given value and pointers initialized to null*
Node(int data) {
val = data;
}
}
*// Given a reference to the head of a DLL and an int to add the node*
*// function/ method which is used for adding elements to DLL at the end of the list*
void addAtEnd(int data) {
*// forms a new node with the given data*
Node add_node = new Node(data);
System.out.print(data + " ");
Node k = head;
*// since this new node is the last so make the next of this pointing to null*
add_node.next = null;
*// If the Linked List is empty, then make the new node as head*
if (head == null) {
add_node.prev = null;
head = add_node;
return;
}
*// else we need to traverse till the end of the linked list*
while (k.next != null) k = k.next;
*// Change the next of the last node*
k.next = add_node;
*// Make the last node as previous of the new node*
add_node.prev = k;
}
*// Driver program*
public static void main(String[] args) {
*// Creating a doubly linked list*
DoublyLinkedList doubly_ll = new DoublyLinkedList();
*// adding all the nodes of the doubly linked list at the end of the list each time*
doubly_ll.addAtEnd(10);
doubly_ll.addAtEnd(20);
doubly_ll.addAtEnd(30);
doubly_ll.addAtEnd(40);
}
}

**Output:**

```
10 20 30 40
```

An example of a doubly linked list having four nodes is shown in the below figure:

**Applications of the Doubly Linked Lists:**

- Doubly linked lists are used by the internet browser to implement backward and forward navigation of visited web pages using a backward and forward arrow button.
- The doubly linked list is also used by various applications where it involves undo and redo functionalities.

## Circular Linked List

The next type of linked list in data structures is a circular linked list. When the last node of a singly linked list points to its first node, we get a circular linked list. Here pointer to the next node is generally called **next**. The first node in the circular linked list is called the head node.

A circular linked list can be traversed in only one direction so it is a unidirectional linked list.

The below image clearly explains the representation of the circular linked list:

**Representation of circular linked list in C++, Python, and Java is as follows:**

**C++ representation:** of a circular linked list.

```
#include <bits/stdc++.h>
#include <bits/stdc++.h>
using namespace std;
```*// Main class which represents each node in the circular linked list*
*// structure of the node*
struct Node
{
int val;
struct Node *next;
};
*// function which adds a node to the empty list*
struct Node *addToempty(struct Node *last, int value)
{
*// This function is only for empty list*
if (last != NULL)
return last;
*// Creating a node dynamically.*
struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
*// Assigning the data.*
temp->val = value;
last = temp;
*// Creating the link.*
last->next = last;
return last;
}
*// Function which adds nodes to the circular linked list*
struct Node *addAtEnd(struct Node *last, int value)
{
*// if the list is empty then add the node to the empty list*
if (last == NULL)
return addToempty(last, value);
*// manipulating the links to add the node at the end of the linked list*
struct Node *temp = (struct Node *)malloc(sizeof(struct Node));
temp->val = value;
temp->next = last->next;
last->next = temp;
last = temp;
return last;
}
void printCircularList(Node *head)
{
if (head == NULL)
{
return;
}
Node *ptr = head;
do
{
cout << ptr->val << " ";
ptr = ptr->next;
} while (head != ptr);
}
*// Driven Code*
int main()
{
*// initializing the last pointer of the circular linked list*
struct Node *last = NULL;
*// adding nodes to the circular linked list*
last = addAtEnd(last, 10);
last = addAtEnd(last, 20);
last = addAtEnd(last, 30);
last = addAtEnd(last, 40);
struct Node *head = last->next;
*// print the elements of the linked list*
printCircularList(head);
return 0;
}

**Output:**

```
10 20 30 40
```

**Python representation:** of circular linked list.

*# class which represents each node in the circular linked list*
class Node:
*# constructor which is invoked when a new object is created*
def __init__(self, val):
self.val = val
self.next = None
*# class which is used for the formation of a circular linked list*
class CircularLinkedList:
*# constructor which is invoked when a new object is created*
*# and is creating a link for the last node where it points to the head of the linked list*
def __init__(self):
self.last = None
*# when no node is present in the circular linked list, create a new node*
def addToempty(self, data):
if (self.last != None):
return self.last
*# Creating the new node with the given data temp*
temp = Node(data)
self.last = temp
*# Creating the link*
self.last.next = self.last
return self.last
*# function/ method which is used for adding elements to CL at the end of the list*
def addAtEnd(self, data):
*# if no node is present in the linked list add it to the empty list*
if (self.last == None):
return self.addToempty(data)
*# Assigning the data to the formed node*
temp = Node(data)
*# Adjusting the links.*
temp.next = self.last.next
self.last.next = temp
self.last = temp
return self.last
def print_circular_list(self, node):
if head == None:
return
node = head
while True:
print(node.val, end=" ")
node = node.next
if node == head:
return
*# creating a doubly linked list*
circular_list = CircularLinkedList()
*# adding all the nodes of the doubly linked list at the end of the list each time*
circular_list.addAtEnd(10)
circular_list.addAtEnd(20)
circular_list.addAtEnd(30)
last = circular_list.addAtEnd(40)
circular_list.print_circular_list(last.next)

**Output:**

```
10 20 30 40
```

**Java representation:** of a circular linked list is created using classes and creating its objects by passing the node’s data value.

```
class Main {
```*// Class for the node*
static class Node {
int val;
Node next;
}
*// function which is used to add a node to the empty list*
static Node addToempty(Node last, int data) {
*// This function is only for empty list*
if (last != null) return last;
*// Creating a node dynamically.*
Node temp = new Node();
*// Assigning the data.*
temp.val = data;
last = temp;
*// Creating the link.*
last.next = last;
return last;
}
*// Method which is used for adding an element at the end of the linked list*
static Node addAtend(Node last, int data) {
*// if the list is empty add the node to the empty list*
if (last == null) return addToempty(last, data);
*// manipulating the pointers to add the node at the end*
Node temp = new Node();
temp.val = data;
temp.next = last.next;
last.next = temp;
last = temp;
return last;
}
static void printCircularList(Node head) {
if (head == null) {
return;
}
Node ptr = head;
do {
System.out.print(ptr.val + " ");
ptr = ptr.next;
} while (head != ptr);
}
*// Driver Code*
public static void main(String[] args) {
*// providing the reference to the last node*
Node last = null;
*// Adding elements to the circular linked list*
last = addAtend(last, 10);
last = addAtend(last, 20);
last = addAtend(last, 30);
last = addAtend(last, 40);
printCircularList(last.next);
}
}

**Output:**

```
10 20 30 40
```

In the implementation of the circular linked list, we need to make the last node’s next pointer point to the first node i.e, the head node.

An example of a circular linked list having four nodes is shown in the below figure:

**Applications of Circular Linked List:**

- For example, consider you are working on a windows manager that allows users to cycle through windows by pressing Cmd+Tab, this is an application of circular linked list.
- Circular linked lists can also be used to implement queues by using only one pointer to the last inserted node, whereas in the singly linked list, we use two pointers.

## Doubly Circular Linked List

The last type of linked list in data structures is a doubly circular linked list. As the name suggests it is the combination of both a circular linked list and a doubly linked list. Same as in the doubly linked list each node has three parts. One part is for data, the second part is for storing the address of the next node and the last part is for storing the address of the previous node. The first node in the linked list is called the **head node**.

Another specialty of a doubly circular linked list is that same as in a circular linked list, the doubly circular linked list’s last node points to the head of the linked list. Here pointer to the next node is generally called **next** and the information to the previous node is called **prev**. A doubly circular linked list can be traversed in both directions and is hence called a bi-directional linked list.

The below image clearly explains the representation of a doubly circular linked list:

**Representation of a doubly circular linked list in C++, Python, and Java are as follows:**

**C++ representation:** of a doubly circular linked list is created using classes and creating its objects by passing the node’s data value.

*// C++ implementation of doubly circular linked list*
#include <bits/stdc++.h>
using namespace std;
*// Structure of a Node*
struct Node {
int val;
struct Node *next;
struct Node *prev;
};
*// print the elements of the linked list*
void printCircularList(Node* node){
Node* temp = node;
if (node != NULL) {
*// Print nodes till we reach the first node again*
do {
cout << node->val << " ";
node = node->next;
} while (temp != node);
}
}
*// Function to insert at the end*
void addAtEnd(struct Node** start, int data) {
*// If the list is empty create a single node*
if (*start == NULL) {
struct Node* add_node = new Node;
add_node->val = data;
add_node->next = add_node->prev = add_node;
*start = add_node;
return;
}
*// If the list is not empty, Find the last node*
Node *last_node = (*start)->prev;
*// Create Node dynamically*
struct Node* add_node = new Node;
add_node->val = data;
*// Start is going to be next of new_node*
add_node->next = *start;
*// Make a new node previous to start*
(*start)->prev = add_node;
*// Make the last previous of the new node*
add_node->prev = last_node;
*// Make new node next to old last*
last_node->next = add_node;
}
*// Driver Code*
int main() {
*// Creating a doubly linked list*
struct Node* head = NULL;
*// adding all the nodes of the doubly linked list at the end of the list each time*
addAtEnd(&head, 10);
addAtEnd(&head, 20);
addAtEnd(&head, 30);
addAtEnd(&head, 40);
printCircularList(head);
return 0;
}

**Output:**

```
10 20 30 40
```

**Python representation:** of a doubly circular linked list is created using classes and creating its objects by passing the node’s data value.

*# class which represents each node in the doubly circular linked list*
class Node:
*# constructor which initializes the node with given data*
def __init__(self, next=None, prev=None, val=None):
self.val = val
*# pointer to next node*
self.next = next
*# pointer to previous node*
self.prev = prev
*# Function to create a Doubly Circular Linked List*
def addAtEnd(data) :
global start
*# If the list is empty, create a*
*# single node circular and doubly list*
if (start == None) :
add_node = Node(0)
add_node.val = data
add_node.next = add_node.prev = add_node
start = add_node
return
*# Find last node*
last_node = (start).prev
*# Create Node dynamically by passing the data*
add_node = Node(0)
add_node.val = data
*# Start is going to be next to new_node*
add_node.next = start
*# Make a new node previous to start*
(start).prev = add_node
*# Make the last previous new node*
add_node.prev = last_node
*# Make a new node next to the old last*
last_node.next = add_node
def printCircularList():
if start == None:
return
temp = start
while True:
print(temp.val, end=" ")
temp = temp.next
if temp == start:
return
*# Driver code*
if __name__ == '__main__':
global start
*# Start with an empty list*
start = None
*# adding all the nodes of the doubly circular linked list at the end of the list each time*
addAtEnd(10)
addAtEnd(20)
addAtEnd(30)
addAtEnd(40)
printCircularList()

**Output:**

```
10 20 30 40
```

**Java representation:** of a doubly circular linked list is created using classes and creating its objects by passing the node’s data value.

```
import java.util.*;
class Solution {
static Node start;
```*// Structure of a Node*
static class Node {
int val;
Node next;
Node prev;
}
*// Main function which creates a node at the end of the doubly circular linked list*
static void addAtEnd(int data) {
*// If the list is empty create a new node*
if (start == null) {
Node add_node = new Node();
add_node.val = data;
add_node.next = add_node.prev = add_node;
start = add_node;
return;
}
*// If the list is not empty*
*// Find the last node*
Node last_node = (start).prev;
*// Create Node dynamically*
Node add_node = new Node();
add_node.val = data;
*// Start is going to be next to new_node*
add_node.next = start;
*// Make a new node previous to start*
(start).prev = add_node;
*// Make the last previous of the new node*
add_node.prev = last_node;
*// Make a new node next to the old last*
last_node.next = add_node;
}
static void printCircularList() {
Node temp = start;
if (temp != null) {
*// Print nodes till we reach the first node again*
do {
System.out.print(temp.val + " ");
temp = temp.next;
} while (temp != start);
}
}
*// Driver Code*
public static void main(String[] args) {
*// start with an empty list*
Node start = null;
*// adding all the nodes of the doubly circular linked list at the end of the list each time*
addAtEnd(10);
addAtEnd(20);
addAtEnd(30);
addAtEnd(40);
printCircularList();
}
}

**Output:**

```
10 20 30 40
```

In the implementation of a doubly circular linked list, we need to make the last node’s next pointer point to the first node’s prev pointer.

An example of a doubly circular linked list having four nodes is shown in the below figure:

**Applications of Doubly Circular Linked List:**

- Popular real-life example of a doubly linked list in music players, apps like Spotify, and Gaana uses doubly linked lists to keep track of previous and next songs in the music album.
- Another application of a doubly circular linked list is managing the shopping cart on online websites.

## Conclusion

- This article explained the types of linked lists in the data structure.
- Four types of data structures are present which are:
- Singly-linked list
- Doubly linked list
- Circular linked list
- Doubly circular linked list

- For a better understanding of the linked list, visit this page Linked Lists.
- Some
**Basic operations**on linked lists and their respective time and space complexities are highlighted in the below table:

Operation | Time Complexity | Space Complexity |
---|---|---|

Insert an element in the linked list | $O(N)$ (worst case) | $O(1)$ |

Delete an element in the linked list | $O(N)$ (worst case) | $O(1)$ |

Search an element in the linked list | $O(N)$ (worst case) | $O(1)$ |

- Where
`N`

is the number of nodes in the given doubly linked list. Here the worst case is when the element to be inserted or deleted or searched is present at the end of the linked list, we need to traverse the complete linked list. - Out of all these types of linked lists, a singly linked list is considered to be more simple and easy to implement.
- Every type of linked list has its applications.

*Dive into the World of Efficient Coding – Enroll in Scaler Academy’s Data Structures Course Today and Learn from Industry Experts!*