What are abstract data types

14.2 Abstract data types

General

A data structure has a specific structure (hence the word "structure" in "data structure"). An array, for example, consists of a defined number of elements of the same data type that are arranged one behind the other in the main memory of the computer. If the memory address of the first array element is known, the address of an element searched for can be calculated with the aid of the index.

In computer science, however, the term "abstract data type" has now established itself. This term is closely related to the notion of algorithmic abstraction, data abstraction and, above all, data encapsulation; an abstract data type basically describes nothing more than a data capsule.

When we define an abstract data type (ADT for short), we don't have to worry at all about the "structure" or "internal organization" or "implementation" of the data, we just specify which operations this ADT should be able to perform. Not more.

ADT stack / stack

Let's make that clear with an example. One of the best-known abstract data types is the stack or stack memory:

A stack of plates

A stack of plates is a good example of a stack. The ADT stack is defined by the following operations:

  • Init (): Creates an empty stack.
  • Push (x): The element x is added.
  • Pop(): The last added item is removed.
  • Top(): The value of the element added last is returned.
  • Empty (): If the stack is empty, TRUE is returned, otherwise FALSE.

These five operations fully describe how a stack works. When defining the ADT, only the operations are specified. How the operations work internally or how they are implemented is completely irrelevant. Spontaneously, one would certainly implement such a stack in Java with the help of an array, but completely different possibilities would also be conceivable. Here the principle of data encapsulation comes to the fore again.

ADT queue

Another important example of an abstract data type is the queue. Here is the full definition of this ADT:

  • Init (): Creates an empty queue.
  • Enqueue (x): The element x is added.
  • Dequeue (): The element added first is removed.
  • Front(): The value of the element added first is returned.
  • Empty (): If the queue is empty, TRUE is returned, otherwise FALSE.

There are plenty of examples of queues in everyday life, for example as a queue in front of a department store checkout.

ADT List / List

A third example of a linear ADT is the list. Here is the (incomplete) definition of the operations of the ADT List from the English Wikipedia

Implementation of the list data structure may provide some of the following operations:

  • a constructor for creating an empty list;
  • an operation for testing whether or not a list is empty;
  • an operation for prepending an entity to a list
  • an operation for appending an entity to a list
  • an operation for determining the first component (or the "head") of a list
  • an operation for referring to the list consisting of all the components of a list except for its first (this is called the "tail" of the list.)

Lists can be found, for example, on the screen of a media player displaying a list of pieces of music or films. With the cursor keys on the remote control you can jump to the beginning or end of the list and work your way up and down through the list.

Lists play an extremely important role, especially in the Central High School in North Rhine-Westphalia. However, the NRW list is not an ADT, but a Java class with a large number of methods.

ADT Binary search tree

The fourth example stands for a non-linear ADT, namely for the binary search tree, which we got to know briefly in episode 12.3 when it came to fast search algorithms, and which we will also deal with in detail later. If you search the internet here, you will find many different operations for the binary search tree. Here's an example:

  • Init (): Creates an empty search tree
  • Insert (x): The element x is added.
  • Delete (x): The element x is removed.
  • Find (x): The element x is searched for
  • FindMax (): The largest element is searched for and returned
  • FindMin (): The smallest element is searched for and returned

There are trees, especially binary search trees, wherever a lot of data has to be systematically managed. Searching in large amounts of data, in particular, is suddenly simplified by such search trees.

This was a small overview of four important abstract data types. There are many other ADTs, but these four ADTs are the most important for computer science classes in North Rhine-Westphalia. In the following, we will take a closer look at each of these four ADTs, starting with the ADT stack.

Top of page -
Continue with the ADT stack ...