What is a data structure?

/
fundamentals

This tutorial is a part of the Data Structures and Algorithms class:

What is a data structure?

A data structure is a specific structure we store data in order to query it later. The speed (time complexity) of querying/inserting the data is the most important factor when choosing what kind of structure to store your data.

lecture-2/data-structures.js
// Example: store numbers, check if a given number is stored
// Data structure used: array, set

const numberToCheck = 1000000
const array = []

for(let i = 0; i <= numberToCheck; i++) {
  array[i] = i
}

const set = new Set(array)
// set: Set { 0, 1, 2, ..., 1000000 }
// array: [ 0, 1, 2, ..., 1000000 ]

console.time('time to check if number is in array')
array.includes(numberToCheck) // time to check if number is in array: 2.186ms, time complexity: O(n)
console.timeEnd('time to check if number is in array')

console.time('time to check if number is in set')
set.has(numberToCheck) // time to check if number is in set: 0.009ms, time complexity: O(1)
console.timeEnd('time to check if number is in set')

// => Array check: 2.186ms
// => Set check: 0.009ms
// => Array check takes 242 times longer than Set check, on 1,000,000 records
$ node data-structures.js
time to check if number is in array: 2.186ms
time to check if number is in set: 0.009ms
Data Structure Insert Delete Access Search
Array O(1) at end: push
O(n) at random: splice		 O(n): pop, splice O(1) with index O(n): includes
Set O(1): add O(1): delete --- O(1): has

What to remember when learning a new data structure?

  • How data looks like (print it out!)
  • How to insert/delete/access/search data
  • How fast (time complexity advantage) to insert/delete/access/search data
lecture-2/array-and-set.js
const array = [1, 2, 3, 'a', 'b']
const set = new Set ([1, 2, 3, 'a', 'b'])

array.push('hi')
set.add('world')

console.log('array:', array) // array: [ 1, 2, 3, 'a', 'b', 'hi' ]
console.log('set:', set) // set: Set { 1, 2, 3, 'a', 'b', 'world' }
$ node array-and-set.js
array: [ 1, 2, 3, 'a', 'b', 'hi' ]
set: Set { 1, 2, 3, 'a', 'b', 'world' }
Data Structure Insert Delete Access Search
Array O(1) at end: push
O(n) at random: splice		 O(n): pop, splice O(1) with index O(n): includes
Set O(1): add O(1): delete --- O(1): has

⬆️ Time complexity (worst case) per operation

Why are there so many data structures?

  • Software has touched every aspect of human life. Due to this vastly diverse application, humans have invented hundreds of data structures best suited for each field such as: finance, manufacturing, agriculture, design, artificial intelligence, ...
  • Each data structure has its own key advantage: O(1) operation(s).
  • But luckily, you don't have to learn all of them. You only need to learn 10 most frequently used data structures. Which will help you solve 90% of daily problems. The rest, only learn when needed.

Improving time usually requires more space and vice versa

  • There is always a tradeoff between Time and Space complexity.
  • Faster time usually requires more Space.
  • Lesser Space usually requires longer Time.
  • We'll discuss this more in algorithms tutorials.

Real life interview questions

  1. What is a data structure?
  2. What should you know when talking about a data structure?
  3. Why are there so many data structures? Should we know them all? Why/why not?
  4. What is the tradeoff between time & space?