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.

 

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 it’s ‘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.

[code]

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”},
   ]
}’;
[/code]

 

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 (Accessed on 5th February 2017)

 

“List of data structures” (2017) – Available from: https://en.wikipedia.org/wiki/List_of_data_structures (Accessed on 6th February 2017)

 

“List (abstract data type)” (2017) – Available from: https://en.wikipedia.org/wiki/List_(abstract_data_type) (Accessed on 6th February 2017)

 

“Stacks and Queues” (2009) – Available from: https://www.cs.cmu.edu/~adamchik/15-121/lectures/Stacks%20and%20Queues/Stacks%20and%20Queues.html (Accessed on 6th February 2017)

 

“JSON Schema: A Media Type for Describing JSON Documents” (2016) – Available from: http://json-schema.org/latest/json-schema-core.html (Accessed on 6th February 2017)