Блог

Главная - Вопросы по программированию - Удаление узла в заданной позиции в двусвязном списке

Удаление узла в заданной позиции в двусвязном списке

#java #doubly-linked-list

#java #двусвязный список

Вопрос:

Я пытаюсь удалить узел с заданным индексом, но я продолжаю проваливать тесты и иногда даже получаю NullPointerException . Вот что я сделал до сих пор:

 public void remove(int pos)

{

 if (head == last)

        {
            head = null;
            last = null;
        }
        if (pos == size - 1)

            return removeLast();

        if (pos == 0)

            return removeFirst();

        else
        {
            DoubleListNode<E> current = head;

            for (int i = 0; i < pos - 1; i   )

            {

                current = current.getNext();

            }
            current.setNext(current.getNext().getNext());

            current.getNext().getNext().setPrev(current);

            return current.getData();
        }
}

Комментарии:

1. Вы не проверяете, возвращает ли GetNext() значение null. Представьте, что произошло бы, если бы в вашем связанном списке был только один элемент (GetNext вернул бы нулевой указатель).

2. если бы это было так, разве не было бы перехода к if (pos == 0), как если бы был только один узел, тогда позиция была бы 0, верно?

3. pos может быть любым номером, который вы передаете для удаления(). Это может быть больше длины списка, и это будет означать, что цикл for выйдет за пределы последнего элемента.

4. Я поставил предварительное условие, что pos будет >= 0 и <= size. Он по-прежнему выдает мне ошибку, а также не выполняет тестовые примеры. Я думаю, что моя логика здесь не совсем верна.

Ответ №1:

Шаги по удалению из двусвязного списка:

Пусть удаляемый узел равен del.

  1. Если удаляемый узел является головным узлом, то измените указатель заголовка на следующий текущий заголовок.
  2. Установите следующий из предыдущих в del, если предыдущий в del существует.
  3. Установите значение prev рядом с del, если существует значение next to del.

Помните, здесь вы должны поддерживать как предыдущий, так и следующий указатель, а также обрабатывать условие null с обеих сторон.