Лучший способ реализации linkedList в javascript

Резюме: Важно понять, как работает LinkedList, потому что это полезный пример его использования на предыдущей и следующей странице в веб-браузере.

Введение

Необходимые условия

Реализация

Примеры использования

Введение

Что такое связный список, как гласит Википедия: «Связный список — это последовательность узлов, которые содержат два поля: целочисленное значение и ссылку на следующий узел. Последний узел связан с терминатором, используемым для обозначения конца списка.»

Википедия дает хорошее объяснение LinkedList, но как он выглядит?

Изображение дает представление о том, как LinkedList выглядит визуально.

Предварительные условия

  • [x] Знать основы javascript

    • [!important] классы
  • [x] Полезные ссылки

    • очередь
    • стек
    • приоритетная очередь

Реализация
Подождите…

Прежде чем мы начнем, я хочу пожелать всем хорошей пятницы и выходных.

Сейчас

Давайте разберем это

class Node {
  constructor(elements, next = null) {
    this.elements = elements;
    this.next = next;
  }
}
Вход в полноэкранный режим Выход из полноэкранного режима

Мы создаем хранилище, где мы будем хранить наши узлы, оно делает довольно простые вещи, мы создаем конструктор, после чего у него есть несколько параметров, мы увидим их использование.

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

}
Вход в полноэкранный режим Выход из полноэкранного режима

Мы инициализируем любой другой класс, но теперь у нас есть null head и size для хранения длины связного списка, теперь пришло время посмотреть на методы, которые использует класс.

Методы

  • InsertH: вставка элемента в начало списка.

  • add: добавление элемента в конец списка.

  • insert: добавление любого элемента по индексу.

  • deleteL: удаление элемента в конце списка.

  • removeFrom: удаление любого элемента из индекса.

  • indexOf: получение индекса любого элемента.

  • print: печать списка LinkedList.

insertH(elements) {
    const node = new Node(elements, this.head);

    this.head = node;

    this.size++;
    return node;
  }
Вход в полноэкранный режим Выход из полноэкранного режима

Эта функция делает основные вещи, сначала у нее есть параметр, а затем в функции мы инициализируем класс Node. Помните про store, а теперь мы меняем this.head на Node из head store узел и left являются первичными.

add(elements) {
    let node = new Node(elements);

    let current;
    if (this.head === null) {
      this.head = node;
    } else {
      current = this.head;

      while (current.next) {
        current = current.next;
      }

      current.next = node;
    }
    this.size++;
  }
Вход в полноэкранный режим Выход из полноэкранного режима

Теперь мы добавляем последний элемент списка, проверяем, является ли this.head нулевым, если да, то this.head устанавливается на узел.
Если нет, мы идем и создаем current= this.head для доступа к свойствам узла после того, как мы пройдемся по списку в конце, если дойдем до конца, то current.next = node; остальные основные.

Позвольте мне перейти от простого к сложному.

   indexOf(elements) {
    let current = this.head;
    let it = 0;
    while (current != null) {
      if (current.elements === elements) {
        console.log('elements', current.elements);
        return it;
      }

      it++;
      current = current.next;
    }
    return null;
  }
  print() {
    let current = this.head;

    let str = '';
    while (current) {
      str += current.elements + '-->';

      current = current.next;
    }

    return console.log(str);
  }

  get length() {
    return console.log(this.size);
  }
Вход в полноэкранный режим Выход из полноэкранного режима

Мы видим, что методов так много, но они просты, что выглядит сложно, так это indexOf, который я собираюсь объяснить.

 indexOf(elements) {
    let current = this.head;
    let it = 0;
    while (current != null) {
      if (current.elements === elements) {
        console.log('elements', current.elements);
        return it;
      }

      it++;
      current = current.next;
    }
    return null;
  }
Вход в полноэкранный режим Выход из полноэкранного режима

Здесь мы пытаемся получить indexOf любого элемента, теперь сначала current устанавливается в this.head затем мы создаем цикл while, в котором сначала проверяем, не равен ли current null затем вне цикла мы увеличиваем it и затем устанавливаем current в current.next затем если элемент не найден мы возвращаем null.

  insert(elements, index) {
    if (index < 0 || index > this.size) return -1;
    else {
      let node = new Node(elements);

      let current, prev, it;

      current = this.head;
      it = 0;
      if (index === 0) {
        this.insertH(elements);
      } else {
        while (it < index) {
          it++;
          prev = current;
          current = current.next;
        }
        node.next = current;
        prev.next = node;
      }
      this.size++;
    }
  }
Вход в полноэкранный режим Выход из полноэкранного режима

Итак, первое, что мы видим, это то, что мы создаем два параметра, первый параметр получает данные, а второй проверяет, доступен ли индекс, затем в функции if (index < 0 || index > this.size) return -1; проверяется, если индекс меньше 0 или индекс больше size, то мы возвращаем -1, что означает, что это null. В операторе else мы инициализируем class Node создаем три переменные, затем устанавливаем current в this.head, после этого устанавливаем it, потому что мы будем использовать его для вставки элементов, теперь мы смотрим, равен ли индекс нулю, если да, то вставляем его в начало. если нет, то зацикливаем список, пока it меньше index, затем устанавливаем prev в current, а затем current в current.next, после чего выходим из цикла.

