Problem Statement: Given an array of integers convert it to a doubly linked list.
Examples
Example 1:
Input Format: arr = [1, 2, 4, 3]
Result: DLL: 1 <-> 2 <-> 4 <->3
Example 2:
Input Format: Arr[2] = {7, 5}
Result: DLL: 7 <-> 5
Solution
Disclaimer: Don’t jump directly to the solution, try it out yourself first.
Intuition:
To convert an array to a doubly linked list, we can start by creating a new head node for the list. We can then iterate over the array, creating a new node for each element in the array.
As we create each new node, we set its next pointer to point to the next node in the list, and its back pointer to point to the previous node in the list. We can return the head of the doubly linked list as the answer.
Approach:
Initialize the first element of the array as the head of the DLL and point the prev and back pointers to NULL.
Iterate through the entire array, starting from index i = 1 to n-1.
During each iteration, create a new node with the value at the index from the array and set its back pointer to the previously created node.
Update the next pointer of the previous node to point to the newly created node.
Update the `prev` pointer to the newly created node `temp`, as it will become the previous node for the next iteration.
Loop through the entire array and return the head.
Code:
C++ Code
#include <iostream>
#include <bits/stdc++.h>
using namespace std;
// Define a Node class for doubly linked list
class Node {
public:
int data; // Data stored in the node
Node* next; // Pointer to the next node in the list (forward direction)
Node* back; // Pointer to the previous node in the list (backward direction)
// Constructor for a Node with both data, a reference to the next node, and a reference to the previous node
Node(int data1, Node* next1, Node* back1) {
data = data1;
next = next1;
back = back1;
}
// Constructor for a Node with data, and no references to the next and previous nodes (end of the list)
Node(int data1) {
data = data1;
next = nullptr;
back = nullptr;
}
};
// Function to convert an array to a doubly linked list
Node* convertArr2DLL(vector<int> arr) {
// Create the head node with the first element of the array
Node* head = new Node(arr[0]);
// Initialize 'prev' to the head node
Node* prev = head;
for (int i = 1; i < arr.size(); i++) {
// Create a new node with data from the array and set its 'back' pointer to the previous node
Node* temp = new Node(arr[i], nullptr, prev);
// Update the 'next' pointer of the previous node to point to the new node
prev->next = temp;
// Move 'prev' to the newly created node for the next iteration
prev = temp;
}
// Return the head of the doubly linked list
return head;
}
// Function to print the elements of the doubly linked list
void print(Node* head) {
while (head != nullptr) {
// Print the data in the current node
cout << head->data << " ";
// Move to the next node
head = head->next;
}
}
int main() {
vector<int> arr = {12, 5, 8, 7};
Node* head = convertArr2DLL(arr); // Convert the array to a doubly linked list
print(head); // Print the doubly linked list
return 0;
}
Output:
12 5 8 7 4
Time Complexity: O(N) The code iterates through the entire ‘n’-length array once, creating a new node for each element, resulting in a linear time complexity.
Space Complexity: O(N) The space complexity depends on the memory used to store doubly linked list nodes. Each node, storing data and two pointers (‘next’ and ‘back’), requires constant space. Thus, space complexity is O(n) as it scales linearly with the array’s size.
Java Code
public class DLinkedList {
public static class Node {
public int data; // Data stored in the node
public Node next; // Reference to the next node in the list (forward direction)
public Node back; // Reference to the previous node in the list (backward direction)
// Constructor for a Node with both data, a reference to the next node, and a reference to the previous node
public Node(int data1, Node next1, Node back1) {
data = data1;
next = next1;
back = back1;
}
// Constructor for a Node with data, and no references to the next and previous nodes (end of the list)
public Node(int data1) {
data = data1;
next = null;
back = null;
}
}
// Function to convert an array to a doubly linked list
private static Node convertArr2DLL(int[] arr) {
Node head = new Node(arr[0]); // Create the head node with the first element of the array
Node prev = head; // Initialize 'prev' to the head node
for (int i = 1; i < arr.length; i++) {
// Create a new node with data from the array and set its 'back' pointer to the previous node
Node temp = new Node(arr[i], null, prev);
prev.next = temp; // Update the 'next' pointer of the previous node to point to the new node
prev = temp; // Move 'prev' to the newly created node for the next iteration
}
return head; // Return the head of the doubly linked list
}
// Function to print the elements of the doubly linked list
private static void print(Node head) {
while (head != null) {
System.out.print(head.data + " "); // Print the data in the current node
head = head.next; // Move to the next node
}
System.out.println();
}
public static void main(String[] args) {
int[] arr = {12, 5, 6, 8};
Node head = convertArr2DLL(arr); // Convert the array to a doubly linked list
print(head); // Print the doubly linked list
}
}
Output:
12 5 8 7 4
Time Complexity: O(N) The code iterates through the entire ‘n’-length array once, creating a new node for each element, resulting in a linear time complexity.
Space Complexity: O(N) The space complexity depends on the memory used to store doubly linked list nodes. Each node, storing data and two pointers (‘next’ and ‘back’), requires constant space. Thus, space complexity is O(n) as it scales linearly with the array’s size.
Python Code
class Node:
def __init__(self, data1, next1=None, back1=None):
# Constructor for a Node with both data, a reference to the next node, and a reference to the previous node
self.data = data1
self.next = next1
self.back = back1
# Function to convert an array to a doubly linked list
def convertArr2DLL(arr):
# Create the head node with the first element of the array
head = Node(arr[0])
# Initialize 'prev' to the head node
prev = head
for i in range(1, len(arr)):
# Create a new node with data from the array and set its 'back' pointer to the previous node
temp = Node(arr[i], None, prev)
# Update the 'next' pointer of the previous node to point to the new node
prev.next = temp
# Move 'prev' to the newly created node for the next iteration
prev = temp
# Return the head of the doubly linked list
return head
# Function to print the elements of the doubly linked list
def printDLL(head):
while head is not None:
# Print the data in the current node
print(head.data, end=" ")
# Move to the next node
head = head.next
print()
if __name__ == "__main__":
arr = [12, 5, 6, 8]
head = convertArr2DLL(arr) # Convert the array to a doubly linked list
printDLL(head) # Print the doubly linked list
Output:
12 5 8 7 4
Time Complexity: O(N) The code iterates through the entire ‘n’-length array once, creating a new node for each element, resulting in a linear time complexity.
Space Complexity: O(N) The space complexity depends on the memory used to store doubly linked list nodes. Each node, storing data and two pointers (‘next’ and ‘back’), requires constant space. Thus, space complexity is O(n) as it scales linearly with the array’s size.
JavaScript Code
// Define a Node class for doubly linked list
class Node {
constructor(data, next = null, back = null) {
// Constructor for a Node with both data, a reference to the next node, and a reference to the previous node
this.data = data;
this.next = next;
this.back = back;
}
}
// Function to convert an array to a doubly linked list
function convertArrToDLL(arr) {
// Create the head node with the first element of the array
let head = new Node(arr[0]);
// Initialize 'prev' to the head node
let prev = head;
for (let i = 1; i < arr.length; i++) {
// Create a new node with data from the array and set its 'back' pointer to the previous node
let temp = new Node(arr[i], null, prev);
prev.next = temp; // Update the 'next' pointer of the previous node to point to the new node
prev = temp; // Move 'prev' to the newly created node for the next iteration
}
return head; // Return the head of the doubly linked list
}
// Function to print the elements of the doubly linked list
function print(head) {
while (head !== null) {
// Print the data in the current node
console.log(head.data + " ");
// Move to the next node
head = head.next;
}
console.log();
}
const arr = [12, 5, 6, 8];
const head = convertArrToDLL(arr); // Convert the array to a doubly linked list
print(head); // Print the doubly linked list
Output:
12 5 8 7 4
Time Complexity: O(N) The code iterates through the entire ‘n’-length array once, creating a new node for each element, resulting in a linear time complexity.
Space Complexity: O(N) The space complexity depends on the memory used to store doubly linked list nodes. Each node, storing data and two pointers (‘next’ and ‘back’), requires constant space. Thus, space complexity is O(n) as it scales linearly with the array’s size.
In case you are learning DSA, you should definitely check out our free A2Z DSA Course with videos and blogs.
Special thanks to Gauri Tomar for contributing to this article on takeUforward. If you also wish to share your knowledge with the takeUforward fam, please check out this article
