How to distinguish between Array's empty items and undefined?

Question

I'm trying to implement a Linked List with Array's methods. Currently trying to implement indexOf and includes. I was looking into the following corner case:

var arr = [1,2,,4,5];
console.log(arr.indexOf(undefined));
console.log(arr.includes(undefined));
console.log(arr[2] === undefined);

Output:

-1
true
true

It looks like, for arr=[1,2,,4,5] it will actually keep undefined at arr[2]. Reading ECMA-262 and based on this page, indexOf uses "Strict Equality" (operator === ) and includes uses SameValueZero (Same as Object.is, except -0 is considered equal to +0). My functions are:

isStrictlyEqual(x,y) {
  return x === y;
}

sameValue(x, y) {
  return Object.is(x,y);
}

sameValueZero(x, y) {
  return x === y || (Number.isNaN(x) && Number.isNaN(y));
}

The implementation of sameValueZero was taken from this topic.

My indexOf uses this isStrictlyEqual and my includes uses this sameValueZero. But, sameValueZero(undefined,undefined) returns true so My indexOf return index 2 for indexOf(undefined) while arr.indexOf(undefined) returns -1. Note that [1,2,undefined,4,5].indexOf(undefined) returns 2. So my only guess is that Array does not actually store this empty item as undefined.

I have a method that allows to fill a linked list from an existing array, like so:

  _extend(iterable) {
    for (var i = 0; i < iterable.length; ++i) {
      this.push(iterable[i]);
    }

In this case iterable[2] will return undefined so my DS will save undefined at index 2. Also tried to use forEach, but it actually skips the empty items.

I want my linked list to be similar to implementation of Array and follow ECMA specification. How my linked list should treat this corner case? Keeping undefined at that place, didn't work because of indexOf. I guess I need to distinguish between an empty item and undefined. How can I do so? I came across with this topic - does it mean I need to do two loops on the array? One regular for and one for in? Would I need to create a dummy node in that case? Does it make sense to do it for Linked list?

My linked list class:

class DoublyLinkedList {
  constructor(array=null) {
    this.head = null;
    this.tail = null;
    this.length = 0;
    if (array !== null) {
      this._extend(array);
    }
  }

}

score 1 · Answer 1 · answered Nov 25 '22 at 17:42

Yes, you can (have to) add a dummy node and check for it in includes (and I guess also find and findIndex). Here's a POC:

const HOLE = Symbol()

class MyArray {
  constructor() {
    this.items = []
  }

  extend(a) {
    for (let i = 0; i < a.length; i++)
      this.items.push(
        a.hasOwnProperty(i) ? a[i] : HOLE
      )
  }

  indexOf(val) {
    for (let i = 0; i < this.items.length; i++)
      if (this.items[i] === val)
        return i
    return -1
  }

  includes(val) {
    for (let i = 0; i < this.items.length; i++)
      if (Object.is(this.items[i], val) || (val === undefined && this.items[i] === HOLE))
        return true
    return false
  }
}


m = new MyArray()
m.extend([1, 2, 3, , 5])

console.log(m.indexOf(undefined))
console.log(m.includes(undefined))

m = new MyArray()
m.extend([1, 2, 3, undefined, 5])

console.log(m.indexOf(undefined))
console.log(m.includes(undefined))

How to distinguish between Array's empty items and undefined?

1 Answers1