Puedo implementar una lista de adyacencia como una matriz de listas vinculadas o como un mapa de listas vinculadas (es decir, una tabla hash). ¿Hay alguna razón para usar la implementación de Array sobre la implementación de Map? Pregunto porque me he encontrado con muchos sitios web que describen la implementación de Array, pero muy pocos que mencionan el uso de Hash Tables. Por lo que entiendo, HashTables debería superar a Arrays.

A continuación se muestra cómo codificaría la lista de adyacencia basada en la tabla hash junto con el código relevante para las clases auxiliares.

LinkedListNode.js

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

LinkedList.js (funciones innecesarias eliminadas)

 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: asumimos que no hay colisiones

 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()}`); } } }

Uso

 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: '