The Algorithm Design Manual Second Edition

Deletion From a List

Deletion from a linked list is somewhat more complicated. First, we must find a

pointer to the predecessor of the item to be deleted. We do this recursively:

copies p to the place pointed to by l, which is the external variable maintaining

access to the head of the list.

---

70

3 .

D A T A S T R U C T U R E S

list *predecessor_list(list *l, item_type x)

{

if ((l == NULL) || (l->next == NULL)) {

return(NULL);

}

if ((l->next)->item == x)

return(l);

else

return( predecessor_list(l->next, x) );

}

The predecessor is needed because it points to the doomed node, so its next

pointer must be changed. The actual deletion operation is simple, once ruling out

the case that the to-be-deleted element does not exist. Special care must be taken

to reset the pointer to the head of the list (l) when the first element is deleted:

delete_list(list **l, item_type x)

{

list *p;

/* item pointer */

list *pred;

/* predecessor pointer */

list *search_list(), *predecessor_list();

p = search_list(*l,x);

if (p != NULL) {

pred = predecessor_list(*l,x);

*l = p->next;

else

pred->next = p->next;

free(p);

/* free memory used by node */

}

}

C language requires explicit deallocation of memory, so we must free the

deleted node after we are finished with it to return the memory to the system.