When bringing up the topic of “Data Structures”, it is first important to understand what they are. TechTarget states that “a data structure is a specialized format for organizing and storing data”. This provides a high-level definition to get you started; so let’s explore it a little deeper.
Below are a few examples of common data structures:
Primitive types: Boolean, Integer, Double, Character, String
Composite/Non-primitive types: Array, Record, Union
Abstract types: List, Associate Array, Stack, Queue, Tree
By identifying some merits and weaknesses of common data structures it becomes clearer where we should make use of the many provided data types.
| Types | Merits | Weaknesses |
|---|---|---|
| String | Can contain a collection of characters. Very fast for searching and indexing. | Not ideal for storing collections of data types together or associating records. |
| Array | Very fast information retrieval. | Not able to mix data types. |
| Stack | Very fast for adding an item to a stack by using its ‘push’ method call. | Not ideal for removing items out of insertion order because of the Last-In First-Out (LIFO) fundamental. |
| Queue | Ideal for maintaining order of which data needs to be processed next. | Difficult to change order of a queue after creation. |
| Tree | Great for organisational hierarchical structures. | Slow for searching if a data item/node is low down in the tree, then all nodes need to be scanned before the item is found. |
Choosing the correct data structure can be paramount to the success, performance and efficiency of a software application/solution.
Say we were given the task of developing a data structure for a phone’s contact list. What data structure options would we have, and how would we decide which one would be the best choice?
From the above table, we could identify a few characteristics that would be needed and narrow down how we could, therefore, approach the situation.
Requirements:
Store a list of names with associative phone numbers and other arbitrary details such as alternative numbers, addresses or notes.
Option 1:
An Associative Array would allow us to store our data in the following pattern.
| [0,0] – Name 1 | [0,1] – Number 1 | [0,2] – Additional Number 1 | [0,3] – Address 1 |
| [1,0] – Name 2 | [1,1] – Number 2 | [1,2] – Additional Number 2 | [1,3] – Address 2 |
| [2,0] – Name 3 | [2,1] – Number 3 | [2,2] – Additional Number 3 | [2,3] – Address 3 |
| [3,0] – Name 4 | [3,1] – Number 4 | [3,2] – Additional Number 4 | [3,3] – Address 4 |
Using this method we can call Array[1][0] and get back “Name 2”.
Option 2:
Using a Javascript Object Notation (JSON) structure would allow us to store and search the information quite rapidly.
ContactList = {[
{"name":"Name 1", "number":"Number 1", "additional_number":"Additional Number 1", "address":"Address 1"},
{"name":"Name 2", "number":"Number 2", "additional_number":"Additional Number 2", "address":"Address 2"},
{"name":"Name 3", "number":"Number 3", "additional_number":"Additional Number 3", "address":"Address 3"},
{"name":"Name 4", "number":"Number 4", "additional_number":"Additional Number 4", "address":"Address 4"},
]};
This way if we refer to ContactList[1].name, we will get “Name 2” back just like the associative array in Option 1 above, except we are able to shuffle and sort the data without having to reindex the base array.
References:
“Data Structure” (2006) – Available from: http://searchsqlserver.techtarget.com/definition/data-structure
“List of data structures” (2017) – Available from: https://en.wikipedia.org/wiki/List_of_data_structures
“List (abstract data type)” (2017) – Available from: https://en.wikipedia.org/wiki/List_(abstract_data_type)
“Stacks and Queues” (2009)
“JSON Schema: A Media Type for Describing JSON Documents” (2016) – Available from: http://json-schema.org/latest/json-schema-core.html