Abstract data types

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.