Data Types
Data types can be grouped into 3 categories.
Primitive
Data types that are directly supported by a programming languages.
Examples are:
- Boolean
- Characters
- Integers
- Floating-point numbers
- Memory pointers
Composite
Data types that are built as
- structured collections of primitive types
- using other composite types already defined
Examples are:
- Array
- Record or Tuple
- Union
Tuple
Represents a finite ordered list of elements. Can contain different data types. Immutable. Tuple with length n is called as “n-tuple”.
Some tuples have special names:
- length 0 : empty-tuple or null-tuple
- length 1 : singleton
- length 2 : couple
- length 3 : triple
Abstract
Data types that are well defined in terms of properties and operations but not implementation.
Examples:
- List
- Set
- Stack - Last in; first out
- Queue - First in; first out
- Tree
- Hash Table
- Graph
List
Represents a countable number of values where the same value can occur more than once. Ordered. Can include different data types. Mutable. Aka. iterable collection.
Defined methods:
- isEmpty()
- prepend(item)
- append(item)
- head()
- get(i)
- set(i)
- tail()
Set
Represents a collection of distinct objects. Unordered. Iterable. Mutable (but elements must be immutable). No duplicate elements.
Dictionary
Collection of key-value pairs. Unordered.
Tree
Holds a set of nodes. Each node holds a value. Each node can have child nodes.
Binary Tree
Tree with the restriction of at most 2 child nodes per node.
Complete Binary Tree
A binary tree in which every level, except possibly the last, is completely filled, and all nodes are as far left as possible.
Binary Heap
A binary heap is complete binary tree where items are stored in a way such that the value in a parent node is greater/smaller than values in its 2 children nodes. Can be represented by a binary tree or an array. 2 types:
- Max heap: when the parent node value is greater than its children nodes
- Min heap: when the parent node value is smaller than its children nodes
Can be represented by either an array or a binary tree.
Array representation
If a parent node is stored at index
Space efficient representation.