Abstract data type

Abstract data types or ADTs are data types described in terms of the operations they support—their interface—rather than how they are implemented.

An ADT consists of two components: an interface and an implementation. Users of an ADT are aware of the interface, but not of the implementation. A third component, a driver, is developed by the user of an ADT, although the developer usually also creates a test driver when writing the ADT.

When done correctly, a totally different implementation could be used without any need to modify existing code using the ADT.

If the ADT is implemented so that instances of the ADT can be created, it is called a First Class ADT. This approach provides a more general ADT, and makes it easier to reuse the ADT on other projects.

For example, the interface for a first class ADT of a Stack might be:

long stack_create(); /* create new instance of a stack */
void stack_push(long stack, void *item); /* push an item on the stack */
void *stack_pop(long stack); /* get item from top of stack */
void stack_delete(long stack); /* delete the stack */

This ADT could be used in the following manner:

long stack;
struct foo *f;

stack = create_stack(); /* create a stack */

stack_push(stack, f); /* add foo structure to stack */

f = stack_pop(stack); /* get top structure from stack */

Notice that nothing has been said of the implementation. The stack could be initially implemented using an array, and then later changed to a linked list, without affecting any user code.

The above ADT could be implemented using an array as follows:

/* this example uses static values and doesn't check for errors */
struct Stack
{
  int top; /* initialized to zero */
  void *items[STACK_SIZE]; /* used to store the actual items */
}
static struct Stack *Stacks[MAX_STACKS]; /* collection of stacks */

long create_stack()
{ /* create a new instance of a stack */
   long ret; /* will be the handle returned to user */
   void *stack; /* will be the actual stack */
   ret = find_available_stack(); /* return index into Stacks above */
   Stack[ret] = malloc_stack(); /* allocate stack */
   return ret;
}

void stack_push(long stack, void *item)
{ /* get item from top of stack */
   struct Stack *s;
   s = Stacks[stack]; /* get the actual stack */
   s->items[s->top++] = item;
}

void *stack_pop(long stack)
{ /* add item to top of stack */
   struct Stack *s;
   s = Stacks[stack]; /* get actual stack */
   return s->items[--(s->top)]; /* item to return */
 }

void stack_free(long stack)
{ /* delete instance of stack */
  free_stack(Stacks[stack]);
  Stacks[stack] = NULL;
}

Some programming languages, such as Ada and Modula-2, have explicit support for abstract data types. Object-oriented languages carry this a step further by adding inheritance and polymorphism to ADTs to get "objects".