Data Structures Easy to Advanced - Full
Tutorial
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.
The add method is used to resize a static array. The size of
the array must be greater than or equal to zero. We first
initialize the array and cast it to type t . We also
include suppress warnings and unchecked due to issues
with generics.
Singly and Doubly Linked Lists
Linked lists are one of the most useful data structures
available. This is part one of two where we will be discussing
Tutorial
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.
The add method is used to resize a static array. The size of
the array must be greater than or equal to zero. We first
initialize the array and cast it to type t . We also
include suppress warnings and unchecked due to issues
with generics.
Singly and Doubly Linked Lists
Linked lists are one of the most useful data structures
available. This is part one of two where we will be discussing
