java - 添加(索引，元素)方法

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 ++;
}

我的 DoubleLinkedlist 的节点类:

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) block ，你永远不会设置 prev头节点的值。

• 在 else block ，你永远不会检查你是否在列表的末尾，所以你会得到 NullPointerException如果你是的话。

• 在 if (index == 0) 中 block 和else阻止，你不设置 tail如果新节点是最后一个节点。

附注:您正在使用原始泛型。切勿使用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();
}