In Example 5.15, we gave a recursive definition of a linked list. Here’s a variant of that definition, where we insist that the elements be in increasing order. Define a nonempty sorted list as one of...

In Example 5.15, we gave a recursive definition of a linked list. Here’s a variant of that definition, where we insist that the elements be in increasing order. Define a nonempty sorted list as one of the following

1. hx,hii; or

2. hx,hy, Lii where x ≤ y and hy, Li is a nonempty sorted list.

Prove by structural induction that in a nonempty sorted list hx, Li, every element z in L satisfies z ≥ x. A string of balanced parentheses (with a close parenthesis that matches every open parenthesis, and appears to its right) is one of the following:

1. the empty string (consisting of zero characters);

2. a string [ S ] where S is a string of balanced parentheses; or

3. a string S1S2 where S1 and S2 are both strings of balanced parentheses