Home > Software engineering >  How to represent a nested array as one-dimensional array?
How to represent a nested array as one-dimensional array?

Time:02-17

How to represent (serialise) an arbitrarily nested array, as a one-dimensional array of values (and meta-data) so that the original nested array and it's structure can be recreated from the serialised one-dimensional array?

I'm looking for a space efficient algorithms for this problem.

For example:

[
  [
    [1, 2, 3, 4]
  ], 
  [
    [5, 6, 7, 8], 
    [9, 10]
  ]
]

Should be serialised / deserialised to / from something like this

[/* elements of meta data* /, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

CodePudding user response:

You could represent a nested array with a sequence that first contains the length of that array (also providing the information that the following content is a sub-array) and then the elements themselves.

If you only have positive numbers as your values, but can store negative numbers, you could use negative numbers as the indicator for sub-arrays (if not, you can of course just use an offset O, which is the highest number you want to store, and treat all numbers greater then O as indicator for a new sub-array). The serialized version of your example would then look like this:

[-2, -1, -4, 1, 2, 3, 4, -2, -4, 5, 6, 7, 8, -2, 9, 10]

To understand better how it's working, here is an indented version of the same serialized array:

[-2,
  -1,
    -4
      1, 2, 3, 4
  -2
    -4
      5, 6, 7, 8
    -2
      9, 10
]

This structure can be serialized and deserialized in linear time using a recursive algorithm.

  • Related