Привет всем, это часть 5.2 из серии блогов о структурах данных и алгоритмах в JavaScript. В предыдущем блоге я рассмотрел push, insert и связанного списка. em>getElementAt методы. Здесь я расскажу об оставшихся методах removeAt, remove и indexOf.

Реализация связанного списка в Javascript

Индекс чего-либо

Этот метод вернет индекс данного элемента, если он существует, иначе вернет -1 ({4}). Чтобы найти индекс элемента, мы начнем с главного элемента ({1}) и будем выполнять цикл до тех пор, пока элемент не будет найден ({2}) и возвращает его индекс ({3}) .

indexOf(element) {
        let current = this.head; //1
        for (let index = 0; index < this.count && current != null; index++) {
            if (current.element == element) { //2
                return index;
            }
            current = current.next; //3
        }
        return -1; //4
    }

RemoveAt

Удаляем элемент по указанному индексу, мы сначала проверяем, является ли связанный список пустым, иначе возвращаем undefined ({1}). После этого мы проверяем ошибку индекса за пределами границы , по проверке - это индекс, который больше нуля и меньше count.

  • Мы хотим удалить первый элемент, т.е. индекс, равный нулю ({2}), сдвинуть голову к следующему узлу. Мы будем ссылаться на первый элемент списка, используя текущую переменную. Если мы назначим заголовок текущему следующему элементу, мы удалим первый элемент ({3}).

  • Мы хотим удалить последний элемент или элемент из связанного списка, мы будем использовать метод getElementAt, чтобы получить один предыдущий элемент, используя индекс -1 ({4}), текущий будет следующим ({5}) предыдущего. Итак, чтобы удалить текущий узел, все, что нам нужно сделать, это связать previous.next с current.next ({6}).

removeAt(index) {
        if (this.isEmpty()) {
            return undefined; //1
        }        
        if (index >= 0 && index < this.count) {

            let current = this.head
            if (index == 0) { // 2
                this.head = current.next;  //3 
            } else {
                let previous = this.getElementAt(index - 1);  //4               
                current = previous.next; //5
                previous.next = current.next; //6
            }
            this.count--;
            return current.element;
        }
        return undefined;
    }

Удалять

Чтобы удалить элемент, мы проверяем, не пуст ли связанный список.
Если нет, то получаем индекс элемента с помощью метода indexOf, если индекс -1, то элемент не существует, иначе используйте индекс и удалите элемент из связанного списка с помощью метода removeAt.

remove(element) {
        if (this.isEmpty()) {
            return undefined;
        }
        let index = this.indexOf(element);
        if (index != -1) {
            this.removeAt(index);
        }
        return undefined;
    }

вы получаете полный источник здесь

Вывод :

Итак, следите за обновлениями в следующем блоге, в котором я расскажу о другом двухсвязном списке DS.