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.

2. Implementing a list as a doubly linked list (as opposed to singly linked list) allows to …

   • use fewer attributes.
   • keep track of the end of the list.
   • store more elements.
   • insert at the beginning of the list faster.

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. … a AddF method that takes an argument of type T and adds it at the beginning (“to the left”) of the CList calling object.

   3. … a RemoveL method that remove the value at the end (“to the right”) of the CList calling object and returns it.

   4. … 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.

   5. If the AddF and RemoveL were the only two methods to add to and to remove from the list, what would be the name of the data-structure we actually just implemented?

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?