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 nodestruct node{ int data; struct node *next; struct node *prev;};// Utility function to create a node in memorystruct node* getNode(){ return ((struct node *)malloc(sizeof(struct node)));}// Function to display the listint 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 listvoid 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 Codeint 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 memorydef getNode(): return (Node(0))# Function to display the listdef 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 listdef 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 Codeif __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 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
… [Trackback]
[…] Info on that Topic: geeksforgeeks.org/convert-an-array-to-a-circular-doubly-linked-list/ […]
… [Trackback]
[…] Read More on to that Topic: geeksforgeeks.org/convert-an-array-to-a-circular-doubly-linked-list/ […]