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

Question

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.

Answer 1

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.

Answer 2

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.