Requisito previo : Lista doblemente enlazada , Lista circular enlazada , Lista circular doblemente enlazada
Dada una array de N elementos. La tarea es escribir un programa para convertir la array en una lista circular doblemente enlazada .
La idea es comenzar a recorrer la array y, para cada elemento de la array, crear un nuevo Node de lista y asignar los punteros anterior y siguiente de este Node en consecuencia.
- Cree un inicio de puntero para apuntar al inicio de la lista que inicialmente apuntará a NULL (Lista vacía).
- Para el primer elemento de la array, cree un nuevo Node y coloque los punteros anterior y siguiente de ese Node en el punto para comenzar a mantener la forma circular de la lista.
- Para el resto de los elementos de la array, inserte esos elementos al final de la lista circular doblemente vinculada creada.
A continuación se muestra la implementación de la idea anterior:
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>
Producción:
The list is: 1 2 3 4 5
Complejidad de tiempo: O (n), ya que estamos usando un bucle para atravesar n veces. Donde n es el número de Nodes en la lista enlazada.
Espacio auxiliar: O(1), ya que no estamos utilizando ningún espacio adicional.
Publicación traducida automáticamente
Artículo escrito por GeeksforGeeks-1 y traducido por Barcelona Geeks. The original can be accessed here. Licence: CCBY-SA