java双向链表，简单链表转换为双向链表

Question

我被要求将我的简单链表转换为双向链表，如果有人能给我一点指导的话。我很感谢你..当我插入带有insertionapres(元素)的元素时，我是否应该将新节点放在temp节点中？

public class dlink {

private static class node{

 private Object element;
 private node next;
 private node prev;

 public node(Object element){
         this.element = element;
         next = null;
         prev= null;
     }
 }

Answer 1

因此，您似乎想要在其他两个节点的中间插入一个节点。

您需要做的是创建一个新节点，将指针precedent和suivant设置为上一个和下一个节点，并更新上一个和下一个节点的指针，如下所示：

​

​

所以，如果你改变你的代码来做这件事，它会是这样的：

// Insert a new node after position
public void insererApres(Object element){
    if(debut == null)
        insererDebut(element);
    else if (position == fin)
        insererFin(element);
    else {
        // First, create the new node
        Noeud nouveau = new Noeud(element);

        // Set the pointers
        nouveau.suivant = position.suivant;
        nouveau.precedent = position;

        // Update the previous node pointer
        nouveau.precedent.suivant = nouveau;

        // Update the next node pointer
        nouveau.suivant.precedent = nouveau;

        position = position.suivant;

        nbElement++;            
    }
}

您还必须更改其他方法，使precedent和suivant始终指向上一个/下一个节点：

public void insererDebut(Object element){
    Noeud noeud = new Noeud(element);

    noeud.suivant = debut;

    if (noeud.suivant!=null)
        noeud.suivant.precedent = noeud;

    debut = noeud;

    if (nbElement == 0)
        fin = debut;

    position = debut;

    nbElement++;
}

public void insererFin(Object element){
    if(debut == null)
        insererDebut(element);
    else{   
        fin.suivant = new Noeud(element);

        fin.suivant.precedent = fin;

        fin = fin.suivant;

        position = fin;

        nbElement++;
    }               
}

Answer 2

不仅仅是你的insertionapres()方法，而且在你的所有方法中，你都需要一个临时的。例如，在insererDebut()函数中，您应该设置suivant和precedent变量。

public void insererDebut(Object element){

     Noeud n = new Noeud(element);

     nbElement++;
     if (nbElement == 0){
         debut = n
         fin = debut;
     }else{
         debut.precedent = n;
         n.suivant = debut;
         debut = n;
     }
 }

我不确定position变量是用来做什么的。

另外两种方法的工作方式应该类似。