DS&A

Abstract Data Types

A type defines not just the possible values that some data can take, but also the operations which can be performed on that data. For example, the int type represents integers, and supports arithmetic operations, bitwise operations and comparison operations.

• In Python, int represents integers of any size, and supports:
  • The arithmetic operations +, -, *, /, **, // and %.
  • The bitwise operations &, |, ~, ^, << and >>.
  • The comparison operations ==, !=, <, <=, > and >=.
• In Java, int represents integers from −2,147,483,648 to 2,147,483,647, and supports:
  • The arithmetic operations +, -, *, / and %.
  • The bitwise operations &, |, ~, ^, <<, >> and >>>.
  • The comparison operations ==, !=, <, <=, > and >=.

An important but often overlooked point is that a type’s operations aren’t just what you can do with its values — they’re all you can do with its values.(1) As far as the programmer is concerned, int’s set of possible values and supported operations completely specify what ints are and what you can do with them; you can define new operations with int inputs yourself, but they must be composed of the operations already defined.

This means we can define types just by specifying their possible values and supported operations; those values must be represented in the computer somehow, but it’s not necessary to specify how they should be represented. A type defined this way is called an abstract data type (ADT) — “abstract” because we specify how the type is used but not how it is implemented. Our above definition of the int type doesn’t mention anything about how to represent integers or do anything with them; it’s about “what” rather than “how”.

Let’s try to specify some standard collection types as ADTs:

List

A list represents a sequence of values, and supports the following operations:

• Create an empty list.
• Get the value at index i.
• Set a new value x at index i, replacing the old value there.
• Get the length (number of values in the list).
• Append a new value x at the end of the list.
• Insert a new value x at index i, shifting any later values forwards by 1 without replacing any.
• Remove the value at index i, shifting any later values backwards by 1.
• Clear the list (remove all values).
• Iterate over the values in the list, in order of index.

There are a few more details — we assume any indices must be within the current bounds of the list, for example. This set of operations also isn’t “complete”; lists in real programming languages usually support many more operations for the programmer’s convenience, but they can be composed of the operations above.

Set

A set represents an unordered collection of values, and supports the following operations:

• Create an empty set.
• Check whether the set contains a value x or not.
• Get the size (number of values in the set).
• Insert a new value x into the set, if it is not already present.
• Remove a value x from the set.
• Clear the set (remove all values).
• Iterate over the values in the set.

Because sets are unordered collections, when we iterate over a set, its values might come in any order — generally not the same order they were originally added, nor any natural ordering like numerical or alphabetical order. Again, sets in most programming languages support more operations, which can be composed of these ones.

Dictionary

A dictionary (also called a map or an associative array) represents a mapping from keys to values.(2) If a key is present in the dictionary, then it is associated with a single value. Dictionaries support the following operations:

• Create an empty dictionary.
• Get the value associated with a key k (if any).
• Set the key k to have a new value x, replacing its old value (if any).
• Check whether the dictionary contains a key k or not.
• Get the size (number of key/value pairs in the dictionary).
• Remove the key k, and the value associated with it, from the dictionary.
• Clear the dictionary (remove all key/value pairs).
• Iterate over the keys in the dictionary.
• Iterate over the values in the dictionary.
• Iterate over the key/value pairs in the dictionary.

There is usually no guarantee of iterating over the keys or values in any particular order. Again, dictionaries in most programming languages support more operations, which can be composed of these ones.

Footnotes

1. Strictly speaking, there are also some things you can do with values of any type, such as store them in variables or pass them as arguments.
2. Dictionary keys serve a similar purpose to list indices; each value is stored ‘at’ a particular key.

• Tags: 
• types, abstract data types, collections, lists, sets, dictionaries