指向先前节点的Java双链接列表指针

Question

我正在制作一个方法，将一个节点添加到名为“publicvoidadd（int-index，T-value）”的列表中。

此方法将把一个值放入索引中，然后将有指向列表中下一个和上一个元素的指针。我把指向前面节点的指针搞砸了，我一直坐在那里进行实验，但没有让它工作。

示例：我们有一个包含整数值[2,4,6]实例变量的列表：Node head、tail；整数金额，变动；

内部类的实例变量为：T值；节点prev，next；

输入：

add(1, 3);
System.out.println(list.toString());
System.out.println(list.backwardsString());

预期产出：

[2, 3, 4, 6]
[6, 4, 3, 2]

到目前为止，我的代码是：

public void add(int index, T value) {
if (index < 0 || index > amount) {
        throw new IndexOutOfBoundsException("Index is not between 0 and amount!");
    }

    if (value== null) {
        throw new NullPointerException("Value can't be null!");
    }

    if (amount == 0) {
        head = tail= new Node<>(value, null, null);
    }
    else if (index == 0) {
        head = head.prev= new Node<>(value, null, head);
    }
    else if (index == amount) {
        tail = tail.next= new Node<>(value, tail, null);
    } 
    else {
        Node<T> p = head;  
        for (int i = 1; i < index; i++) {
            p = p.next;
        }
        p.next= new Node<>(value, p, p.next);


        p = tail;
        for (int i = amount; i > index; i--) {
            p.prev= new Node<>(value, p.prev, p);
            p = p.prev;
        }*/
    }

    amount++;
    changes++;
}

在这个场合，我也会问你

p、 上。下一个或下一个。上

工作

Answer 1

通过在List类中引入一个空的伪节点，可以大大简化设计。

由于此节点始终存在，因此不需要以下特殊情况：

if (amount == 0) {
    head = tail= new Node<>(value, null, null);
}
else if (index == 0) {
    head = head.prev= new Node<>(value, null, head);
}

第一个伪节点可以用

pseudo.next = pseudo;
pseudo.prev = pseudo;

列表是空的，如果

pseudo.next == pseudo.prev

真正的列表开始将pseudo.next，最后一个列表条目将pseudo.prev.所以你的列表实际上是一个环。

您的搜索循环将变为

   Node<T> p = pseudo.next;  
   for (int i = 0; i < index && p!=pseudo; i++) {
        p = p.next;
   }

然而，在这里：

   p.next= new Node<>(value, p, p.next);

下一步你必须操纵p。prev，它还指向（或更好地指）非法节点

但我把它作为家庭作业——这显然是；-）

编辑：

演示前哨节点的完整列表实现

公共班级名单{

public class  Node {
    T value = null;
    Node(T v) {
        value=v;
    }
    Node()   {
    }
    public Node getNext() {
        return next;
    }

    public Node getPrev () {
        return prev;
    }
    public T getValue() {
        return value;
    }

    Node prev = null;
    Node next = null;
};

private Node pseudo = new Node();

List() {
    pseudo.next = pseudo.prev = pseudo;
}

public Node getBegin() {
    return pseudo.next;
}

public Node getEnd() {
    return pseudo;
}

public boolean add(int index, T value) {
    Node p = pseudo.next;

    for (int i = 0; i < index && p!=pseudo; i++) {
        p = p.next;
    }

    // Correct for tail insertion
    if(p == getEnd())
        p = p.prev;

    Node ptm = p.next;

    p.next      = new Node(value);
    p.next.next = ptm;
    p.next.prev = p;
    ptm.prev    = p.next;

    return true;
}

public void delete(int i) {

    Node p = pseudo.next;

    for (int ix = 0; ix < i && p!=pseudo; ix++) {
        p = p.next;
    }

    if(p != getEnd()) {
        Node ptm = p.prev;
        p.prev.next = p.next;
        p.next.prev = ptm;
    }       
}

}