// remove the element
 node.next = current;
 prev.next = node;
Вход в полноэкранный режим Выход из полноэкранного режима
removeFrom(index) {
    if (index < 0 || index >= this.size) return -1;
    else {
      let current, prev, it;
      it = 0;
      current = this.head;
      prev = current;
      if (index === 0) {
        this.head = current.next;
      } else {
        while (it < 0) {
          it++;
          prev = current;
          current = current.next;
        }
        prev.next = current.next;
      }
      this.size--;

      return current.elements;
    }
  }
Войти в полноэкранный режим Выход из полноэкранного режима

Удаление элемента в списке по индексу очень просто, как показано в приведенном выше коде. Сначала мы проверяем, меньше ли индекс нуля или больше нуля, если да, то мы возвращаем -1, что означает, что это null Следующий код прост, но после проверки w, если индекс равен нулю, то мы удаляем голову в операторе else мы перебираем циклы до тех пор, пока it, меньше нуля, то мы увеличиваем его после, как показано ниже, мы устанавливаем prev в current и затем current в current. Следующий после этого является довольно простым и понятным.

 prev = current;
 current = current.next;
Войти в полноэкранный режим Выйти из полноэкранного режима
  deleteL(elements) {
    let current = this.head;

    let prev = null;
    while (current != null) {
      if (current.elements === elements) {
        if (prev === null) {
          this.head = current.next;
        } else {
          prev.next = current.next;
        }
        this.size--;
        return current.elements;
      }
      prev = current;
      current = current.next;
    }

    return -1;
  }
Войти в полноэкранный режим Выйти из полноэкранного режима

Сначала мы создадим переменную current, как мы это делали во многих наших кодах. Полагаю, вы уже знакомы с ней, обратите внимание, что prev имеет значение null. Теперь мы перебираем список, пока переменная не станет нулевой, затем мы проверяем, равен ли current.next данным elements, которые мы вставили. Затем внутри оператора if у нас есть еще один оператор, который проверяет, что если prev равен null, мы удаляем элемент, а в операторе else то же самое, мы уменьшаем size, и левый элемент остается основным.

let node = new LinkedList();

node.insertH(1);
node.add(2);

node.add(4);

node.add(5);
node.insert(47, 0);

node.deleteL(1);
console.log(node.indexOf(47));
node.removeFrom(0);

node.length

node.print();
Вход в полноэкранный режим Выход из полноэкранного режима

Вывод терминала

Полный код.

class Node {
  constructor(elements, next = null) {
    this.elements = elements;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.size = 0;
  }

  insertH(elements) {
    const node = new Node(elements, this.head);

    this.head = node;

    this.size++;
    return node;
  }

  add(elements) {
    let node = new Node(elements);

    let current;
    if (this.head === null) {
      this.head = node;
    } else {
      current = this.head;

      while (current.next) {
        current = current.next;
      }

      current.next = node;
    }
    this.size++;
  }
  insert(elements, index) {
    if (index < 0 || index > this.size) return -1;
    else {
      let node = new Node(elements);

      let current, prev, it;

      current = this.head;
      it = 0;
      if (index === 0) {
        this.insertH(elements);
      } else {
        while (it < index) {
          it++;
          prev = current;
          current = current.next;
        }
        node.next = current;
        prev.next = node;
      }
      this.size++;
    }
  }

  removeFrom(index) {
    if (index < 0 || index >= this.size) return -1;
    else {
      let current, prev, it;
      it = 0;
      current = this.head;
      prev = current;
      if (index === 0) {
        this.head = current.next;
      } else {
        while (it < 0) {
          it++;
          prev = current;
          current = current.next;
        }
        prev.next = current.next;
      }
      this.size--;

      return current.elements;
    }
  }

  deleteL(elements) {
    let current = this.head;

    let prev = null;
    while (current != null) {
      if (current.elements === elements) {
        if (prev === null) {
          this.head = current.next;
        } else {
          prev.next = current.next;
        }
        this.size--;
        return current.elements;
      }
      prev = current;
      current = current.next;
    }

    return -1;
  }

  indexOf(elements) {
    let current = this.head;
    let it = 0;
    while (current != null) {
      if (current.elements === elements) {
        console.log('elements', current.elements);
        return it;
      }

      it++;
      current = current.next;
    }
    return null;
  }
  print() {
    let current = this.head;

    let str = '';
    while (current) {
      str += current.elements + '-->';

      current = current.next;
    }

    return console.log(str);
  }

  get length() {
    return console.log(this.size);
  }
}

let node = new LinkedList();

node.insertH(1);
node.add(2);

node.add(4);

node.add(5);
node.insert(47, 0);

node.deleteL(1);
console.log(node.indexOf(47));
node.removeFrom(0);

node.length

node.print();

Вход в полноэкранный режим Выход из полноэкранного режима

Оцените статью
devanswers.ru
Добавить комментарий