How to implement deep copy without using recursion, JSON.parse \ JSON.stringify, structuredClone(). There can be any number of elements in an object.
const data1 = {
a: 10,
y: null,
k: [1, 2],
b: 3,
c: {
d: 4,
e: {
w: 50,
u: undefined,
s: {
f: {
v: 5,
},
},
},
},
};
const data2 = [
{
a: 10,
y: null,
k: [1, 2],
b: 3,
c: {
d: 4,
e: {
w: 50,
u: undefined,
s: {
f: {
v: 5,
},
},
},
},
};
];
In my example, I can't implement a deep copy, I just stop at the second loop. How can we avoid recursion and other ready-made solutions?
function deepCopy(dataType) {
const copy = {};
let data = dataType;
if (Array.isArray(data)) {
data = dataType[0];
}
for (const [key, value] of Object.entries(data)) {
if (typeof data[key] === "object") {
copy[key] = Array.isArray(data[key]) ? [] : value;
for (let deepKey in data[key]) {
copy[key][deepKey] = data[key][deepKey];
}
} else {
copy[key] = data[key];
}
}
return copy;
}
If you use a stack and and a reference lookup map, you can iterate through the structure without any recursion.
Here is a breakdown of the algorithm:
Check if the input is an object (including arrays), if not, return it directly.
Initialize a stack with an entry containing the source (the input object) and a target (a new object or array of the same type).
Create a reference map to keep track of original objects and their corresponding copies.
While the stack is not empty:
Pop an item from the stack, which includes a source object and its corresponding target copy.
Iterate over all the keys in the source object:
If the value associated with the key is an object (including arrays):
If the value is not an object, assign it directly to the corresponding key in the target object.
Return the copy of the input object from the reference map.
const data1 = {
a: 10,
y: null,
k: [1, 2],
b: 3,
c: {
d: 4,
e: {
w: 50,
u: undefined,
s: { f: { v: 5 } }
}
}
};
const data2 = deepCopy(data1);
// Objects are not the same reference
console.log(data1.c !== data2.c); // true
console.log(data1.c.e !== data2.c.e); // true
console.log(data1.c.e.s.f !== data2.c.e.s.f); // true
console.log(data2); // Print the copy
function deepCopy(dataType) {
// Helper functions
const isObject = (value) => typeof value === 'object' && value !== null;
const getEmptyCopy = (source) => Array.isArray(source) ? [] : {};
// Return the value directly if it's not an object (e.g., primitives)
if (!isObject(dataType)) { return dataType; }
// Stack for iterative deep copying and a map to handle cyclic references
const stack = [], refMap = new Map();
// Adds a reference of the source object to the map and pushes it onto the stack
const addReference = (source) => {
const copy = getEmptyCopy(source);
refMap.set(source, copy);
stack.push({ source, copy });
};
// Initialize the process with the input data
addReference(dataType);
// Iterate over the stack, copying properties from source
while (stack.length) {
const { source, copy } = stack.pop();
for (const key in source) {
const value = source[key];
if (isObject(value)) {
// Handle cyclic references and nested objects
if (!refMap.has(value)) {
addReference(value); // Create a new reference
}
copy[key] = refMap.get(value); // Grab the existing reference
} else {
copy[key] = value; // Copy primitive values directly
}
}
}
return refMap.get(dataType); // Grab the copy ref for the input
}
.as-console-wrapper { top: 0; max-height: 100% !important; }