Data Types Flashcards
Primitive data types
The set depends on the language. Best definition: a data type that isn’t built from other data types and can only represent a single value.
Composite data type
Any data type that can be constructed from primitive data types. Often called a structure or aggregate. Examples include arrays, tuples / structs / records, unions and tagged unions.
Abstract data type
Class of objects whose behavior is defined by a set of values and a set of operations. Lists, sets, stacks, queues, trees, graphs
Linear data structures
Linear data structures are data structures whose elements form a sequence. Interesting example: system image: a serialized copy of the entire state of a computer system.
Array
Linear data structure, useful because the indices can be computed at run time
Lists
Dynamic / growable array
Linked list
Each item is comprised a reference link and a value
Tree
A tree can be defined recursively as a root node and its child nodes
Data structure operations
Insert, delete, search, traversal
Tree uses
- Representing hierarchical data
- Storing data in a way that makes it efficiently searchable
- Routing algoritms
Binary tree
- Defined recursively as the set (L, S, R)
- In computing, binary trees are typically used along with a labeling function associating each node with a value which makes them efficient for searching and sorting
Full binary tree
Each node has 0 or 2 children
Perfect binary tree
All interior nodes have 2 children and all leaf nodes are on the same level
Balanced binary tree
Has the minimum possible maximum depth
B-tree
A generalization of the binary search tree in that a node can have more than 2 children.
