Convert an Array to a Circular Doubly Linked List

0 0 6 minutes read

Prerequisite: Doubly Linked list, Circular Linked List, Circular Doubly Linked List
Given an array of N elements. The task is to write a program to convert the array into a circular doubly linked list.

The idea is to start traversing the array and for every array element create a new list node and assign the prev and next pointers of this node accordingly.

Create a pointer start to point to the starting of the list which will initially point to NULL(Empty list).
For the first element of the array, create a new node and put that node’s prev and next pointers to point to start maintaining the circular fashion of the list.
For the rest of the array elements, insert those elements to the end of the created circular doubly linked list.

Below is the implementation of the above idea:

C++

// CPP program to convert array to 
// circular doubly linked list
 
#include<bits/stdc++.h>
using namespace std;
 
// Doubly linked list node
struct node
{
    int data;
    struct node *next;
    struct node *prev;
};
 
// Utility function to create a node in memory
struct node* getNode()
{
    return ((struct node *)malloc(sizeof(struct node)));
}
 
// Function to display the list
int displayList(struct node *temp)
{
    struct node *t = temp;
    if(temp == NULL)
        return 0;
    else
    {   
        cout<<"The list is: ";
         
        while(temp->next != t)
        {
            cout<<temp->data<<" ";
            temp = temp->next;
        }
         
        cout<<temp->data;
         
        return 1;
    } 
}
 
// Function to convert array into list
void createList(int arr[], int n, struct node **start)
{
    // Declare newNode and temporary pointer
    struct node *newNode,*temp;
    int i;
     
    // Iterate the loop until array length
    for(i=0;i<n;i++)
    {
        // Create new node
        newNode = getNode();
         
        // Assign the array data
        newNode->data = arr[i];
         
        // If it is first element
        // Put that node prev and next as start
        // as it is circular
        if(i==0)
        {
            *start = newNode;
            newNode->prev = *start;
            newNode->next = *start;
        }
        else
        {   
            // Find the last node
            temp = (*start)->prev;
             
            // Add the last node to make them
            // in circular fashion
            temp->next = newNode;
            newNode->next = *start;
            newNode->prev = temp;
            temp = *start;
            temp->prev = newNode;
        }
    }
}
 
// Driver Code
int main()
{
    // Array to be converted
    int arr[] = {1,2,3,4,5};
    int n = sizeof(arr) / sizeof(arr[0]);
     
    // Start Pointer
    struct node *start = NULL;
     
    // Create the List
    createList(arr, n, &start);
     
    // Display the list
    displayList(start);
     
    return 0;
}

Java

// Java program to convert array to 
// circular doubly linked list 
class GFG
{
     
// Doubly linked list node 
static class node 
{ 
    int data; 
    node next; 
    node prev; 
}; 
 
// Utility function to create a node in memory 
static node getNode() 
{ 
    return new node(); 
} 
 
// Function to display the list 
static int displayList( node temp) 
{ 
    node t = temp; 
    if(temp == null) 
        return 0; 
    else
    { 
        System.out.print("The list is: "); 
         
        while(temp.next != t) 
        { 
            System.out.print(temp.data+" ");
            temp = temp.next; 
        } 
         
        System.out.print(temp.data); 
         
        return 1; 
    } 
} 
 
// Function to convert array into list 
static node createList(int arr[], int n, node start) 
{ 
    // Declare newNode and temporary pointer 
    node newNode,temp; 
    int i; 
     
    // Iterate the loop until array length 
    for(i = 0; i < n; i++) 
    { 
        // Create new node 
        newNode = getNode(); 
         
        // Assign the array data 
        newNode.data = arr[i]; 
         
        // If it is first element 
        // Put that node prev and next as start 
        // as it is circular 
        if(i == 0) 
        { 
            start = newNode; 
            newNode.prev = start; 
            newNode.next = start; 
        } 
        else
        { 
            // Find the last node 
            temp = (start).prev; 
             
            // Add the last node to make them 
            // in circular fashion 
            temp.next = newNode; 
            newNode.next = start; 
            newNode.prev = temp; 
            temp = start; 
            temp.prev = newNode; 
        } 
    } 
    return start;
} 
 
// Driver Code 
public static void main(String args[])
{ 
    // Array to be converted 
    int arr[] = {1,2,3,4,5}; 
    int n = arr.length; 
     
    // Start Pointer 
    node start = null; 
     
    // Create the List 
    start = createList(arr, n, start); 
     
    // Display the list 
    displayList(start); 
} 
}
 
// This code is contributed by Arnab Kundu

Python3

# Python3 program to convert array to 
# circular doubly linked list
 
# Node of the doubly linked list 
class Node: 
     
    def __init__(self, data): 
        self.data = data 
        self.prev = None
        self.next = None
 
# Utility function to create a node in memory
def getNode():
 
    return (Node(0))
 
# Function to display the list
def displayList(temp):
 
    t = temp
    if(temp == None):
        return 0
    else:
         
        print("The list is: ", end = " ")
         
        while(temp.next != t):
         
            print(temp.data, end = " ")
            temp = temp.next
         
        print(temp.data)
         
        return 1
     
