CSC 161 Schedule Readings Labs & Projects Homework Deadlines Resources

List Array ADT

Summary
You will implement and test a novel data structure we call a List Array.
Objectives
  • Gain exposure to additional semantics for a list ADT
  • Practice implementing code to a given specification
  • Develop memory management skills
  • Reap the benefits of a memory error detector
  • Experience using parameterized preprocessor macros
  • Reinforce good unit testing habits

Introduction

Typically the list ADT is understood as a linearly indexed data structure supporting get and set operations with an add operation to insert new items at the end of the sequence.

So far we have seen how linked lists can easily support these operations, and clearly arrays can, too. Of course, with arrays, there is the complication that space may run out if the array is not big enough for all the add operations one may want to apply.

One common approach to this problem is to create a new, much larger array when space runs out, copy the old data to this array, and release the previous array. (Java's ArrayList and C++'s vector both use this strategy.) It may seem wasteful at first, but it turns out that the copying time amortizes well if the new array doubles in size.

Unfortunately, that analysis only applies when copying is cheap relative to time spent traversing memory. What if copies are expensive (slow)?

In this assignment, we will take a hybrid approach to expansion by constructing a list which holds arrays of increasingly larger sizes. The (conceptual) concatenation of all the arrays in the list would give rise to the linear index to the data in the collection.

Implementation Details

We will use the following structures to organize the collection's data. 

typedef struct node node_t;

struct node {
  data_t * array;
  unsigned int length;
  node_t * next;
};

typedef struct {
  node_t * first;
  unsigned int size;  
} listarray_t;

Note that data_t is not part of the C standard. Use of the code will require we also define this type somewhere before it is used, as follows. 

typedef int data_t;

Of course we need not necessarily store ints, we could just have easily have specified doubles, chars, or even potentially a struct like Picture or a pointer like float *. (However, a struct would require us to rethink our approach to the function contains, which relies on the == operator that cannot be used to compare structures.)

In any case, the definitions above give rise to a structure that we can conceptually visualize in the figure below.

Memory organization for a list array
Conceptual organization of memory and pointers for a list array.

The operations your listarray_t will need to support are given in the accompanying listarray.h header and include new, size, add, get, set, contains, and clear.

While your listarray.c implementation will naturally contain these operations, you can greatly simplify several of them with an additional helper function that either returns the address of the data_t item at a particular index or else returns (via a handle) the address of the last node_t in the list, (i.e., for when the index is the list size and the last node's array is full; this bookkeeping avoids an additional traversal to attach a new node.) 

/* Get pointer to data at specified index 
 * Precondition:
 *  index <= size(list) [Note: equality allowed for add() function]
 * Postcondition:
 *  returns address of data item or NULL
 *  if returns NULL and last is not NULL, changes last to point to last node
 * [PRIVATE METHOD] */
data_t *
get_ptr (listarray_t * list, unsigned int index, node_t ** last);

Expansion Behavior

The first node—allocated when new (unsigned int capacity) is called—should contain a array length capacity, but the list's size should be zero, because nothing has yet been added. We put array in quotes because you must use malloc to create a block of memory with the appropriate size; the node will then contain a pointer to that block of memory, which will function as the array in the node.

When the add method is called, the size of the list should increase and the data item should be stored at the next available index (as determined by the list size) in the last node's array.

When there is no such available index (i.e., because the last node's array is full), a new node should be added to the list with an array that is double the size of the previous node's array.

Thus, if the initial capacity is 10, the nodes in the list would have arrays of lengths 10, 20, 40, 80, etc, as add is invoked to necessitate the space.

Testing

Because you're implementing an outright data structure, testing is more straightforward. For this assignment, you can use the handy testing macro from the C Preprocessor Lab, as demonstrated the testing program skeleton below.

test_listarray.c
#include <stdbool.h>
#include <stdio.h>

#include "listarray.h"

#define TEST(EXP,RESULT) if (EXP != RESULT) { ++errors; printf ("  Error for: %s\n", #EXP);}

/* Test collection example */
void
testExample (void)
{
  printf("--EXAMPLE TEST--\n");

  int errors = 0;
  
  listarray_t * list = new (5);

  TEST( size (list),   0 );   // list is empty
  TEST( add (list,42), true); // added item
  TEST( size (list),   1 );   // list is appropriate size
  TEST( get (list,0),  42);   // check item was added / indexable

  clear(list);
  printf ("Done: errors = %d\n", errors);
} // testExample


/* Test all methods for a single node (no expansions) */
void
testBasic (void)
{
  printf("--BASIC TESTS--\n");
  
  const unsigned int CAPACITY = 10;
  int errors = 0;
 
  listarray_t * list = new (CAPACITY);

  TEST( size(list), 0 );        // initial list is empty

  int i; // index for all loops
  
  /* Test add (successful), size (incremented), and get (new item) */
  for (i=0 ; i<CAPACITY ; i++) {
    TEST( add (list,i), true);  // added item i
    TEST( size (list),  i+1 );  // list is appropriate size
    TEST( get (list,i), i);     // check index i is item i
  }

  /* Test contains (true and false) at all locations*/
  for (i=0 ; i< 2*CAPACITY ; i++) {
    TEST( contains (list,i), i<CAPACITY); // list contains item
  }

  /* Test set (return), size (same), and get (new value) */
  for ( i=0 ; i<CAPACITY ; i++) {
    TEST( set (list, i, i + CAPACITY), i);
    TEST( size (list), CAPACITY ) ;
    TEST( get (list,i), i + CAPACITY); 
  }

  clear (list); // should run without memory errors
  
  printf ("Done: errors = %d\n", errors);
} // testBasic


/* Driver program for test suite */
int
main (void)
{
  testExample();
  testBasic();
  // Add more test collections here
} // main

You should expand this program to include a complete set of tests.

Important Reminders

Specific Requirements

Grading

In addition to the general grading guidelines for evaluation, the assignment is worth 30 points.

A five point penalty will apply to any submission that includes personally identifying information anywhere other than the references/honesty file.

Creative Commons License Copyright © 2017 Jerod Weinman. This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 4.0 International license.
Validate HTML