CS 245 Homework 4

Due Date

4:00 pm Monday October 12

Assignment Name

sllist

File Names

sllist.c sllist.h

Below is a header file for a single linked list and an implementation file with no code for any of the functions.

You will write all of the functions using iteration. You may not add extra fields (like length or tail).

Turnin will compile your programs together with a test program, but you should write your own test program. To compile it, you can use:

          cc -Wall -o testsllist testsllist.c sllist.c

sllist.h

#ifndef SLLIST_H
#define SLLIST_H

// An sllist is a single linked list.
// array. The item type is void * so it can store pointers
// to items of any type.

typedef struct sllist sllist;


// Creates a new empty sllist.
// If memory allocation fails, returns NULL.
sllist *sllist_new();

// Frees the memory for list. Does not free any dynamically
// allocated memory for the items in list.
void sllist_free(sllist *list);

// Returns the length of list.
size_t sllist_length(sllist *list);

// Returns the item in list in position index which
// must be less than the length of list.
void *sllist_get(sllist *list, size_t index);

// Sets the value of the item in list in position
// index which must be less than the length of list.
void sllist_put(sllist *list, size_t index, void *value);

// Appends a new item to the end of list. Returns list. If
// memory allocation fails, leaves list unchanged and
// returns NULL.
sllist *sllist_append(sllist *list, void *value);

// Removes the item from list in position index
// which must be less than the length of list. Items
// to the right of position index are shifted left.
void sllist_remove(sllist *list, size_t index);

// Inserts an item into list at position index which
// must be less than or equal to the length of list.
// Items from position index to the right are shifted right.
sllist *sllist_insert(sllist *list, size_t index, void *value);

// Returns a dynamically allocated array containing
// (the pointers to) the items in list.
void **sllist_to_array(sllist *list);

// Returns an sllist containing (the pointers to) the items
// in array of size n.
sllist *sllist_new_from_array(int n, void *array[n]);

// Iterates over the items in list calling func on each item in list.
void sllist_iterate(sllist *list, void (*func)(void *));

#endif

sllist.c

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <assert.h>
#include "sllist.h"

typedef struct node {
  void *value;
  struct node *next;
};

struct sllist {
  struct node *head;
};

// Creates a new empty sllist.
// If memory allocation fails, returns NULL.
sllist *sllist_new();

// Frees the memory for list. Does not free any dynamically
// allocated memory for the items in liust.
void sllist_free(sllist *list);

// Returns the length of list.
size_t sllist_length(sllist *list);

// Returns the item in list in position index which
// must be less than the length of list.
void *sllist_get(sllist *list, size_t index);

// Sets the value of the item in list in position
// index which must be less than the length of list.
void sllist_put(sllist *list, size_t index, void *value);

// Appends a new item to the end of list. Returns list. If
// memory allocation fails, leaves list unchanged and
// returns NULL.
sllist *sllist_append(sllist *list, void *value);

// Removes the item from list in position index
// which must be less than the length of list. Items
// to the right of position index are shifted left.
void sllist_remove(sllist *list, size_t index);

// Inserts an item into list at position index which
// must be less than or equal to the length of list.
// Items from position index to the right are shifted right.
sllist *sllist_insert(sllist *list, size_t index, void *value);

// Returns a dynamically allocated array containing
// (the pointers to) the items in list.
void **sllist_to_array(sllist *list);

// Returns an sllist containing (the pointers to) the items
// in array of size n.
sllist *sllist_new_from_array(int n, void *array[n]);

// Iterates over the items in list calling func on each item in list.
void sllist_iterate(sllist *list, void (*func)(void *));

}