Deleting from a Linked List

Linked List example:
Here, we will discuss deleting an element with a specific value from a linked list.
Here are some constraints for our example:
1. The list holds char's.
2. Deletion can occur anywhere in the list.
3. The delete operation will not return the element that we delete, it only need remove it from the list.
Now, recall the basic structure of a singly-linked list:
```
list
 |
 v
---------     ---------     ---------
| a | --+---> | b | --+---> | c | 0 |
---------     ---------     ---------
```
In other words, there is a node for each element, where nodes consist of a part in which the element is stored and a link to the next node. The last node links to nothing (i.e., there are no nodes after it). Also, there is a link to the beginning of the list.
What do these links correspond to in C?
Answer: Pointers!

We'll consider our elements and nodes to have the following types:
```
typedef char elementT;

...

typedef struct nodeTag {
  elementT element;
  struct nodeTag *next;
} nodeT;
```
and thus, the pointer to the beginning of the list will be:
```
nodeT *list;
```
Aside: Although list is a pointer, we won't use the convention of naming it "listP". That's because we want to be abstract about what "list" is. I.e., users of the list don't really care whether it is implemented as a linked list or array or whatever--when they want to access a list, they just call list functions on this variable.

When the list is empty, what value will the pointer to the beginning have?
Answer: There are no nodes to point to, so it will be NULL!
Different cases:
There are a few steps to deleting a specific element from the list:
1. Find the node with the element (if it exists).
2. Remove that node.
3. Reconnect the linked list.
4. Update the link to the beginning (if necessary).
The order in which we perform these steps will depend on how we implement the deletion operation.

Note: For simplicity, if there are two elements with the value we want, we'll just remove the first one.

Finding the node in question is a matter of traversing the list and looking at each node's element.
Reconnecting the list once a node is to be removed is more interesting. Let's consider at least 3 cases:
- Removing a node from the beginning.
- Removing a node from the middle.
- Removing a node from the end.
Removing from the beginning
When removing the node at the beginning of the list, there is no relinking of nodes to be performed, since the first node has no preceding node. For example, removing node with a:
```
list
 |
 v
---------     ---------     ---------
| a | --+---> | b | --+---> | c | 0 |
---------     ---------     ---------
```
However, we must fix the pointer to the beginning of the list:
```
list
 |
 +-------------+
               |
               v
---------     ---------     ---------
| a | --+---> | b | --+---> | c | 0 |
---------     ---------     ---------
```
Removing from the middle
Removing a node from the middle requires that the preceding node skips over the node being removed. For example, removing the node with b:
```
list
 |
 v
---------     ---------     ---------
| a | --+--+  | b | --+---> | c | 0 |
---------  |  ---------     ---------
           |                ^
           +----------------+
```
This means that we need some way to refer to the node before the one we want to remove.
Removing from the end
Removing a node from the end requires that the preceding node becomes the new end of the list (i.e., points to nothing after it). For example, removing the node with c:
```
list
 |
 v
---------     ---------     ---------
| a | --+---> | b | 0 |     | c | 0 |
---------     ---------     ---------
```
Note that the last two cases (middle and end) can be combined by saying that "the node preceding the one to be removed must point where the one to be removed does."

IMPORTANT NOTE: When there is only one node, and it is the one to be removed, are we in the case of removing at the beginning or end?! We should make sure that one of these cases handles removing this single node ELSE we should create a new case.

