Removing a random node from both singly- and doubly-linked lists

0
votes

I'm having a hard time coming up with the logic for removing some node from both a doubly and singly linked list. I've looked online from help, but I couldn't find a simple example of it. Here is what I have:

Doubly linked deletion. dCurrent is the node that we want to delete.

if (dCurrent == dHead){
   dHead = dCurrent->next;
   dHead->prev = NULL;
}
else if(dCurrent == dTail){
   dTail = dCurrent->prev;
   dTail->next = NULL;
}
else{
   dCurrent->next->prev = dCurrent->prev;
   dCurrent->prev->next = dCurrent->next;   
}

Here is what I have for the singly linked list. Again, sCurrent is the node to delete. and sPrev = sCurrent->prev.

if(sPrev == NULL){
   sHead = sCurrent->next;
}
else{
   sPrev->next = sCurrent->next;
}

The problem is that after I delete a collection of random nodes from both lists, the doubly linked list displays correctly from head to tail, but not tail to head. The singly linked list doesn't display correctly, either.

2
clinked-listsingly-linked-listdoubly-linked-list
So what is your problem. From the first look the code is ok. - Roman Byshko
The code looks ok. And your question is? - Piotr Zierhoffer
Sorry, somehow I forgot to state my problem. Fixed now - Michael Schilling
@MichaelSchilling: The code that you've shown doesn't seem to contain the bug. I think you need to post a complete program that's as brief as possible while still displaying your problem. (Also, you might want to restrict this question to just one problem or the other. The problem with your doubly-linked-list program might turn out to be completely unrelated to the problem with your singly-linked-list program, in which case they should be separate questions, or they might turn out to be exactly the same, in which case you'll only need to ask about one, anyway.) - ruakh

2 Answers

3
votes

Your doubly-linked-list logic looks fine to me. My only concern is that if dCurrent is the only element in the list, then this:

if (dCurrent == dHead){
    dHead = dCurrent->next;
    dHead->prev = NULL;
}

will most likely try to reference a null-pointer. (It depends on how you design your list. But in a typical design, if dCurrent is the only node, then dCurrent->next is NULL.)

Your singly-linked-list logic also looks fine to me, in the abstract, given the assumption that "sPrev = sCurrent->prev"; but I don't understand how that assumption can be correct. If it's a singly-linked list, then sCurrent doesn't have a prev pointer.

0
votes

The only issues I can see is that your code won't function properly for scenarios where head or tail are updated to NULL.

Basically if you delete the only node, dHead will point to null, so you need to put "guards" around subsequent statements like

dHead->prev = NULL;

like so

if (dHead != NULL) {
  dHead->prev = NULL;
}

One way to "get around" having so many conditionals is to assign a NIL (not a type) element.

NIL is the "node" which replaces NULL. It represents "off the data portion of the list" so its next is ALWAYS NIL (a circular reference) and it's previous is ALWAYS NIL (a circular reference). In such cases, you ensure that NIL is never accessible outside of the list, and that head->prev == NIL and tail->next == NIL. That way you can avoid the many if (tail != null) { ... } type statements.

Under such a construct, an empty list is one where head == NIL && tail == NIL. This dramatically reduces the number of if (something == null) statements, but you still have one if statement to consider, when head is NIL (after deleting something) you need to set tail to NIL for consistency's sake.