Unit 1 Data & Types of Data Structure

 

Data Types

A data type is an attribute of data which tells the compiler (or interpreter) how the programmer intends to use the data.

• Primitive: basic building block
• (boolean, integer, float, char etc.)
• Composite: any data type (struct, array, string etc.) composed of primitives or composite types.
• Abstract: data type that is defined by its behaviour (tuple, set, stack, queue, graph etc).

If we consider a composite type, such as a ‘string’, it describes a data structure which contains a sequence of char primitives (characters), and as such is referred to as being a ‘composite’ type. Whereas the underlying implementation of the string composite type is typically implemented using an array data structure (we’ll cover data structures shortly).

An abstract data type (ADT) describes the expected behaviour associated with a concrete data structure. For example, a ‘list’ is an abstract data type which represents a countable number of ordered values, but again the implementation of such a data type could be implemented using a variety of different data structures, one being a ‘linked list’.

Data Structure

A data structure is a collection of data type ‘values’ which are stored and organized in such a way that it allows for efficient access and modification. In some cases a data structure can become the underlying implementation for a particular data type.

For example, composite data types are data structures that are composed of primitive data types and/or other composite types, whereas an abstract data type will define a set of behaviours (almost like an ‘interface’ in a sense) for which a particular data structure can be used as the concrete implementation for that data type.

When we think of data structures, there are generally four forms:

1. Linear: arrays, lists
2. Tree: binary, heaps, space partitioning etc.
3. Hash: distributed hash table, hash tree etc.
4. Graphs: decision, directed, acyclic etc.