CODEWITHSUNDEEP
java
user3394847
user3394847

Reputation: 1

java double linked list, simple linked list convert to double linked list

I have been ask to convert my simple linkedlist to double linked list, if anyone could give me a bit of guidance. ill appreciate thx.. when i'm inserting the elements with the insertionapres(elements), should i put the new node in the temp node???

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

Upvotes: 0

Views: 188

Answers (2)

Florent Bayle
Florent Bayle

Reputation: 11910

So, it seems that you want to insert a node in the middle of two other nodes.

What you have to do, is create a new node, set the pointers precedent and suivant to the previous and next nodes, and update the pointers of the previous and next node, something like that:

Double Linked List Node Insertion

So, if you change your code to do it, it will be something like that:

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

You also have to change your other methods to always have precedent and suivant pointing to the previous/next node:

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

Upvotes: 1

stack smasher
stack smasher

Reputation: 463

Not just your insertionapres() method, but in all your methods you need a temp. For example, in your insererDebut() function, you should set the suivant and precedent variables.

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

I'm not sure what your position variable is for.

The other two methods should work similarly

Upvotes: 0

Related Questions