Добавить (индекс, элемент) метод

Question

Я реализую метод add (int index, E element), который должен вставлять указанный элемент по указанному индексу в список и смещать элемент, находящийся в данный момент в этой позиции, и любые последующие элементы вправо. Кто-нибудь знает, почему мой метод не работает, когда мой код:

        newNode.setNext(temp.getNext());
        newNode.setPrev(temp);
        newNode.getNext().setPrev(newNode);
        temp.setNext(newNode);

в конце метода, но работает, когда у меня есть только

        newNode.setNext(temp.getNext());
        temp.setNext(newNode);

Мой код:

public class DoubleLinkedList<E> implements IDoubleLinkedList<E> {

DLLNode head;
DLLNode tail;
int size = 0;
@Override
public void add(int index, E element) throws IndexOutOfBoundsException {
    if (index > size) {
        throw new IndexOutOfBoundsException();
    }
    if (index < 0) {
        throw new IndexOutOfBoundsException();
    }
    if (head == null) {
        head = new DLLNode(element);
        tail = head;
    }
    else if (index == 0) {
        DLLNode temp = new DLLNode(element);
        temp.setNext(head);
        head = temp;
    } else {
        DLLNode temp = head;
        for (int i = 1; i < index; i++) {
            temp = temp.getNext();
        }
        DLLNode newNode = new DLLNode(element);
        newNode.setNext(temp.getNext());
        newNode.setPrev(temp);
        newNode.getNext().setPrev(newNode);
        temp.setNext(newNode);
    }
    size ++;
}

Класс узла для моего списка DoublyLinkedlist:

public class DLLNode<E> {
private DLLNode<E> next;
private DLLNode<E> prev;
private E element;

public DLLNode(E element){
    this.element=element;
    prev=null;
    next=null;
}
public DLLNode(E element, DLLNode prev, DLLNode next) {
    this.element=element;
    this.prev=prev;
    this.next=next;
}
public E getData(){
    return element;
}

public void setData(E element){
    this.element=element;
}

public DLLNode getPrev(){
    return prev;
}

public DLLNode getNext(){
    return next;
}

public void setPrev(DLLNode where){
    prev=where;
}

public void setNext(DLLNode where){
    next=where;
}}

Answer 1

Это не работает по трем причинам, которые я вижу:

• В блоке if (index == 0) вы никогда не установите значение prev головного узла.

• В блоке else вы никогда не проверяете, находитесь ли вы в конце списка, поэтому вы получите NullPointerException, если вы есть.

• В обоих блоках if (index == 0) и else вы не установите tail, если новый узел является последним узлом.

На стороне примечание: вы используете raw генерики во всем. Никогда не используйте DLLNode без < сразу после него. В основном, измените все DLLNode на DLLNode<E>.

---

Вот как вы тестируете свой собственный код.

Добавьте этот метод к DLLNode:

void verifyIntegrity() {
    if (this.prev != null && this.prev.next != this)
        throw new AssertionError("prev.next is corrupt");
    if (this.next != null && this.next.prev != this)
        throw new AssertionError("next.prev is corrupt");
}

Добавьте этот метод к DoubleLinkedList:

void verifyIntegrity() {
    int count = 0;
    DLLNode<E> last = this.head;
    for (DLLNode<E> node = this.head; node != null; count++, last = node, node = node.getNext())
        node.verifyIntegrity();
    if (this.tail != last)
        throw new AssertionError("tail is corrupt");
    if (this.size != count)
        throw new AssertionError("size is corrupt");
}

Теперь проверьте ваш код следующим образом:

DoubleLinkedList<Integer> listHead = new DoubleLinkedList<>();
DoubleLinkedList<Integer> listTail = new DoubleLinkedList<>();
DoubleLinkedList<Integer> listMid = new DoubleLinkedList<>();
listHead.verifyIntegrity();
listTail.verifyIntegrity();
listMid.verifyIntegrity();
for (int i = 0; i < 10; i++) {
    listHead.add(0, i);
    listTail.add(i, i);
    listMid.add(i / 2, i);
    listHead.verifyIntegrity();
    listTail.verifyIntegrity();
    listMid.verifyIntegrity();
}