List data structures in JavaScript

Question

In an exercise in the book Eloquent JavaScript I need to create a list data structure (as below) based on the array [1, 2, 3].

The tutorial JavaScript Data Structures - The Linked List shows how to do this, but I don't really understand the intention to create this.start and this.end variables inside the tutorial.

var list = {
  value: 1,
   rest: {
     value: 2,
      rest: {
        value: 3,
        rest: null
      }
   }
};

I tried to solve this via the code below.

function arrayToList(array){
  var list = { value:null, rest:null};
  for(i=0; i<array.length-1; i++)
     list.value = array[i];
     list.rest = list;
  return list;
}

This code gives me an infinite loop of array[0]. What's wrong with my code?

list.value = array[i]; also use index not i as your variable name then it is clearer. — Hogan
– Hogan, Commented Jun 15, 2014 at 15:21

Bergi · Accepted Answer · 2014-06-15 15:25:11Z

3

This tutorial shows how to do this but I don't really understand the intention to create this.start and this.end variables inside the tutorial.

The tutorial uses a List wrapper around that recursive structure with some helper methods. It says: "It is possible to avoid having to record the end of the list by performing a traverse of the entire list each time you need to access the end - but in most cases storing a reference to the end of the list is more economical."

This code gives me an infinite loop of array[0].

Not really, but it creates a circular reference with the line list.rest = list;. Probably the code that is outputting your list chokes on that.

What's wrong is with my code?

You need to create multiple objects, define the object literal inside the loop body instead of assigning to the very same object over and over! Also, you should access array[i] inside the loop instead of array[0] only:

function arrayToList(array){
    var list = null;
    for (var i=array.length-1; i>=0; i--)
        list = {value: array[i], rest:list};
    return list;
}

answered Jun 15, 2014 at 15:25

Bergi

671k162 gold badges1k silver badges1.5k bronze badges

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

2 Comments

Yang Wei Over a year ago

I understand how this code works. But how did you think to loop the array backward instead of forward. Can a forward loop works in this case?

Bergi Over a year ago

A forward loop could work, but would need that queer end "pointer" (a variable, in this case). Most eays thing would be to shift() the first element from the array, and build the rest with a recursive call from the tail of the array.

georg · Accepted Answer · 2014-06-15 15:33:10Z

3

This particular data structure is more commonly called cons. Recursion is the most natural (not necessarily the most efficient) way to work with conses. First, let's define some helper functions (using LISP notation rather than "value/rest"):

function cons(car, cdr) { return [car, cdr] }
function car(a) { return a[0] }
function cdr(a) { return a[1] }

Now, to build a cons from an array, use the following recursive statement:

cons-from-array = cons [ first element, cons-from-array [ the rest ] ]

In Javascript:

function arrayToList(array) {
    if(!array.length)
        return null;
    return cons(array[0], arrayToList(array.slice(1)));
}

And the reverse function is similarly trivial:

function listToArray(list) {
    if(!list)
        return [];
    return [car(list)].concat(listToArray(cdr(list)));
}

answered Jun 15, 2014 at 15:33

georg

216k57 gold badges324 silver badges401 bronze badges

1 Comment

Raydot Over a year ago

Crazy, but interesting. Makes a lot of sense.

holmberd · Accepted Answer · 2016-07-09 15:09:43Z

1

function arrayToList (arr) {
    var list = null;
    for (var i = arr.length - 1; i >= 0; i--) {
        list = {
            value: arr[i],
            rest: list
        };
    }
    return list;
}

function prepend (elem, list) {
    return {
        value: elem,
        rest: list
    };
}

function listToArray (list) {
    var arr = [];
    for (var node = list; node; node = node.rest) {
        arr.push(node.value);
    }
    return arr;
}

function nth(list, num) {
  if (!list) {
    return undefined;
    } else if (num === 0) {
        return list.value;
    } else {
        return nth(list.rest, num - 1);
    }
}

answered Jul 9, 2016 at 15:09

holmberd

2,65231 silver badges33 bronze badges

Collectives™ on Stack Overflow

List data structures in JavaScript

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Linked

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

2 Comments

1 Comment

Comments

Your Answer

Sign up or log in

Post as a guest

Linked

Related