Index

## 1. Building on Lists

• we will look at how our slist class can be extended to include
• length , reverse methods
• use recursion and functional programming where appropriate
• we will notice a problem with C++ when applying this technique

## 2. Tutorial answers: length

• firstly we add two helper methods to our class slist
• c++/lists/single-list/int/slist.h

```...
private:
element *e_tail (element *l);
int *e_length (element *l);
...```

## 3. e_tail

• c++/lists/single-list/int/slist.cc

```/*
*  e_tail - given a list, l, return the list without the
*           pre-condition:   non empty list.
*           post-condition:  return the list without the
*                            first element.
*                            The original list is unaltered.
*/

element *slist::e_tail (element *l)
{
return l->next;
}```

• c++/lists/single-list/int/slist.cc

```/*
*  e_length - return the length of element list, l.
*/

int slist::e_length (element *h)
{
if (h == 0)
return 0;
else
return (1 + e_length (e_tail (h)));
}```

• c++/lists/single-list/int/slist.cc

```/*
*  length - return the length of list, l.
*/

int slist::length (void)
{
}```

## 4. reverse

• must return the list with its contents reversed
• not a new list with a copy of the contents reversed!
• c++/lists/single-list/int/slist.cc

```slist slist::reverse (void)
{
if (is_empty ())
return *this;
else
return tail ().reverse().cons (empty().cons (head ()));
}```

• notice the use of recursion
• notice that tail removes and deletes a datum
• head obtains the first element
• cons appends the first element to an empty list
• ie creates a list with one element
• this single element list is added to the end of the reversed list
• the reversed list comes from the tail of the original list

## 5. cons (slist l)

• c++/lists/single-list/int/slist.cc

```/*
*  cons - concatenate list, l, to the end of the current list.
*         pre-condition :  none.
*         post-condition:  returns the current list with a copy of
*                          contents of list, l, appended.
*/

slist slist::cons (slist l)
{
if (l.is_empty ())
return *this;
else
return cons (duplicate_elements (l.head_element));
}```

## 6. Recursive version of cons (slist l)

• c++/lists/single-list/int/slist.cc

```/*
*  cons - concatenate list, l, to the end of the current list.
*         pre-condition :  none.
*         post-condition:  returns the current list with a copy of
*                          contents of list, l, appended.
*/

slist slist::cons (slist l)
{
if (l.is_empty ())
return *this;
else
{
int h = l.head ();  // use h to force evaluation order
return cons (h).cons (l.tail ());
}
}```

• notice the gotya
• we must use a temporary variable h to contain an intermediate result containing the result of l.head()
• it ensure that the call to head occurs before l.tail()
• if the code were re-written as:

• c++/lists/single-list/int/slist.cc

```slist slist::cons (slist l)
{
if (l.is_empty ())
return *this;
else
return cons (l.head()).cons (l.tail ());
}```

• it would fail, as l.tail() is executed before l.head()

## 7. Further tutorial questions

• write some test code to generate a large list and perform reverse on the list several times
• compare the execution time between the iterative and recursive solutions
• which is faster, why?
• hint use -pg flags to g++ and analyse the execution time with gprof
• see week 1 notes for further hints on using the compiler
• enable debugging in the slist.cc file and watch for the addresses of the new elements created and deleted
• when reverse is called - how many new elements are created when the
• recursive version is run
• when the iterative version is run

## Index

1. Building on Lists
2. Tutorial answers: length
3. e_tail
4. reverse
5. cons (slist l)
6. Recursive version of cons (slist l)
7. Further tutorial questions
Index

This document was produced using groff-1.22.