Javascript array to linked list, and understanding memory

Question

I have the following code to convert an array to a linked list:

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

This code was given to me so I'm trying to understand it. I get the basic intuition/gist of it (I've worked with linked lists, took a data structures class in Java already, understand basics of pointers in C), etc.

However, something's not clicking and I want to make sure I can see what's going on. So let's consider we create a variable, list, referring to memory space whose value is declared to be null. Let's say this "memory address" of this is 0001:

0001: [null] list

So what happens after the first iteration of our loop? This is my interpretation. list now refers to a new chunk of space. That is, by re-defining list in the line:

list = {value: array[i], rest: list};

we created a "new" object that occupies new space. So now we might have:

0001: [null]
0002: [array[i]] list.value
0003: [null] list.rest

(I'm not quite sure where exactly list is "pointing" to now, assuming 0002, though conceptually I guess that's kind of moot in Javascript)

Is this understanding correct? I'm used to thinking of data structures a la Java, where an object like list has already-defined blocks of space every time an instance is created. I've worked with Python but have not built linked lists with it before. From this I assume a language like Javascript is fluid in that you can just have a variable be null, then have it refer to a hash, then when you set it to be another hash it creates a "new" hash, etc.

Thanks!

Paul S. · Accepted Answer · 2014-09-20 01:40:22Z

1

First off, there is no native data structure in JavaScript which is a linked list, we have Objects and we have Arrays (which confusingly are special cases of Objects).

The code you've shown us here makes Objects by using object literals.

This seems to be more a question about using the same identifier on both sides of an =

The variable on the RHS of an = will point to the thing before it changes on the LHS

// say we have
var foo = {};

// Then
foo = {"fizz": foo};

is equivalent to having

var foo = {};

var t = foo;
foo = {"fizz": t}; // `foo` becomes a new object in a different memory location
// that points to `t`s target, meaning that `t` is referencable through `foo` and so
// won't be GC'd if the identifier `t` is cleaned up from namespace

You might find this be counter-intuitive based on the usual left-to-right order of execution, but if you think about it - you can't "set" until you know what to set, so until the RHS has finished you can't update the identifier from the LHS

So if you loop this, you might end up with a structure like

foo;           // Object @ e.g. 0x30
foo.fizz;      // Object @ e.g. 0x20
foo.fizz.fizz; // Object @ e.g. 0x10
foo.fizz.fizz.fizz; // undefined

Where each Object has it's own hash map which points back to the previous one (when looking up fizz) until you run out of Objects, and none of the memory gets GCd because each one is still reachable. How an environment actually implements this isn't specified in the spec, so it isn't a requirement that the memory location of an Object never moves, but it's location in memory is not something you are able to see or interact with (it's all done behind the scenes). Therefore, for all in-environment purposes, you can think of the memory locations as static.

edited Sep 20, 2014 at 1:40

answered Sep 20, 2014 at 1:17

Paul S.

66.6k9 gold badges129 silver badges143 bronze badges

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

2 Comments

Derek 朕會功夫 Over a year ago

I think the OP is discussing how a linked list is stored in memory in JavaScript, not how objects are set in this abstracted layer.

PM 77-1 Over a year ago

Are you saying that OP's code actually produces a linked list?

Collectives™ on Stack Overflow

Javascript array to linked list, and understanding memory

1 Answer 1

2 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

2 Comments

Your Answer

Sign up or log in

Post as a guest

Related