Data Structures Easy to Advanced Course - Full Tutorial from a Google Engineer
NITRO CREATION
In these first few videos, we will lay the foundation for core concepts needed throughout these tutorials.
Let's start with the basics.
Data Structures
A data structure organizes data for efficient use and is essential for creating powerful algorithms.
Another reason for using data structures is to manage and organize data naturally. To understand the
performance that data structures provide, we need to look at the wild world of computational
complexity.
The abstract data type defines how a data structure should behave and what methods it should have.
However, it does not provide the details surrounding how those methods are implemented. Big O
notation only cares about what happens when input becomes arbitrarily large, ignoring things like
constants and multiplicative factors. Almost any mathematical expression containing n can be wrapped
around a Big O. If the algorithm takes logarithmic or quadratic/cubic time, then it's represented as Big O
of a log event.
Constant Time Algorithms
Both of the following algorithms run in constant time relative to the input size because they are
independent of n. As the input size grows infinitely large, the loop still runs for the same amount of time.
Algorithm 1
Algorithm 2
Binary Search Algorithm
A classic algorithm for binary search has a logarithmic time complexity. This algorithm starts by creating
two pointers: one at the beginning and one at the end of the array. Then, it selects a midpoint between
the two pointers and checks if the value being searched for is found at the midpoint. Regardless of
, whether the value is found or not, it discards one half of the array and adjusts either the high or low
pointer accordingly.
This is the first part of a two-part video series on arrays. Arrays are fundamental building blocks for all
other data structures, and with arrays and pointers alone, it is possible to construct nearly any data
structure.
What is a Static Array?
A static array is a fixed-length container containing elements.
The Access Time for Static Array and a Dynamic Array is Constant Because of a property that Arrays are
indexable.
Searching Can Take up to the Linear Time Because We Potentially Have to Traverse all the Elements in
the Array in the Worst Case.
Inserting/Appending from a Static Array Doesn't Really Make Sense. The Static Array is a Fixed Size
Container, so It Cannot Grow Larger or Smaller.
When Inserting with a Dynamic Array, This Operation Can Cost up Linear Time. If We Look at a, You Can
See That it Contains the Values 4412, -517, 6039, and 100. Currently, All the Elements are Distinct.
However, This is Not at All a Requirement of the Array.
Also Remark That the Very First Element 44 is Indexed, or Positioned, at Index of Zero in the Array, Not
One. This Confuses a Lot of Intro Computer Science Students. The Confusing Part is That Mathematics is
One-Based While Computer Science is Zero-Based.
This is Part Two of Two in the Array Series.
The Source Code for This Video Can be Found at the Following Link:
NITRO CREATION
In these first few videos, we will lay the foundation for core concepts needed throughout these tutorials.
Let's start with the basics.
Data Structures
A data structure organizes data for efficient use and is essential for creating powerful algorithms.
Another reason for using data structures is to manage and organize data naturally. To understand the
performance that data structures provide, we need to look at the wild world of computational
complexity.
The abstract data type defines how a data structure should behave and what methods it should have.
However, it does not provide the details surrounding how those methods are implemented. Big O
notation only cares about what happens when input becomes arbitrarily large, ignoring things like
constants and multiplicative factors. Almost any mathematical expression containing n can be wrapped
around a Big O. If the algorithm takes logarithmic or quadratic/cubic time, then it's represented as Big O
of a log event.
Constant Time Algorithms
Both of the following algorithms run in constant time relative to the input size because they are
independent of n. As the input size grows infinitely large, the loop still runs for the same amount of time.
Algorithm 1
Algorithm 2
Binary Search Algorithm
A classic algorithm for binary search has a logarithmic time complexity. This algorithm starts by creating
two pointers: one at the beginning and one at the end of the array. Then, it selects a midpoint between
the two pointers and checks if the value being searched for is found at the midpoint. Regardless of
, whether the value is found or not, it discards one half of the array and adjusts either the high or low
pointer accordingly.
This is the first part of a two-part video series on arrays. Arrays are fundamental building blocks for all
other data structures, and with arrays and pointers alone, it is possible to construct nearly any data
structure.
What is a Static Array?
A static array is a fixed-length container containing elements.
The Access Time for Static Array and a Dynamic Array is Constant Because of a property that Arrays are
indexable.
Searching Can Take up to the Linear Time Because We Potentially Have to Traverse all the Elements in
the Array in the Worst Case.
Inserting/Appending from a Static Array Doesn't Really Make Sense. The Static Array is a Fixed Size
Container, so It Cannot Grow Larger or Smaller.
When Inserting with a Dynamic Array, This Operation Can Cost up Linear Time. If We Look at a, You Can
See That it Contains the Values 4412, -517, 6039, and 100. Currently, All the Elements are Distinct.
However, This is Not at All a Requirement of the Array.
Also Remark That the Very First Element 44 is Indexed, or Positioned, at Index of Zero in the Array, Not
One. This Confuses a Lot of Intro Computer Science Students. The Confusing Part is That Mathematics is
One-Based While Computer Science is Zero-Based.
This is Part Two of Two in the Array Series.
The Source Code for This Video Can be Found at the Following Link:
