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

Question

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

I suggest you read what LinkedList does. It is a doubly linked list and a good representation of what you should do in Java. — Peter Lawrey
– Peter Lawrey, Commented Mar 8, 2014 at 1:47

Florent Bayle · Accepted Answer · 2014-03-08 02:30:38Z

1

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

edited Mar 8, 2014 at 2:30

answered Mar 8, 2014 at 2:23

Florent Bayle

12k4 gold badges39 silver badges50 bronze badges

Sign up to request clarification or add additional context in comments.

3 Comments

Florent Bayle Over a year ago

@user3394847 I don't see that in the code I posted, do you mean nouveau.precedent.suivant = nouveau; ? In that case, this line of code update the suivant pointer of nouveau.precedent to make it point to nouveau. I could also have written it position.suivant = nouveau; in that particular case.

user3394847 Over a year ago

ok so for what i understand, fin.suivant.precedent = fin; is the same as position.precedent = fin;?

Florent Bayle Over a year ago

No, not in that case, because fin.suivant references the node you just created with new Noeud(element), and position references something else (I'm not really sure what position is supposed to be, I just assumed that you are iterating over the list, and it can be everything).

stack smasher · Accepted Answer · 2014-03-08 02:23:30Z

0

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

answered Mar 8, 2014 at 2:23

stack smasher

4633 silver badges12 bronze badges

Collectives™ on Stack Overflow

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

2 Answers 2

3 Comments

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

3 Comments

Comments

Your Answer

Sign up or log in

Post as a guest

Related