How to do deep copy an object without using recursion and json methods

Question

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;
}

Answer 1

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:

1. Check if the input is an object (including arrays), if not, return it directly.

2. Initialize a stack with an entry containing the source (the input object) and a target (a new object or array of the same type).

3. Create a reference map to keep track of original objects and their corresponding copies.

4. While the stack is not empty:

   1. Pop an item from the stack, which includes a source object and its corresponding target copy.

   2. Iterate over all the keys in the source object:

      1. If the value associated with the key is an object (including arrays):

         1. Check if the object already has a copy in the reference map. If so, use the existing copy; otherwise, create a new copy and add it to the reference map.
         2. Assign the copy to the corresponding key in the target object.
         3. Push a new entry onto the stack with the source being the value object and the target being its copy.

      2. If the value is not an object, assign it directly to the corresponding key in the target object.

5. 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; }