Abstract data types

By Martin McBride, 2018-05-04
Tags: abstract data type list array map encapsulation
Categories: data structures

An abstract data type defines a composite data type such as a list, queue, or map. The data type is defined by the set of functions that can be used to operate on the data.

For example a list might provide functions like these:

  • Add an element to the end of the list, using the append() function
  • Count how many elements are in the list, using the len() function
  • Check if it has an element with value 5, using the find() function
  • Sort the elements into decreasing order, using the sort() function
  • And many more...

A programmer will use these functions to access the list, which means that they don't need to know anything about how the list works in order to use it. We call it an abstract type because its internal structure is not visible.

In this diagram, the low level data structure that implements the list is hidden (represented by the cloud around it). We call this information hiding because you can't access the raw data. It is also sometimes called encapsulation. The various functions allow you access and modify the list.

You will find that most languages provide abstract data types for other structures such as queues, maps, trees etc.

Data structures

An abstract data type always has an underlying data structure that implements its functionality. Quite often there are several different ways to implement the data type - for example a list can be implemented as an array list or a linked list.

The abstract data type provides the interface that programmers use to access that data. The interface remains the same, even if a different data structure is used underneath to implement the data type.

Examples

In Python, you can create a list like this:

k = [1, 'abc', 2, 'xyz']

A Python list can contain any type of data, or even a mix of different types as shown here. You don't get any choice of what type of list. In fact, Python uses array lists, but you don't really need to know that.

In Java, lists have a type. For example if you create a list of type String, it can only contain String elements. You also get to choose what type of list you want - typically an ArrayList or a LinkedList (one or the other might be slightly faster, depending on how the list will be used):

List<String> k = new ArrayList();
k.add("abc");

In this case we have created an ArrayList, but we are storing it in a variable of type List, so the rest of the code doesn't know what type of list it is dealing with.

See also

Sign up to the Creative Coding Newletter

Join my newsletter to receive occasional emails when new content is added, using the form below:

Popular tags

555 timer abstract data type abstraction addition algorithm and gate array ascii ascii85 base32 base64 battery binary binary encoding binary search bit block cipher block padding byte canvas colour coming soon computer music condition cryptographic attacks cryptography decomposition decryption deduplication dictionary attack encryption file server flash memory hard drive hashing hexadecimal hmac html image insertion sort ip address key derivation lamp linear search list mac mac address mesh network message authentication code music nand gate network storage none nor gate not gate op-amp or gate pixel private key python quantisation queue raid ram relational operator resources rgb rom search sort sound synthesis ssd star network supercollider svg switch symmetric encryption truth table turtle graphics yenc