Блог

Я могу реализовать список смежности либо в виде массива Связанных списков, либо в виде Карты Связанных списков (т. Е. хэш-таблица). Есть ли когда-нибудь причина использовать реализацию массива поверх реализации карты? Я спрашиваю, потому что я сталкивался со многими веб-сайтами, которые описывают реализацию массива, но очень немногие упоминают использование хэш-таблиц. Насколько я понимаю, хэш-таблицы должны превосходить массивы.

Ниже показано, как я бы закодировал список смежности на основе хэш-таблицы вместе с соответствующим кодом для вспомогательных классов.

LinkedListNode.js

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

LinkedList.js (удалены ненужные функции)

 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 — мы предполагаем, что столкновений не будет

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

Использование

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

Есть ли когда-нибудь причина использовать реализацию массива поверх реализации карты?

ДА:

• когда вы знаете, сколько узлов n имеет ваш график, и
• узлы идентифицируются целыми числами в диапазоне 0..n-1

В этом случае «хэш» — это индекс в массиве. Некоторые движки JavaScript могут создавать более быстрый код, когда вы работаете с массивами вместо обычных объектов.

ПРИМЕЧАНИЕ: это, безусловно, будет быстрее, если вы замените связанные списки массивами (и push ).