Best Adjacency List Implementation

Question

I can implement an adjacency list as either an Array of Linked Lists, or as a Map of Linked Lists (ie. a Hash Table). Is there ever a reason to use the Array implementation over the Map implementation? I ask because I have come across many websites that describe the Array implementation, but very few that mention using Hash Tables. From what I understand, HashTables should outperform Arrays.

Below is how I would code the Hash Table based Adjacency List along with the relevant code for helper classes.

LinkedListNode.js

class LinkedListNode {
  constructor(value = 0, next = undefined) {
    this.value = value;
    this.next = next;
  }
}

LinkedList.js (removed unnecessary functions)

class LinkedList {
  constructor(headValue = null) {
    this.head = headValue ? new LinkedListNode(headValue) : headValue;
  }

  addToTail(value) {
    const node = new LinkedListNode(value);
    if (!this.head) {
      this.head = node;
    } else {
      let pointer = this.head;
      while (pointer.next) {
        pointer = pointer.next;
      }
      pointer.next = node;
    }
  }
  
  toArray() {
    const items = [];
    let pointer = this.head;
    while (pointer) {
      items.push(pointer.value);
      pointer = pointer.next;
    }
    return items;
  }
}

HashTable.js - we are assuming no collisions

class HashTable {
  constructor() {
    this.items = {};
  }

  set(key, value) {
    if (this.items[key]) {
      this.items[key].addToTail(value);
    } else {
      this.items[key] = new LinkedList(value);
    }
  };

  get(key) {
    return this.items[key]; 
  }

  print() {
    const entries = Object.entries(this.items);
    for (let i = 0; i < entries.length; i += 1) {
      const [key, list] = entries[i];
      console.log(`${key}: ${list.toArray()}`);
    }
  }
}

Usage

const adjacencyList = new HashTable();
adjacencyList.set(1, 2);
adjacencyList.set(2, 4);
adjacencyList.set(3, 1);
adjacencyList.set(3, 2);
adjacencyList.set(3, 5);
adjacencyList.set(4, 6);
adjacencyList.set(5, 2);
adjacencyList.set(5, 4);
adjacencyList.set(5, 6);
adjacencyList.set(6, null);
adjacencyList.print();

// Outputs
'1: 2'
'2: 4'
'3: 1,2,5'
'4: 6'
'5: 2,4,6'
'6: '

Answer 1

Is there ever a reason to use the Array implementation over the Map implementation?

Yes:

• when you know the number of nodes n your graph has, and
• the nodes are identified by integers in the range 0..n-1

In that case, the "hash" is the index in the array. Some JavaScript engines may produce faster code for when you work with arrays instead of plain objects.

NB: it will certainly be faster if you replace the linked lists with arrays (and push).