Princeton University
COS 217: Introduction to Programming System

Precept 6: A List ADT

Purpose

(1) Help you to learn/review advanced C programming

(2) Help you with Assignment 2

(3) Help you learn more about ADTs in C (and thus support lectures)

Reading

Hanson, Chapter 7

Approach

Study a series of List ADTs

Each version reflects different design decisions

Why List?

(1) Illustrates structure declarations, typedefs, void pointers, opaque pointers, function pointers, pointer manipulation, dynamic memory management

(2) Can serve as a model for your work on Assignment 2

(3) Illustrates a real-world ADT

Void Pointers

Can point to data of any type

Escape hatch out of C typing system

See example: voidpointers.c

void* is very different from void (should be different keywords):

void f(int x) {...} -- f returns nothing

void *f(int x) {...} -- f returns a pointer; we decline to tell the compiler what type of data that pointer is pointing to

Good: List can contain pointers to data of any type; List is generic

Bad: List cannot contain anything but pointers

Add operation is awkward for primitive types
List_addFirst(oList, "Ruth"); // OK
List_addFirst(oList, 5.5);  // no
double d = 5.5;
List_addFirst(oList, &d);  // OK
Get operation is awkward for all types: user must cast before dereferencing
*List_getFirst(oList); // no
*((char*)List_getFirst(oList)); // yes
*((double*)List_getFirst(oList)); // yes

List Version 1: Fundamentals

See list.h, list.c, testlist.c

Describe what it does

Defines a generic List ADT, and manipulates it

Describe how it works

Implementation is a doubly-linked list

Draw informal picture on board

Each node contains address of next node and previous node

Easy to add/remove/get nodes from either front or back

Very common implementation: see C++ Standard Template Library, Java standard collection classes

Circular, with a "marker" node marking the boundary between the first and last nodes

Draw informal picture on board

The interface: list.h

Describe each function declaration

Note structure declaration

Informs compiler that structure exists

Does not define the structure (i.e., does not name its fields)

Compiletime error to refer to fields in list.h or testlist.c

Note typedef

Establishes an alias: "List_T" is an alias for "struct List *"

Structure declaration and typedef used in that manner define an opaque pointer

Hides implementation of data structure from user

Can change implementation without needing to change user

Name of structure and typedef'd name can be same -- see Hanson book

Error prone; I avoid

Note function comments -- for user

References to formal parameters, descriptions of exceptions

Note variable naming conventions

Very valuable with C

"o" means object

"pv" means pointer to void

Note void pointer

Note function pointer

(Described next precept)

The user: testlist.c

Note that it includes list.h so compiler can check function calls

Trace entire main function informally

The implementation: list.c

Note that it includes list.h so compiler can check for inconsistencies between function declarations and definitions

Note function comments -- for maintainer

Note use of variable prefixes to indicate types

Note validation of formal parameters via assert function calls

Note use of malloc and free

Note use of the -> operator

Trace List_new, List_addFirst

Refer to diagrams listtrace1.pdf and listtrace2.pdf

Princeton University COS 217: Introduction to Programming System