Skip to main content

Define data structure; explain ADT

Short answer

A data structure is a way of organizing and storing data efficiently. An abstract data type (ADT) is a mathematical model defined by values and allowed operations, hiding implementation. For example, the STACK ADT specifies push, pop, and empty operations without revealing whether the stack uses an array or linked list.

Define data structures. Explain ADT with suitable example.

A data structure is a particular way of organising and storing data in the memory of a computer so that it can be accessed, searched and modified efficiently. It also includes the set of operations defined on the organised data. Examples: array, stack, queue, linked list, tree, graph.

Abstract data type (ADT)

An abstract data type (ADT) is a mathematical model of a data type that is defined by its values and the operations allowed on them, without saying how they are stored or coded. The user sees only what the type does; how it is done (array, linked list, etc.) stays hidden. In Tenenbaum's style an ADT has two parts: a value definition and an operator definition.

Example: STACK ADT

/* Value definition: a sequence of elements of type eltype,
   insertion and deletion allowed only at one end (top) */
abstract typedef <<eltype>> STACK(eltype);

/* Operator definition */
abstract empty(s)  STACK(eltype) s;
   postcondition empty == (len(s) == 0);
abstract push(s, elt)  STACK(eltype) s; eltype elt;
   postcondition s == <elt> + s(before);
abstract eltype pop(s)  STACK(eltype) s;
   precondition  empty(s) == FALSE;
   postcondition pop == first(s(before));
                 s == sub(s(before), 1, len(s(before)) - 1);

A program uses push, pop and empty only; whether the stack is an array or a linked list is hidden.

✓ Answer checked by Claude Opus 5.5 (high effort)

Related questions

All Data Structure and Algorithm chapter 1 questions →