Help with Doubly Link List - Deleting a Node - Java Code

general
, ,
1

**My code compiles and deletes from the head and tail, but I’m not able to delete from the middle. Can someone look at my code and see what I’m missing. Thanks **

public class Queue {

private IntDNode head;

private IntDNode tail;

public Queue() {

  head = tail = null;

}

public void insertToSortedlist(int n) {

IntDNode node = head;

while (node != null && n >= node.getData()) {
    node = node.getNext();
}

if (node == head) {
    addToHead(n);
}
else {
    if (node == null) {
	addToTail(n);
    }
    else {
	insertBefore(n, node);
    }
}

}

private void addToHead(int n) {

 head = new IntDNode (n, null, head);
 if (head.getNext() != null) {
head.getNext().setPrev(head);
 }
 if (tail == null) {
tail = head;
 }
 else {
if (tail.getPrev() == null) {
    tail.setPrev(head);	
}
 }

}

private void addToTail(int n) {

IntDNode temp = new IntDNode(n, tail, null);
tail.setNext(temp);
tail = temp;

}

private void insertBefore(int n, IntDNode node) {

IntDNode temp = new IntDNode(n, node.getPrev(), node);
node.setPrev(temp);
temp.getPrev().setNext(temp);

}

public void addToQueue(int n) {

IntDNode node = head;
while (node != null && n >= node.getData()) {
      node = node.getNext();
}

if (node == head) {
    addToHead(n);	
}
else {
    if (node == null) {
	addToTail(n);
    }
    else {
	insertBefore(n, node);
    }
}

}

private void deleteFromTail() {

  tail = tail.getPrev();
if (tail == null) {
  head = null;
  }

  else {
    tail.setNext(null);
  }

}

private void deleteFromHead() {

  head = head.getNext();
if (head == null) {
  tail = null;
  }

  else {
    tail.setPrev(head);
  }

}

public void deleteFromQueue(int n) {

 IntDNode auxNode = head;

 while (auxNode != null && auxNode.getData() < n) {

     auxNode = auxNode.getNext();
 }
 if (auxNode != null && auxNode.getData() == n) {

    if (auxNode == tail) {

       deleteFromTail();

    }

else {
    if (auxNode == head) {
     deleteFromHead();
        }
    else {
	
    }
    }
 }

}

public boolean isEmpty() {

  return head == null;

}

public void printQueue() {

  if (isEmpty()) {
     System.out.println("The list is empty");
  }
  else {
     IntDNode node = head;
     while (node != null) {
        System.out.print(node.getData() + " ");
        node = node.getNext();
     }
     System.out.println();
  }

}

}

2

In this code of yours,

if (auxNode != null && auxNode.getData() == n) {

if (auxNode == tail) {

   deleteFromTail();

} else {
if (auxNode == head) {
 deleteFromHead();
    }
else {

}

Will you please explain how you expect deletion to occur? lets say your list is 2,3,6,7 and you have to delete 6, then auxnode is the third node i.e. node with value 6. Now any of your if conditions are not satisfied, so how it’ll be deleted? Neither auxnode is head nor it is tail, and nothing you have specified in the else part.

3

That is where I’m having the problem, I’ve set else{ } with:

head = head.getNext;
tail = tail.getNext;
head.setPrev(Tail);
tail.setPrev(head);
head = null;
tail = null;
tail.setNext(null);
tail.setPrev(head);

But none of this commands didn’t work. It’s missing that one element there but I’m not able to come up with it.

4

what you need to do is : let the list is 1,2,3,6,7 and you have to delete 6 , then using temporary variable let’s say, temp=auxnode->left; and next=auxnode->right;
then set, temp->right=next and next->left as temp and free auxnode. PS: this is regard with the assumption that you have left and right fields in your struct node. If you’re not using that as I can see in your code, your head=head.getnext() is wrong because you need to get the just previous node of auxnode, so traverse head till traverse->next== auxnode.