Object.create(null)

JavaScript
1

I am at the start of a course on Data Structures in JS, with the first section being on linked lists.

It is typical to start with a node class e.g.

class Node {
  constructor (data) {
    this.data = data
    this.next = null
  }
}

I was thinking alternatively I could use Object.create(null). Along the lines of…

const Node = function (data) {
  return Object.create(null, {
    data: {
      writable: true,
      value: data
    },
    next: {
      writable: true,
      value: null
    }
  })
}

class LinkedList {
  constructor () {
    this.head = null
    this.tail = null
  }

  insertBefore (data) {
    const node = Node(data)
    node.next = this.head
    if (!this.head) this.tail = node
    this.head = node
  }
}

I would prefer to be using ‘new’ on a class to make a node instance, but it does seem cleaner to me. Is it a bad idea though?

Testing some outputs

const linkedList = new LinkedList()

linkedList.insertBefore('A')
linkedList.insertBefore('B')

console.dir(linkedList)

v LinkedList
  v head:
      data: "B"
    v next:
        data: "A"
        next: null
  v tail: 
      data: "A"
      next: null
> __proto__: Object

If we need to use an object prototype method

const has = Object.prototype.hasOwnProperty
console.log(has.call(linkedList.head, 'data')) // true

It was just a thought, and may well be ill advised.

There doesn’t appear to be a way using classes (syntactic sugar, just to get that in) to replicate Object.create(null).

Any feedback appreciated

Thanks

2

I know that you’re wanting to prefer to use the new operator, but that has been a bad idea. The new keyword was to make Java programmers more comfortable with JavaScript, but didn’t work well because people wouldn’t know of they needed to use new or not, and if they used it when they shouldn’t or didn’t when they should, it broke things in strange and interesting ways.

Some articles of interest might be:

Object.create(), as you are using it, is a better way instead.

3

Instead of returning the following object.create:

  return Object.create(null, {
    data: {
      writable: true,
      value: data
    },
    next: {
      writable: true,
      value: null
    }
  })

Is there any reason why that can’t just be an object instead?

return {
    "data": data,
    "next": null
};

Or even just:

return {
    data,
    "next": null
};

or even just the data?

return {
    data
};
4

In which case, why is the Node function required any more?

Can’t we just keep it simple, and create the object instead?

const node = {data};

If so, I it makes sense to telegraph the node aspect of things, by including the next property too.

const node = {
    data
    "next": null
};
1 Like
5

I’d just like to note that both those articles are from pre-ES2015 when the actual class construct was introduced, which solves the issues of the cumbersome “manual” constructor / prototype definition and related confusion. Factories still allow for more fine-grained control on a lower level (such as enumerability), but most of the time the use of classes is just fine IMHO.

2 Likes
6

Edit: Sorry for the lengthy response

Thanks for the feedback Paul,

Prefer was probably the wrong word. It was more for consistency. New is used on the linkedlist class, and it seemed a bit off then having a factory function for the node class.

My idea, was to keep the node objects as separate entities without proto links to Object.prototype. For one it made the console.log output easier to decipher without the addition of proto links in the mix. It was just an idea:)

I have looked at numerous tutorials on linked lists, with all of them having different implementations. For instance some use a tail node, some rely on loops to find the last node. Some find by value, some by index. One thing that does seem to be consistent is keeping the node class separate to the linked list class. I’m guessing this is by design? Not as tightly coupled perhaps? I don’t know.

I did change things around a bit, following the course’s implementation, in that the node function now takes two other arguments, previous and next, which gives it a bit more of a reason to be a reusable function.

Anyway if of any interest, this is where I left it yesterday. I opted for using a mock index. It still needs a remove method and could have a length property, but I think I am getting the gist of linked list.

The generator and yield method, which gives you the facility of using a for of loop was taken from here and is something I want to read up on.

Computer science in JavaScript: Linked list

I will look at those articles, thanks again.

const CreateNode = function (data, next = null, prev = null) {
  return Object.create(null, {
    data: {
      writable: true,
      value: data
    },
    next: {
      writable: true,
      value: next
    },
    prev: {
      writable: true,
      value: prev
    }
  })
}

class LinkedList {
  constructor () {
    this.head = null
    this.tail = null
  }

  /**
   * return node at index
   * @param index
   */
  getNode (index) {
    let currNode = this.head,
        i = 0;

    while (currNode && i < index) {
      currNode = currNode.next
      i++
    }
    return currNode
  }

  /**
   * return value at index
   * @param index
   */
  getValue (index) {
    const node = this.getNode(index)
    return node ? node.data : undefined
  }

  /**
   * insert new node at the beginning of list
   * @param data
   */
  prepend (data) {
    const newNode = CreateNode(data, this.head)

    // if empty linked list
    if (!this.head) {
      this.tail = newNode
    } else {
      this.head.prev = newNode
    }
    this.head = newNode
  }

  /**
   * insert new node at the ending of list
   * @param data
   */
  append (data) {
    const newNode = CreateNode(data, null, this.tail)

    // if empty linked list
    if (!this.tail) {
      this.head = newNode
    } else {
      this.tail.next = newNode
    }
    this.tail = newNode
  }

  /**
   * insert node after index
   * @param index
   * @param data
   */
  insertAfter (index, data) {
    const prevNode = this.getNode(index)

    if (prevNode) {
      const newNode = CreateNode(data, prevNode.next, prevNode)

      prevNode.next.prev = newNode
      prevNode.next = newNode
    }
  }

  /**
   * Generator to enable for of loop
   */

  * values () {
    let currNode = this.head

    while (currNode) {
      yield currNode.data
      currNode = currNode.next
    }
  }

  [Symbol.iterator] () {
    return this.values()
  }
}

const list = new LinkedList()

list.append(10)
list.append(20)
list.append(30)
list.prepend(5)
list.insertAfter(1, 25)

for (const num of list) {
  console.log(num)
}

console.dir(list)
7

This topic was automatically closed 91 days after the last reply. New replies are no longer allowed.