I. Singly-Linked Lists
 A. motivation
------------------------------------------
           MOTIVATION FOR LISTS

For the contacts app in the homework
we limited the number of contacts. Why?




Could we ask the user how many contacts
they want to use?




So, we want








------------------------------------------
 B. lists
------------------------------------------
              LISTS

Idea:
   - Use
   
   - Each list node points to


   - Like the Lisp Lists we used in Python

   
------------------------------------------
  1. data structure (header file)
------------------------------------------
           DATA STRUCTURE

Idea:

  - Use NULL pointer to 


  - Use pointer to a struct to



// file list.h

#ifndef LIST_H
#define LIST_H 1
#include <stdlib.h>









/* ... declarations of list functions...*/
#endif
------------------------------------------
  2. operations on lists
------------------------------------------
        CREATION AND INITIALIZATION

// requires: malloc has enough space to allocate a new node
// ensures: result is a new node with first element val and tail tl
extern list list_cons(ELEM val, list tl) {






------------------------------------------
  3. accessors
------------------------------------------
       ACCESSOR FUNCTIONS

// ensures: result is true just when lst is an empty list
extern bool list_isEmpty(list lst) {



// requires: lst is not NULL
// ensures: result is the first element of lst
extern ELEM list_first(list lst) {





// requires: lst is not NULL
// ensures: result is the tail of lst
extern list list_tail(list lst) {





------------------------------------------
    Does list_isEmpty work for all kinds of lists?
    How would you write list_tail?
  4. mutators for nodes
------------------------------------------
         MUTATOR OPERATIONS

// requires: lst is not NULL
// effect: the element stored at the first node is changed to val
extern void list_set_first(list lst, ELEM val) {






// requires: lst is not NULL
// effect: the tail of the first node is changed to tl
extern void list_set_tail(list lst, list tl) {






------------------------------------------
    How would you write list_set_tail?
 C. error handling
------------------------------------------
          ERROR HANDLING

What should happen if NULL is passed
to list_first or list_tail?

Possibilities:
   - return

   - print an 
  
   - return

   - set

   - throw


------------------------------------------
   Why might aborting execution be bad?
   Why might returning a struct like that be problematic?
   Why might setting a global flag be problematic?
   Why might throwing exceptions be problematic?
II. Examples of Singly-Linked lists
 A. client code
  1. list_equal
------------------------------------------
          CLIENT CODE: LIST_EQUAL

Determine if two lists have the same elements
in the same order

// ensures: result is true just when
//          each element of lst1 is equal (==)
//          to the corresponding element of lst2.
extern bool list_equal(list lst1, list lst2) {


















------------------------------------------
    Can we write list_equal without using recursion?
  2. list_length
------------------------------------------
          FOR YOU TO DO

Implement the following function

// ensures: result is the number of elements in lst
extern int list_length(list lst);

(a) using recursion
(b) using a while loop













------------------------------------------
  3. list_sum
------------------------------------------
           FOR YOU TO DO

If ELEM is a numeric type we can write

// ensures: result is sum of the elements in lst
extern ELEM list_sum(list lst);

(a) using a while loop
(b) using a recursion








------------------------------------------
  4. list_copy
------------------------------------------
           FOR YOU TO DO

// ensures: result is copy of list,
//          which is equal to lst
//          but does not share storage with lst
extern list list_copy(list lst);

(a) using a while loop
(b) using a recursion








------------------------------------------
III. Friday Problems with Singly-linked Lists
 A. reverse
------------------------------------------
             FOR YOU TO DO

Using lists as in "list.h",
write a function list_reverse that reverses
the order of a list.

// modifies: lst
// effect: the order of elements in lst
//         is reversed from its original order
extern void list_reverse(list lst);

Do this:
(a) iteratively, with a loop
(b) recursively













------------------------------------------
 B. find
------------------------------------------
            FOR YOU TO DO
            
Using lists as in "list.h",
write a function list_find that
returns a pointer to the first node
containing a given element, or NULL
if the element is not in the list

// ensures: the order of elements in lst
//          is reversed from its original order
extern list list_find(list lst, ELEM sought);

Do this:
(a) iteratively, with a loop
(b) recursively


















------------------------------------------
 C. insert_after
------------------------------------------
            FOR YOU TO DO
            
Using lists as in "list.h",
write a function list_insert_after that
inserts a given element, what,
after the first node in lst containing sought,
or at the end of the list if sought
is not in the list

// effect: what is put into the list just after
//         the first occurrence of sought, if any,
//         or at the end if sought is not in the list
extern void list_insert_after(list lst, ELEM sought,
                              ELEM what);

Do this:
(a) iteratively, with a loop
(b) recursively


















------------------------------------------