What we've learned from these pictures is that when we find the node we want to remove, we need some kind of reference to the node preceding it OR some way to backtrack to that node.
In addition, since we need to fix the pointer to the beginning of the list, we'll need some way to get the new beginning pointer out of the function. One way to do so (and the one we'll initially use) is to return the pointer from the deletion function. This means we will have a deletion function as follows:
```
nodeT *ListDelete(nodeT *list, elementT value);
```
and use it as:
```
list = ListDelete(list, value);
```
Recursive implementation:
One way to implement a deletion function is with recursion (since recursion gives us backtracking). Remember that for a recursive function (i.e., a function that calls itself), we need to decide:
- Base case(s): when to stop recursing.
- Recursive part(s): how function will call itself to solve the problem.
The base cases are fairly easy, since we need to stop recursing when:
- We find the matching value.
- We search the whole list and don't find a matching value.
To determine what should be the recursive part of the function, we should consider 2 tasks required of this function:
1. Finding the one to remove.
  How will we search the list for the element? Well, the list will be passed as a pointer to a node (recall the prototype--here we've renamed the pointer to currP):
```
nodeT *ListDelete(nodeT *currP, elementT value);
```
  So, if we decide that the node pointed to by currP is not the right node, then we just recurse to examine the next node:
```
ListDelete(currP->next, value);
```
  and so on, until all nodes have been examined.
  Note: Arrow (->), of course, is the syntax to use when you want to access a field in a structure using a pointer (like currP) to that structure.
2. Relink the list.
  When we remove a node, the previous node has to skip over the removed node. A way to achieve this with recursion is through pointer reassignment.
  Consider the following, where the current call to ListDelete() gets a pointer to the node with x:
```
1. ListDelete(pointer-to-node-with-x, 'y');

---------     ---------     ---------
| x | --+---> | y | --+---> | z | --+--->
---------     ---------     ---------
  ^
  |
currP (in 1.)
```
  Since x is NOT the thing to be removed, another recursive call is made. This next recursive call is going to access the node with y:
```
1. ListDelete(pointer-to-node-with-x, 'y');
2.   ListDelete(pointer-to-node-with-y, 'y');

---------     ---------     ---------
| x | --+---> | y | --+---> | z | --+--->
---------     ---------     ---------
  ^             ^
  |             |
currP (in 1.)  currP (in 2.)
```
  Remember that when the recursive call on the node with y (call 2) is done, we'll be back to the call on the node with x (i.e., we backtrack to call 1):
```
1. ListDelete(pointer-to-node-with-x, 'y');
2.   call 2 done, back to 1.

---------     ---------     ---------
| x | --+---> | y | --+---> | z | --+--->
---------     ---------     ---------
  ^
  |
currP (in 1.)
```
  Now since y is the thing to be removed...
  If there was some way that this function call on the node with y (call 2) could tell us the node with y was removed and that it pointed to the node with z, then we could fix the node with x, having it skip over y (to z).
  Well, it can!! Remember that each recursive call returns a pointer to a node!
  Thus, what we'll do is have each recursive call return a pointer to the node to which the previous node should point. Thus, when the node is left alone, we just return a pointer to itself (i.e., "Don't skip over me!"). When the node is removed, we return a pointer to the next node (i.e., "Skip over me!").
  So, we use the return value of the recursive call as:
```
currP->next = ListDelete(currP->next, value);
```
  When the next node is not removed, this pointer reassignment is equivalent to if we had done:
```
currP->next = currP->next;
```
  i.e., no change. However, if the next node is the one to be removed, it would be like we had done:
```
currP->next = currP->next->next;
```
  and thus, skips over the removed node.
  
  Note: This also works for removing the first node (i.e., it fixes the pointer to the beginning of the list), since the initial call to the function is:
```
list = ListDelete(list, value);
```
Again, to complete the function, all the things we'll have to do are:
- Determine when we hit the end of the list.
- Determine when we've found the right node.
- Deallocate the correct node.
- Return what the link in the previous call should point to.
Finally, our whole recursive function looks like (we named the pointer currP since it will traverse the list instead of just pointing to the beginning):
```
nodeT *ListDelete(nodeT *currP, elementT value)
{
  /* See if we are at end of list. */
  if (currP == NULL)
    return NULL;

  /*
   * Check to see if current node is one
   * to be deleted.
   */
  if (currP->element == value) {
    nodeT *tempNextP;

    /* Save the next pointer in the node. */
    tempNextP = currP->next;

    /* Deallocate the node. */
    free(currP);

    /*
     * Return the NEW pointer to where we
     * were called from.  I.e., the pointer
     * the previous call will use to "skip
     * over" the removed node.
     */
    return tempNextP;
  }

  /*
   * Check the rest of the list, fixing the next
   * pointer in case the next node is the one
   * removed.
   */
  currP->next = ListDelete(currP->next, value);


  /*
   * Return the pointer to where we were called
   * from.  Since we did not remove this node it
   * will be the same.
   */
  return currP;
}
```
This recursive implementation even works when we try to delete from an empty list (i.e., there are no nodes).

As mentioned, the initial call to this function will be:
```
list = ListDelete(list, value);
```
which will make sure that the pointer to the beginning gets fixed if we remove the first node.
Iterative implementation:
Now that we've seen how to delete a node using recursion, let's look at how to do the same thing iteratively (i.e., with a loop).
Again, we'll need to be able to change the pointer to the list, i.e., list, in the case that the first node in the list is removed. However, instead of passing back a new value for the beginning of the list via the return mechanism, as in:
```
list = ListDelete(list, value);
```
we'll pass in the pointer to the beginning of the list by reference (as a pointer to a pointer), so that we can change it in ListDelete() when necessary. Thus, the prototype for our function will be:
```
void ListDelete(nodeT **listP, elementT value);
```
Note: This time, we pass the address of the "list" variable to the function, so it makes sense to call the parameter that receives that address "listP", since it is a pointer to a "list".

Before, we used recursion to search through the list, but now we will interate (i.e., loop) through it. It's easy to see how to start a pointer at the beginning and move it from one node to the next:
```
---------     ---------     ---------
| x | --+---> | y | --+---> | z | --+--->
---------     ---------     ---------
  ^
  |
 currP
```
In other words:
- Start at the beginning:
```
currP = *listP
```
  Note that to access the address of the first node, we have to dereference listP with the star (*) since listP is a "pointer to a pointer to the first node" (and we want to remove one level of pointer-ness to get the "pointer to the first node").
- Advance to the next node when necessary:
```
currP = currP->next
```
- Stop when there are no more nodes, i.e., make sure that:
```
currP != NULL
```
It's easy to combine these into a for loop:
```
for (currP = *listP; currP != NULL; currP = currP->next) {
  ...
```
However, when we find the one to remove, we'll also need a pointer to the previous node:
```
---------     ---------     ---------
| x | --+---> | y | --+---> | z | --+--->
---------     ---------     ---------
  ^            ^
  |            |
 prevP        currP
```
Thus, we also need to maintain a previous pointer at each step of the loop:
```
for (currP = *listP;
      currP != NULL;
      prevP = currP, currP = currP->next) {
```
(Notice that there are 2 increments separated by a comma.)

To complete the function, we'll have to:
- Have some way to indicate when there is no previous node.
  Remember that removing the first node is a special case because...
  - It requires no relinking of nodes.
  - We have to update the pointer to the beginning of the list. We don't have to return the new pointer to the beginning (in case it was changed) since we have direct access to it in the function (via listP).
- Relink the list (i.e., skip over the node to be deleted).
- Remove the node.
One implementation of this function might be:
```
void ListDelete(nodeT **listP, elementT value)
{
  nodeT *currP, *prevP;

  /* For 1st node, indicate there is no previous. */
  prevP = NULL;

  /*
   * Visit each node, maintaining a pointer to
   * the previous node we just visited.
   */
  for (currP = *listP;
	currP != NULL;
	prevP = currP, currP = currP->next) {

    if (currP->element == value) {  /* Found it. */
      if (prevP == NULL) {
        /* Fix beginning pointer. */
        *listP = currP->next;
      } else {
        /*
         * Fix previous node's next to
         * skip over the removed node.
         */
        prevP->next = currP->next;
      }

      /* Deallocate the node. */
      free(currP);

      /* Done searching. */
      return;
    }
  }
}
```
We do handle the situation of removing the first node, i.e., when there is no previous. See how we use a previous pointer value of NULL to indicate this and do the right thing.
Does this function handle deletions from empty lists correctly?

Finally, this function will be called as:
```
ListDelete(&list, value);
```
Note that the address of the list must be passed.

Deleting from a Linked List

Removing from the beginning

Removing from the middle

Removing from the end