# Function to convert array into list
def createList(arr, n, start):
 
    # Declare newNode and temporary pointer
    newNode = None
    temp = None
    i = 0
     
    # Iterate the loop until array length
    while(i < n):
     
        # Create new node
        newNode = getNode()
         
        # Assign the array data
        newNode.data = arr[i]
         
        # If it is first element
        # Put that node prev and next as start
        # as it is circular
        if(i == 0):
         
            start = newNode
            newNode.prev = start
            newNode.next = start
         
        else:
             
            # Find the last node
            temp = (start).prev
             
            # Add the last node to make them
            # in circular fashion
            temp.next = newNode
            newNode.next = start
            newNode.prev = temp
            temp = start
            temp.prev = newNode
        i = i + 1
    return start
 
# Driver Code
if __name__ == "__main__": 
 
    # Array to be converted
    arr = [1, 2, 3, 4, 5]
    n = len(arr)
     
    # Start Pointer
    start = None
     
    # Create the List
    start = createList(arr, n, start)
     
    # Display the list
    displayList(start)
     
# This code is contributed by Arnab Kundu

C#

// C# program to convert array to 
// circular doubly linked list 
using System;
 
class GFG 
{ 
     
// Doubly linked list node 
public class node 
{ 
    public int data; 
    public node next; 
    public node prev; 
}; 
 
// Utility function to create a node in memory 
static node getNode() 
{ 
    return new node(); 
} 
 
// Function to display the list 
static int displayList( node temp) 
{ 
    node t = temp; 
    if(temp == null) 
        return 0; 
    else
    { 
        Console.Write("The list is: "); 
         
        while(temp.next != t) 
        { 
            Console.Write(temp.data + " "); 
            temp = temp.next; 
        } 
         
        Console.Write(temp.data); 
         
        return 1; 
    } 
} 
 
// Function to convert array into list 
static node createList(int []arr, 
                        int n, node start) 
{ 
    // Declare newNode and temporary pointer 
    node newNode,temp; 
    int i; 
     
    // Iterate the loop until array length 
    for(i = 0; i < n; i++) 
    { 
        // Create new node 
        newNode = getNode(); 
         
        // Assign the array data 
        newNode.data = arr[i]; 
         
        // If it is first element 
        // Put that node prev and next as start 
        // as it is circular 
        if(i == 0) 
        { 
            start = newNode; 
            newNode.prev = start; 
            newNode.next = start; 
        } 
        else
        { 
            // Find the last node 
            temp = (start).prev; 
             
            // Add the last node to make them 
            // in circular fashion 
            temp.next = newNode; 
            newNode.next = start; 
            newNode.prev = temp; 
            temp = start; 
            temp.prev = newNode; 
        } 
    } 
    return start; 
} 
 
// Driver Code 
public static void Main(String []args) 
{ 
    // Array to be converted 
    int []arr = {1,2,3,4,5}; 
    int n = arr.Length; 
     
    // Start Pointer 
    node start = null; 
     
    // Create the List 
    start = createList(arr, n, start); 
     
    // Display the list 
    displayList(start); 
} 
} 
 
// This code contributed by Rajput-Ji

Javascript

<script>
 
// JavaScript program to convert array to 
// circular doubly linked list 
 
// Doubly linked list node 
class node 
{
    constructor()
    {
        this.data=0;
        this.next=this.prev=null;
    }
}
 
// Utility function to create a node in memory 
function getNode() 
{
    return new node(); 
}
 
// Function to display the list 
function displayList(temp)
{
    let t = temp; 
    if(temp == null) 
        return 0; 
    else
    { 
        document.write("The list is: "); 
           
        while(temp.next != t) 
        { 
            document.write(temp.data+" ");
            temp = temp.next; 
        } 
           
        document.write(temp.data); 
           
        return 1; 
    } 
}
 
// Function to convert array into list 
function createList(arr,n,start)
{
    // Declare newNode and temporary pointer 
    let newNode,temp; 
    let i; 
       
    // Iterate the loop until array length 
    for(i = 0; i < n; i++) 
    { 
        // Create new node 
        newNode = getNode(); 
           
        // Assign the array data 
        newNode.data = arr[i]; 
           
        // If it is first element 
        // Put that node prev and next as start 
        // as it is circular 
        if(i == 0) 
        { 
            start = newNode; 
            newNode.prev = start; 
            newNode.next = start; 
        } 
        else
        { 
            // Find the last node 
            temp = (start).prev; 
               
            // Add the last node to make them 
            // in circular fashion 
            temp.next = newNode; 
            newNode.next = start; 
            newNode.prev = temp; 
            temp = start; 
            temp.prev = newNode; 
        } 
    } 
    return start;
}
 
// Driver Code 
let arr=[1,2,3,4,5];
let n = arr.length; 
// Start Pointer 
let start = null; 
 
// Create the List 
start = createList(arr, n, start); 
 
// Display the list 
displayList(start); 
 
 
// This code is contributed by avanitrachhadiya2155
 
</script>

Output:

The list is: 1 2 3 4 5

Time Complexity: O(n), as we are using a loop to traverse n times. Where n is the number of nodes in the linked list.

Auxiliary Space: O(1), as we are not using any extra space.

Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 zambiatek!