添加（索引，元素）方法

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

我的双向链表的节点 class：

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();
}

添加（索引，元素）方法

Add(index, element) method

java

methods

linked-list

doubly-linked-list