CODEWITHSUNDEEP
javascriptrecursionlinked-list
R.Long
R.Long

Reputation: 39

Recursive linked list from array

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

Upvotes: 1

Views: 436

Answers (5)

Nir Alfasi
Nir Alfasi

Reputation: 53535

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:

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

Upvotes: 2

trincot
trincot

Reputation: 350310

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

Upvotes: 0

Kraylog
Kraylog

Reputation: 7553

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]));

Upvotes: 0

Dresha
Dresha

Reputation: 96

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

}

Upvotes: 0

samanime
samanime

Reputation: 26557

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

Upvotes: 0

Related Questions