CSE 428: Solutions of
exercises on abstract data types and
The superscript "(d)" stands for "difficult".
Exercises similar to those marked with "(d)"
might appear in
candidacy exams, but not in the standard exams of CSE 428.
Consider the implementation of the ADT "simple list"
seen in Lecture 10 (CSE 428 Spring 99, see
Assume that the data are somehow protected, so that it is
possible to access to lists only via the operations of the ADT.
- Is it possible to create "circular lists", i.e. lists in which
it is possible, following the links from an element, to come back to the
- Is it possible to create "shared lists", i.e.
lists which have a part in common?
- Is it possible that an operation done on a list affects
- It's not possible to create circular lists.
In fact, lists are created by the function
"emptylist", which returns a null pointer, and
are expanded by the function "cons",
which adds a new element on the front and returns the pointer to this
(newly allocated) element. Of course, this pointer could not be used before
being created, hence it could not have been
mentioned in previous operations on the
- Is it possible to create "shared lists". For instance,
the following two instructions create two lists, L1 and L2,
which share the same tail (L).
L1 := cons(1,L) ; L2 := cons(2,L)
Note that if two lists have a common sublist, it is always
the final part in both of them.
- Is it possible
that a modification done on a list has a side effect
on another list.
In fact, if L1 and L2 are created with
the two commands above,
then the application of "tail" two times
on L1 (i.e. "tail(tail(L1))")
would deallocate the first element of L and leave dangling the
pointer in the field "next" of the first element of L2.
On the other hand, this is the only case of side-effect.
If we modify the definition of "tail" by eliminating the instruction
"dispose", then the implementation of the "simple lists" becomes "pure", i.e.
no side-effects would be possible with the operations of the ADT.
Suppose that the above implementation of "simple lists"
is done in a language like Pascal Standard or C, which do not
offer a mechanism for data protection.
- Would the creation of
circular lists, shared lists and side effects be possible?
- Would it be possible to create lists with multiple links
in their elements,
for instance tree-like structures or two-dimentional structures?
- All of the above would be possible without data protection.
In fact, nothing would prevent to access the elements via the usual
operations on records.
Thus for instance we could create a circular list
with a command of the form
L^.next := L
We could also have different forms of side-effects. For instance,
if we create L1 and L2 like above, with the commands:
L1 := cons(1,L) ; L2 := cons(2,L)
and then we perform the command
L1^.next^.info := L1^.next^.info + 1
this would modify also the content of the field "info" of the
second element of L2.
- In the given implementation it
would not be possible to create lists containing
elements with multiple links, since this would violate
the type declared for the element of a list
(a record with only one field of type pointer).
Note that Pascal would allow for a different implementation of
lists, using variant records, were the number of links in an element
Describe briefly the advantages of having a mechanism for data protection.
The main advantages are
(I have listed here the main advantages I know of,
maybe there are other advantages too.)
- Independence from implementation of the ADT:
Even if the implementation of the ADT will change,
the programs which use the ADT need not to change.
- Preservation of the properties of the ADT described
in the specification.
This would be useful to study the correcteness of the program,
i.e. to ensure that the program gives the expected results.
What are the mechanism offered in Modula 2 and in C++
for data protection?
- In Modula 2 we have the possibility of encapsulating an
ADT in a "module" specification. Such specification
includes the declaration of the set of operations
that can be performed on the elements of the
ADT being defined (interface).
The elements of the ADT cannot be accessed
(externally to the module) in
any other way.
- In C++ we have the possibility of encapsulating an
ADT in a "class" specification.
For each member of the class, it is
possible to declare whether the member is "public", "protected", or "private".
Externally to the class, we cannot use the private and the protected
(unless we are in a friend class, or we are
in a subclass and the member is protected).