Recursive linked list from array

Question

I am working through the examples in Eloquent Javascript and I cannot seem to generate a working solution to recursively go from an array to a linked list.

The first (iterative) approach seems to work. I am stumped by the recursion. A push in the right direction would be greatly appreciated. Here is the code I have written so far:

function arrayToList(arr) {
    var retObj = {};
    var current = retObj;
    for (var i = 0; i < arr.length; i++) {
        current.value = arr[i];
        if (arr[i + 1] === undefined) {
            current.rest = null;
        } else {
            current.rest = {};
        }
        current = current.rest;
    }
    return retObj;
}

function recArrayToList(arr, obj) {
    if (arr.length === 0) {
        return 'DONE!';
    }
    obj.value = arr[0];
    obj.rest = {};
    return recArrayToList(arr.slice(1), obj.rest);
}

What do you mean by "linked list"? A sample of input and expected results always helps — charlietfl
– charlietfl, Commented Nov 27, 2017 at 18:13
I don't think you want to return the string 'DONE!', have you tried returning obj? — IrkenInvader
– IrkenInvader, Commented Nov 27, 2017 at 18:14
@IrkenInvader: returning obj gives an empty object. @charleitfl: console.log(arrayToList([10, 20])); // → {value: 10, rest: {value: 20, rest: null}}(taken from Eloquent Javascript) — R.Long
– R.Long, Commented Nov 27, 2017 at 18:21

Nir Alfasi · Accepted Answer · 2017-11-27 18:54:02Z

2

In this example we're building the current item by setting its value to be the first item in the array and the rest we'll set to the result of the recursive call. The stop condition sets the rest to null (meaning - we're done:

    function recArrayToList(arr) {
        if (arr.length === 0) {
            return null; // last element
        }
        var obj = {};
        obj.value = arr[0];          
        obj.rest = recArrayToList(arr.slice(1)); // recursive call
        return obj;
    }

    // example
    console.log(recArrayToList([1,2,3]));

The code in the question was close, but there are two mistakes:

it didn't handle the stop condition properly
the recursive call didn't set obj.rest the way it should have

edited Nov 27, 2017 at 18:54

answered Nov 27, 2017 at 18:20

Nir Alfasi

53.6k11 gold badges93 silver badges138 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

R.Long Over a year ago

This answer was very helpful, thank you @alfasin. Preserved the original structure and helped me see my errors.

JJJ Over a year ago

Instead of returning null, it should return obj.rest = null

Nir Alfasi Over a year ago

@JosanIracheta how do you return an assignment ?

JJJ Over a year ago

@alfasin return obj.rest = null assigns the value to obj.rest and then returns from the function. That way the last rest will have the value of null

Nir Alfasi Over a year ago

@JosanIracheta you do understand that return obj.rest = null has the same affect as return null right ? the assignment has a return value of null so when you "return" an assignment you're practically returning a null which is assigned (again) to obj.rest in the line: obj.rest = arrayToList(array.slice(1))

|

samanime · Accepted Answer · 2017-11-27 18:35:30Z

0

Since it's a single-linked list (meaning it only goes one way), you'll also need to pass in the root as well. You could have this be a default parameter that you don't need to pass in the first time.

Similarly, you can also make obj an optional parameter which will self-initialize as well, making your initial call just recArrayToList(someArr).

function recArrayToList(arr, obj, root) {
        if (arr.length === 0) {
            obj.rest = null;
            return root;
        }
        
        if (!obj) {
          obj = {};
        }

        if (!root) {
          root = obj;
        }

        obj.value = arr[0];
        obj.rest = {};
        return recArrayToList(arr.slice(1), obj.rest, root);
    }
    
let current = recArrayToList([1,2,3,4,5]);

while(current.rest) {
  console.log(current.value);
  current = current.rest;
}

You can also crunch it down a bit with some more compact JS (some people don't like some of these conventions):

function recArrayToList(arr, obj, root) {
        if (arr.length === 0) {
            obj.rest = null;
            return root;
        }
        
        obj = obj || {};
        root = root || obj;
        Object.assign(obj, { value: arr.shift(), rest: {} });
        return recArrayToList(arr, obj.rest, root);
    }
    
let current = recArrayToList([1,2,3,4,5]);

while(current.rest) {
  console.log(current.value);
  current = current.rest;
}

edited Nov 27, 2017 at 18:35

answered Nov 27, 2017 at 18:17

samanime

26.8k17 gold badges99 silver badges155 bronze badges

6 Comments

Kraylog Over a year ago

If I'm not mistaken, the result of this function would always be an empty object - the last empty node.

Nir Alfasi Over a year ago

Did you try to run it ?

Kraylog Over a year ago

Only in my head. However, it makes sense that if what's returned is the result of recArrayToList, and the only return value is obj, and when that happens it's an empty object, then that's what you'll get.

samanime Over a year ago

Indeed it would. My mistake. Updated my answer with a functioning example. =p

Nir Alfasi Over a year ago

I took the liberty to improve it a bit :) That's a good solution but there is one slight change from the requirements: in the OP's iterative approach the last element has rest point to null while in this solution the last element's rest points to {}.

|

Dresha · Accepted Answer · 2017-11-27 18:36:40Z

0

Try this:

function recArrayToList(arr, current, retObj) {
  var obj = current;

   if(retObj){
      obj = retObj;
   }

   if (arr.length === 0) {
      return current;
   }

   obj.value = arr[0];
   obj.rest = {};

   return recArrayToList(arr.slice(1), current, obj.rest);

}

answered Nov 27, 2017 at 18:36

Dresha

961 silver badge5 bronze badges

Comments

Kraylog · Accepted Answer · 2017-11-27 18:42:48Z

0

This should work:

function recArrayToList(arr) {
  if(arr.length === 0){
    return null;
  }
  return {value: arr[0], rest: recArrayToList(arr.slice(1))}; 
}

console.log(recArrayToList([1, 2, 3]));

answered Nov 27, 2017 at 18:42

Kraylog

7,6131 gold badge28 silver badges37 bronze badges

Comments

trincot · Accepted Answer · 2017-11-27 18:45:22Z

The recursive version has some flaws. "Done!" is not really what you want as return value if you expect a linked list.

It is also nicer if you don't have to pass the result object as second argument, as the recursive call should really not have to know the object its value is going to be used in. You can do it without that.

It helps to think that the recursive call returns the rest value, and that you can inject that immediately in that property as you create the wrapper object as an object literal. And then you find that the code really reduces to just one return statement... which you can combine with the stop condition in a ternary operator:

function recArrayToList(arr) {
    return arr.length ? {
        value: arr[0],
        rest: recArrayToList(arr.slice(1))
    } : null;
}

const list = recArrayToList([1, 2, 3]);

console.log(list);

Collectives™ on Stack Overflow

Recursive linked list from array

5 Answers 5

8 Comments

6 Comments

Comments

Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

5 Answers 5

8 Comments

6 Comments

Comments

Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related