Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

Data Structures
A data structure organizes data for efficient use and is essential for creating powerful
algorithms
...

To understand the performance that data structures provide, we need to look at the wild world
of computational complexity
...
However, it does not provide the details surrounding how those methods are
implemented
...
Almost any mathematical
expression containing n can be wrapped around a Big O
...

Constant Time Algorithms
Both of the following algorithms run in constant time relative to the input size because they are
independent of n
...

●
●

Algorithm 1
Algorithm 2

Binary Search Algorithm
A classic algorithm for binary search has a logarithmic time complexity
...
Then, it selects a
midpoint between the two pointers and checks if the value being searched for is found at the

midpoint
...

This is the first part of a two-part video series on arrays
...

What is a Static Array?
A static array is a fixed-length container containing elements
...

Searching Can Take up to the Linear Time Because We Potentially Have to Traverse all the
Elements in the Array in the Worst Case
...
The Static Array is a Fixed
Size Container, so It Cannot Grow Larger or Smaller
...
If We Look at a,
You Can See That it Contains the Values 4412, -517, 6039, and 100
...
However, This is Not at All a Requirement of the Array
...
This Confuses a Lot of Intro Computer Science Students
...

This is Part Two of Two in the Array Series
...
com/myusername/data-structures
...

The add method is used to resize a static array
...
We first initialize the array and cast it to type t
...


Singly and Doubly Linked Lists
Linked lists are one of the most useful data structures available
...
In part two, we will examine source code on
how to implement a doubly linked list
...
There are two types of
linked lists:
●
●

Singly linked lists only contain a pointer to the next node
...


Each has its own trade offs
...

A doubly linked list uses twice as much memory as a singly linked list but allows us to easily
traverse the list backwards and remove elements
...
Here's how we remove elements from a singly linked list:
​
​
​
​

Create two pointers: traverser1 and traverser2
...

Track the previous element using traverser2
...
next to traverser1
...


While the worst case scenario for searching in a linked list is linear, removing elements from a
singly linked list takes linear time
...
For source
code on doubly linked lists, check out part two of the linked list series
...
Peeking means examining the element at either the beginning
or the end of the linked list, but a runtime exception is thrown in Java to prevent peeking an
empty list
...
Note that this
method is set to private because the node class is also private, and the user should not have
access to the node
...
If we are somewhere in the middle of the
linked list, we make the pointers adjacent to our current node equal to each other, effectively
skipping over the current node
...
We'll look at some creative examples of how to
solve problems with stacks, and then briefly investigate their internal implementation
...


Stacks in Programming
The behavior is commonly known as LIFO, or Last In First Out
...
It is common to see elements in a stack always get removed and added to the
top of the pile
...


Determining Valid Bracket Sequences
Given a string made up of the following brackets: round brackets (), square brackets [], and curly
brackets {}, determine whether the brackets properly match
...
So before I
show you the solution, try and come up with a solution yourself
...

Here's the pseudocode of the algorithm we just ran through:
if (left bracket)
 push to stack
else if (right bracket)
 if (stack is empty)
  invalid bracket sequence
 else
  pop from stack
So, if we let "us" be a stack, and for every bracket in our bracket string, we can get the reverse
bracket for that current bracket easily
...

Otherwise, we check if the stack is empty
...




---