What are the Types of Linked Lists in Data Structure?

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:

1. Singly linked list
2. Doubly linked list
3. Circular linked list
4. 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:

• 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!