10.1.7. Destructive Functions on Linked Lists

Destructive functions

---

A destructive function on a linked list changes the list, either by changing the items in the list cells or by changing the next pointers (or both). You almost certainly want to avoid memory sharing when you are using destructive functions, since otherwise changing one list might implicitly change another one that shares cells with the one you change.

Pointer variables

---

If a destructive function wants to change a pointer then the pointer must be a variable. That presents a problem if we use the tail function. If L is a linked list then tail(L) has type ListCell*, but it is not a variable. Hence, it cannot be used as a parameter that is call-by-reference.

To avoid this problem, we will avoid the tail function. Instead of writing tail(L), we write L->next;

Example: insert a value into a sorted linked list

---

Imagine that you have a linked list L that is in nondescending order. For example, list [2,4,4,5,9] is in nondescending order, but [2,4,3] is not. You would like to insert a value into this list, changing the list, and preserving the fact that it is in nondescending order. For example, if L is [2,4,4,5,9] and you insert 7, you get [2,4,4,5,7,9].

This function needs to be able to change pointers in L so that it can insert a new cell. So L needs to be passed by reference. There are three cases to consider to insert x into L.

1. If L is an empty list, just change L to [x].

2. If L is not empty and its head is greater than or equal to x, change L to x:L, adding x to the beginning of the list. For example, if x is 2 and L is [4,6,8], change L to be [2,4,6,8].

3. If L is not empty and its head is less than x then insert x into the tail of L. The change in pointers in the tail of L will affect L.

  void insert(int x, List& L)
  {
    if(isEmpty(L))
    {
      L = cons(x, emptyList);
    }
    else if(x <= head(L))
    {
      L = cons(x, L);
    }
    else
    {
      insert(x, L->next));
    }
  }

  L = cons(x, L);

  void insert(int x, List& L)
  {
    if(isEmpty(L) || x <= head(L))
    {
      L = cons(x, L);
    }
    else
    {
      insert(x, L->next);
    }
  }

Example: Remove a value from a list

---

Suppose that remove(x, L) is intended to be a destructive function that removes the first occurrence of x from list L, or does nothing if x does not occur in L. For example, if L is [2,4,2,4,5] and you perform remove(4, L), then L is changed to [2,2,4,5]. The cases are as follows.

1. If L is empty, do nothing, since x obviously does not occur in L.

2. If L is nonempty and the head of L is equal to x, then set L to its tail. However, the cell that contains x is presumably no longer needed. (We are not using memory sharing, so this cell only belongs to one list, L.) So it should be deleted.

3. If L is not empty and its head is not equal to x, then remove x from the tail of L.

  void remove(int x, List& L)
  {
    if(!isEmpty(L))
    {
      if(head(L) == x)
      {
        List p = L;
        L = L->next;
        delete p;
      }
      else
      {
        remove(x, L->next))
      }
    }
  }

Example: Modify the items in a list

---

Suppose that you want doubleAll(L) to modify the items in list L by doubling each. For example, if L is [1,3,5], then after doing doubleAll(L), L will contain [2,6,10]. The cases are simple.

1. If L is empty there is nothing to do.

2. if L is not empty then double its head and call doubleAll on its tail. Notice that, to double the head of L, you must change variable L->item. Expression head(L) returns an integer, not an integer variable. So we write L->item for the variable name.

  void doubleAll(List L)
  {
    if(!isEmpty(L))
    {
      L->item = 2 * L->item;
      doubleAll(L->next);
    }
  }

Exercises

---

1. Write a C++ definition of function removeAll(x, L), which removes all occurrences of x from list L. Answer

2. Write a C++ definition of function addToEnd(x, L), which adds x to the end of list L. Answer

3. If L has length n, how much time does it take to perform addToEnd(x, L)? Use big-Θ notation to express the answer. Answer

4. Write a C++ definition of function addToStart(x, L) that adds x to the beginning of list L. If L has length n, how long does it take to perform addToStart(x, L)? Answer

5. Write a C++ definition of function destroy(L), which deletes every cell in list L. Answer

6. One way to sort a linked list L is to start with an empty list R and successively add each member of L to R, using function insert defined above. Write a function that sorts a linked list into nondescending order using this idea. Answer

7. Is the definition of doubleAll tail-recursive? Answer