Chapter Exercises

Define the following terms: linked list, node, head reference, external reference.

Why must a linked list contain at least one external reference, namely the head reference?

How is an empty list represented?

Why is a second external reference needed when removing a node from a linked list?

What advantage does the use of a tail reference provide?

In terms of storage space, what advantage(s) does a singly linked list provide over a vector? What about the disadvantage(s)?

Given a head reference to a singly linked list that contains integer values, implement a function that accepts the head reference and returns the smallest value or None if the list is empty.

Implement the following functions related to the singly linked list:

1. The removaAll(head) function, which accepts a head reference to a singly linked list, unlinks and remove every node individually from the list.

Evaluate the following code segment which creates a singly linked list. Draw the resulting list, including the external references.

Consider the following singly linked list. Provide the instructions to insert the new node immediately following the node containing 52. Do not use a loop or any additional external references.

Consider the following singly linked list. Provide the instructions to remove the node containing 18. Do not use a loop or any additional external references.

The following questions are related to the Sparse Matrix ADT.

1. Implement the remaining methods of the Sparse Matrix class presented in the chapter using the array of sorted linked lists: __getitem__, transpose, __sub__, and __mul__.
2. Determine the time-complexity for each of the SparseMatrix methods implemented in part (a).
3. Prove or show that the matrix addition operation of the SparseMatrix class, as implemented in the chapter using an array of sorted linked lists, has a worst case run time of $\text{O}\left(kn\right)$.
4. As you proved in part (c), the implementation of the SparseMatrix __add__ method presented in the chapter is $\text{O}\left(kn\right)$. A more efficient implementation is possible without the use of the __getitem__ and

   __setitem__ methods. Design and implement a new version of the __add__ method that has a run time of no more than $\text{O}\left(k\right)$.

5. Show that your implementation of the __add__ method from part(d) has a worst case run time of $\text{O}\left(k\right)$.
6. What advantages are there to using sorted linked lists with the Sparse Matrix ADT instead of unsorted linked lists?