Data Structure Basics pt.6
Table of Contents
Review
Over the course of the Data Structure Basics series we talked at an introductory level about:
- Basic concepts and definitions.
- Arrays.
- Lists, stacks, and queues.
- Associative arrays.
- Tree data structures.
Choosing Data Structures
These are a few things about the data we deal with that we should always keep in mind when choosing data structures:
- How much data do we have?
- How often does it change?
- Does it need to be kept sorted?
- and so on.
However complex we get, these questions will drive our decision. We need to get passed the ‘which data structures are fast’ question. Instead, we should consider the situation we are dealing with to figure out if we want speed in accessing a direct object, searching, inserting, deleting, sorting, or what have you, because those are the key question.
Which data structure we choose hardly impacts the performance of our system when we only deal with trivial amounts of data. But as we gather data and we need to perform thousands of operations per second choosing the right data structure becomes quite relevant. Here are a few thing to keep in mind when choosing.
Arrays
| Strengths | Weaknesses |
|---|---|
| Direct indexing | Sorting and seaching |
| Easy to create and use | Inserting and deleting particularly if not at start/end |
Linked Lists
| Strengths | Weaknesses |
|---|---|
| Inserting and deleting elements | Direct access requires traversal of the list |
| Iterating through the collection | Searching and sorting (same as direct access) |
Stacks and Queues
| Strengths | Weaknesses |
|---|---|
| Design for LIFO/FIFO | Direct access |
| Searching and sorting |
Hash Tables
| Strengths | Weaknesses |
|---|---|
| Speed of insertion and deletion | Some overhead |
| Speed of access | Retrieving in a sorted order |
| Searching for a specific value |
Sets
| Strengths | Do not use for |
|---|---|
| Checking existence | Direct access |
| Avoiding duplicates |
Binary Search Trees
| Strengths | Weaknesses |
|---|---|
| Speed for insertion and deletion | Some overhead |
| Speed of access | |
| Maintaining sorted order |
Other things to consider are:
- Fixed structures are faster and smaller.
- Choose fixed (immutable) structures whenever is possible.
- Use mutable structures so you can load it up with unpredictable amounts of data. Consider then copying it into an immutable one if all you need to do from then on is only accessing the data.