Solutions for those exercises.

Multiple Choices

1. Put a checkmark in the box corresponding to true statements about the List abstract data type.

   • A list contains an finite collection of elements, in a particular order.
   • A list cannot contain multiple elements with the same value.
   • A list must have a fixed number of elements.
   • A list is generally endowed with an operation to test for emptiness.
   • Only the element at the beginning of a list can be removed.

Exercises

1. Given the usual implementation of Cell and CList:

   public class CList<T>{
       private Cell first;
       private class Cell{
           public T Data { get; set; }
           public Cell Next { get; set; }
           public Cell(T dataP, Cell nextP){Data = dataP; Next = nextP;}
       }
       public CList(){first = null;}
   }

   Write…

   1. … a IsEmpty property that is true if the CList calling object is empty.

   2. … the AddF method that add a cell at the beginning of the CList (to the left).

   3. … a series of statements, to be inserted in a Main method, that a. create a CList object capable of containing char, b. insert the elements 'b' and '/' in it, c. displays whether it is empty using IsEmpty.

2. Briefly explain the purpose of the IsReadonly property from the ICollection<T> interface, and list at least two methods in a List implementation realizing ICollection<T> that should use it.

3. Explain the main differences between singly linked list and doubly linked list, and name a few methods that need to be implemented differently.

4. For what operation(s) does doubly linked list provide a complexity gain over singly linked list?