Laboratory: Lists

Summary:

Prerequisites: Familiarity with pointers, linked lists, malloc, and more.

• Preparation
• Exercises
  • Exercise 1: Setting Elements
  • Exercise 2: Inserting Elements
  • Exercise 3: Deleting Elements
  • Exercise 4: Deleting Elements, Revisited

Preparation

a. Create a new directory for this lab. I would suggest something like CSC161/Labs/Lists.

b. Make a copy of Examples/Lists/lists.tar.

c. Unpack that tarball in your directory.

d. Review the list.h file to make sure you understand which functions the list library should provide.

e. Review the implementations of list_get (provided) and list_index_of (written in class).

Exercises

Exercise 1: Setting Elements

An important list operation is list_set(lst, n, val), which sets the nth element of lst to val.

a. Review the documentation for list_set so that you know what it should do.

b. Write some simple unit tests for list_set. For example, you might create a four element list of the word "Bravo" set the second element to "Beta", and make sure that the second element is "Beta" but the rest remain "Bravo".

c. Write some simple experiments for list_set. You might create a four element list of the word "Bravo" and set the second element ot "Beta"

d. Implement list_set.

Exercise 2: Inserting Elements

a. Review the documentation for list_insert so that you know what it should do.

b. Write some simple unit tests for list_insert.

c. Write some simple experiments for list_insert.

d. Implement list_insert.

Exercise 3: Deleting Elements

a. Review the documentation for list_delete so that you know what it should do.

b. Review the implementation of list_cut so that you are comfortable with the strategy for removing elements from a list.

c. Write some simple unit tests for list_delete.

d. Write some simple experiments for list_delete.

e. Implement list_delete.

Exercise 4: Deleting Elements, Revisited

There are two common strategies for implementing list_delete. One might delete a element by finding its index and using list_cut. One might delete an element by iterating through the list until one finds the element.

Pick whichever of these stratedy you did not use for the previous exercise and implement list_delete using that strategy.