10.3. Nondestructive Methods on Linked Lists

A nondestructive method on a linked list is one that does not change the list. A simple example is a method to compute the length of a linked list. We can use either a loop or recursion.

A recursive solution makes use of two facts.

1. An empty list has length 0.
2. The length of a nonempty list is one more than the length of its tail. For example, the length of [2,4,6,8] is one greater than the length of [4,6,8].

  static int length(List L)
  {
    if(isEmpty(L))
    {
      return 0;
    }
    else
    {
      return = 1 + length(tail(L));
    }
  }

A looping definition of length is based on the following table showing computation of length(L) where L = [2,4,6,8].

Notice that, at every line, length(L) = num + length(rest). That is, assertion

  length(L) = num + length(rest)

  static int length(List L)
  {
    int num = 0;
    for(List rest = L; !isEmpty(rest); rest = tail(rest))
    {
      num++;
    }
    return num;
  }

Membership test

---

Let's define method member(x,L), which returns true if x occurs in list L. For example, member(2, [2,4,6,8]) is true, but member(3, [2,4,6,8]) is false. This is an example of a search problem.

Let's start with a recursive definition. No number is a member of an empty list. A number x is a member of a nonempty list L just when either x is equal to the head of L or x is a member of the tail of L.

  static boolean member(int x, List L)
  {
    if(isEmpty(L))
    {
      return false;
    }
    else
    {
      return head(L) == x || member(x, tail(L));
    }
  }

A looping method looks at each member of the list, asking it is equal to x.

  static boolean member(int x, List L)
  {
    for(List rest = L; !isEmpty(rest); rest = tail(rest))
    {
      if(x == head(rest))
      {
        return true;
      }
    }
    return false;
  }

Selecting the even numbers in a list.

---

Let's write a method that takes a list L and returns a list of the even numbers in list L, in the same order as they occur in L. For example, evens([1,2,3,4,5,6] = [2,4,6].

Here is a thought process for defining evens(L).

1. If L is empty, then it does not contains any even numbers, so evens(L) = [ ].

2. If L begins with an odd number, then surely evens(L) = evens(tail(L)). For example, evens([1,2,3,4,5,6]) = evens([2,3,4,5,6]).

3. If L begins with an even number, then evens(L) is a list that begins with head(L), and evens(L) = head(L) : evens(tail(L)). For example,

     evens([2,3,4,5,6]) = 2 : [4,6]
                        = 2 : evens([3,4,5,6]).
   

   Replacing the : operator by the cons method, we see that evens(L) = cons(head(L), evens(tail(L))).

  static List evens(List L)
  {
    if(isEmpty(L))
    {
      return emptyList;
    }
    else if(head(L) % 2 == 0)
    {
      return cons(head(L), evens(tail(L)));
    }
    else
    {
      return evens(tail(L));
    }
  }

Exercises

---

1. Write a definition of static method copyList(L), which yields a copy of list L. (The copy is made of new list cells.)

   Answer

2. Write a definition of static method sum(L), where sum(L) returns the sum of all members of list L. For example, sum([2,3,4]) = 2 + 3 + 4 = 9. The sum of an empty list is 0. Answer

3. If L has length n, how long does it take to compute sum(L)? Use big-O notation to express the answer. Answer

4. Write a definition of static method smallest(L), which yields the smallest member of nonempty list L. For example, smallest([2,3,4]) = 2 and smallest([6,4,8,7]) = 4. Answer

5. Write a definition of static method prefix(L, n), which yields the length n prefix of list L. For example, prefix([2,4,6,8,10], 3) = [2,4,6]. If n is larger than the length of L then prefix(L, n) should return L. For example, prefix([2,4,6,8,10], 50) = [2,4,6,8,10]. Answer