top

COMP 202: Principles of Object-Oriented Programming II

← Review of List Processing →

Home — Fall 2008

Today's Menu:

Processing the immutable list vs. Processing the mutable list

Immutable List Processing vs. Mutable List Processing

In list processing, whether or not the list is mutable, we must always consider two cases:

empty list
non-empty list.

Both list frameworks enforce this approach. In the non-empty case, we should only see the list in question in terms of its first and rest, and process rest as another list. This naturally leads to recursive algorithms.

When processing an immutable list, there are times we will need to construct new lists, while processing mutable lists, in many situations, we will want to mutate the original list to obtain the desired results. We will examine a few examples to illustrate the differences between the two kinds of lists.

Reversing a list

IList (Immutable List)	LRStruct (Mutable list)
// Creates and return a new list that is the reverse // of the given host list public class RevIList implements IListAlgo {	// Reverses the given host list public class RevLRS implements IAlgo {
// empty case: in class exercise public Object emptyCase(IMTList h, Object... p) { }	// empty case: in class exercise public Object emptyCase(LRStruct h, Object... p) { }
// non-empty case: in class exercise // Hint: use anonymous helper public Object nonEmptyCase(INEList h, Object... p) { } }	// non-empty case: in class exercise // Hint: use anonymous helper public Object nonEmptyCase(LRStruct h, Object... p) { } }

Appending a list to another list

IList (Immutable List)	LRStruct (Mutable list)
// Creates and return a new list that is the concatenation // of the given host list and the input list. public class AppendIList implements IListAlgo {	// Concatenate the input list to the end of the given host list public class AppendLRS implements IAlgo {
// empty case: in class exercise public Object emptyCase(IMTList h, Object... p) { }	// empty case: in class exercise public Object emptyCase(LRStruct h, Object... p) { }
// non-empty case: in class exercise // Hint: use anonymous helper public Object nonEmptyCase(INEList h, Object... p) { } }	// non-empty case: in class exercise // Hint: use anonymous helper public Object nonEmptyCase(LRStruct h, Object... p) { } }

Download the IList framework and the LRStruct framework.

← Review of List Processing →