Data Structures Easy to Advanced Course - Full Tutorial
from a Google Engineer
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:
github.com/myusername/data-structures.
Make Sure You Saw the Last Video So You Know What's Going on With This Array
Implementation.
from a Google Engineer
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:
github.com/myusername/data-structures.
Make Sure You Saw the Last Video So You Know What's Going on With This Array
Implementation.
