# Data Structures & Algorithms

Algorithms Course by Grow with Google

###### tags: Data Structures & Algorithms Practice

## Efficiency (Complexity)
* *Efficiency* Is how well you're using you're computers resources to get a job done
* How long does it take for your code to run? How much storage space do you need?
* You can think of it in terms of *space* and *time*

## Big O Notation O(n)
* n contiains an algebraic expression
* n represents the length of an input to your function
* *Approximation* - "Some number of computations must be performed for EACH letter in the input"
* Note that anything that can be approximated to O(n) can be said to occur "in linear time". If you plotted n = y on a graph, it would be a line.

[More about Time Complexity](https://en.wikipedia.org/wiki/Time_complexity#Table_of_common_time_complexities)

### O notation Practice
Below are some examples of functions in Python. Look at each and take note of the time efficiency:

"""
input manatees: a list of "manatees", where one manatee is represented by a dictionary
a single manatee has properties like "name", "age", et cetera
n = the number of elements in "manatees"
m = the number of properties per "manatee" (i.e. the number of keys in a manatee dictionary)
"""

def example1(manatees):
    for manatee in manatees:
        print manatee['name']

def example2(manatees):
    print manatees[0]['name']
    print manatees[0]['age']

def example3(manatees):
    for manatee in manatees:
        for manatee_property in manatee:
            print manatee_property, ": ", manatee[manatee_property]

def example4(manatees):
    oldest_manatee = "No manatees here!"
    for manatee1 in manatees:
        for manatee2 in manatees:
            if manatee1['age'] < manatee2['age']:
                oldest_manatee = manatee2['name']
            else:
                oldest_manatee = manatee1['name']
    print oldest_manatee

#### Example 1

We iterate over every `manatee` in the `manatees` list with the for loop. Since we're given that `manatees` has n elements, our code will take approximately O(n) time to run.

#### Example 2

We look at two specific properties of a specific `manatee`. We aren't iterating over anything - just doing constant-time lookups on lists and dictionaries. Thus the code will complete in constant, or O(1), time.

#### Example 3

There are two for loops, and nested for loops are a good sign that you need to multiply two runtimes. Here, for every `manatee`, we check every property. If we had 4 `manatees`, each with 5 properties, then we would need 5+5+5+5 steps. This logic simplifies to the number of `manatees` times the number of properties, or O(nm).

#### Example 4

Again we have nested for loops. This time we're iterating over the `manatees` list twice - every time we see a `manatee`, we compare it to every other `manatee`'s age. We end up with O(nn), or O(n^2) (which is read as "n squared").

Reference the [Big-O Cheat Sheet](http://bigocheatsheet.com/) to keep track of time complexities for many of the algorithms and data structures

## List-Based Collections
* A *Collection* is a group of things - ex) books, people, animals
* Collections dont have a particular order
* cant say give me the third element
* Collection on its own cannot be used in a programming language

### List
* Has all the properties of a collection
* So it has a group of things but the objects have an order
* ex.) shopping list - has a lot of same properties to a list, the order doesnt mean much and there is no fixed length

### Arrays
* An array is a list with a few added rules
* Each array has a location called an index. An index is just the number associated with that place in the array
* Insertion and deletion can be very messy with arrays - it is difficult if you want to put an element in the middle of the array
* you'll need to move everything after the inserted element back into different boxes with a different index
* For example, inserting into a list is easy (happens in constant time). However, inserting into an array is O(n), since you may need to shift elements to make space for the one you're inserting, or even copy everything to a new array if you run out of space.
* Thus, inserting into a Python list is actually O(n), while operations that search for an element at a particular spot are O(1). You can see the runtime of other list operations [here](https://wiki.python.org/moin/TimeComplexity).

### Linked List
* A Linked List is an extension of a list, but it is definitely not an array
* There are still some things that have order, but there are no indices - instead its characterized by its links
* Each element has some notion of what the next element is since it's connected to it, but not necessarily how long the list is or where it is in the list
* In an array, you know what the next element is by what the next index is... but adding and removing elements in an array is complicated

### Arrays Vs Linked List
* The main distinction is that each element stores different information
* In both cases a single element will store a value (ex. value: 8)
* In an array we would store a number as an index (ex. index: 0)
* You can get the next index by querying the array for the element at index one in this case([8,...])

* In a linked list we store a reference to the next element in the list
* In this case, the first component([8,...])is actually storing the memory address of the next element. While the second element is storing null because it doesnt point to anything else
* The nice thing about this system is that its pretty easy to insert and delete elements

### Linked List Practice
There isn't a built-in data structure in Python that looks like a linked list. Thankfully, it's easy to make classes that represent data structures in Python!

Here's the code for an `Element`, which will be a single unit in a linked list:

class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None

We use `__init__` to initialize a new `Element`. An Element has some `value` associated with it (which could be anything—a number, a string, a character, et cetera), and it has a variable that points to the `next` element in the linked list.

Now, let's set up a `LinkedList` class:

class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

This code is very similar—we're just establishing that a `LinkedList` is something that has a `head` `Element`, which is the first element in the list. If we establish a new `LinkedList` without a `head`, it will default to `None`.

Let's add a method to our `LinkedList` to make it a little more useful. This method will add a new `Element` to the end of our `LinkedList`.

  def append(self, new_element):
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = new_element
        else:
            self.head = new_element

If the `LinkedList` already has a `head`, iterate through the `next` reference in every `Element` until you reach the end of the list. Set `next` for the end of the list to be the `new_element`. Alternatively, if there is no `head` already, you should just assign `new_element` to it and do nothing else.

Add three functions to the LinkedList.
1. "get_position" returns the element at a certain position.
2. The "insert" function will add an element to a particular spot in the list.
3. "delete" will delete the first element with that particular value.

"""Get an element from a particular position.
Assume the first position is "1".
Return "None" if position is not in the list."""
def get_position(self, position):
        counter = 1
        current = self.head
        if position < 1:
            return None
        while current and counter <= position:
            if counter == position:
                return current
            current = current.next
            counter += 1
        return None
        
"""Insert a new node at the given position.
Assume the first position is "1".
Inserting at position 3 means between the 2nd and 3rd elements."""
    def insert(self, new_element, position):
        counter = 1
        current = self.head
        if position > 1:
            while current and counter < position:
                if counter == position - 1:
                    new_element.next = current.next
                    current.next = new_element
                current = current.next
                counter += 1
        elif position == 1:
            new_element.next = self.head
            self.head = new_element
            
"""Delete the first node with a given value."""
    def delete(self, value):
        current = self.head
        previous = None
        while current.value != value and current.next:
            previous = current
            current = current.next
        if current.value == value:
            if previous:
                previous.next = current.next
            else:
                self.head = current.next

### Stack
* Stacks are also list-based data structures
* A *stack* is like a stack of objects in real life - you keep putting elements on top and you have easy access to remove or look at the top element
* Stacks can be really useful if you only care about the most recent elements or the order in which you see and save elements actually matters * ex.) news feed
* When you add an element to a Stack the operation is called *push* instead of insert
* when you take an element off of the stack the operation is called *pop* instead of remove
* stacks could be implemented with another data type - what each element looks like and how they're connected aren't actually specified just the methods for adding and removing elements
* ex.) you could use a linked list to implement a stack - you would keep track of the front of a single link list and just keep adding elements on top as you went

* *L.I.F.O* - Last in, First out - the element you put on the stack when you use push is always the first one you get out when you use pop

### Stack Practice
The [Python documentation](https://docs.python.org/2/tutorial/datastructures.html#using-lists-as-stacks) shows how you can use built-in funtions to turn your Python list into a stack. `pop()` is a given function, and `append()` is equivalent to a push function.

Add a couple methods to our LinkedList class, and use that to implement a Stack. You have 4 functions below to fill in: *insertfirst, deletefirst, push, and pop*.

Think about this while you're implementing:
*Why is it easier to add an "insertfirst" function than just use "append"?*

class Element(object):
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedList(object):
    def __init__(self, head=None):
        self.head = head

    def append(self, new_element):
        current = self.head
        if self.head:
            while current.next:
                current = current.next
            current.next = new_element
        else:
            self.head = new_element

"Insert new element as the head of the LinkedList"
    def insert_first(self, new_element):
        new_element.next = self.head
        self.head = new_element

"Delete the first (head) element in the LinkedList as return it "
    def delete_first(self):
        if self.head:
            deleted_element = self.head
            temp = deleted_element.next
            self.head = temp
            return deleted_element
        else:
            return None

class Stack(object):
    def __init__(self,top=None):
        self.ll = LinkedList(top)

"Push(add) a new element onto the top of the stack"
    def push(self, new_element):
        self.ll.insert_first(new_element)
        
"Pop(remove) the first element off the top of the stack and return it"
    def pop(self):
        return self.ll.delete_first()
   
# Test cases
# Set up some Elements
e1 = Element(1)
e2 = Element(2)
e3 = Element(3)
e4 = Element(4)

# Start setting up a Stack
stack = Stack(e1)

# Test stack functionality
stack.push(e2)
stack.push(e3)
print stack.pop().value
print stack.pop().value
print stack.pop().value
print stack.pop()
stack.push(e4)
print stack.pop().value

### Queues
* Queues are a first in first out structure (F.I.F.O) - opposite to stacks
* The oldest element comes out first
* The first/oldest element in a queue is called the *head*
* The last/newest element in the queue is called the *tail*
* *Enqueue* - Add an element to the tail
* *Dequeue* - Remove the head element
* *Peek* - Allows you to look at the head element but doesn't remove it
* *Priority Queue* you assign a numerical property when you insert it into the queue
* When you dequeue, you remove the element with the highest priority

### Queue Practice
Queue's are mentioned in [Python's documentation](https://docs.python.org/2/tutorial/datastructures.html#using-lists-as-queues). Examine the code below:

from collections import deque

From a library called `collections`, you can import a package called `deque`. A deque is a double-ended queue. You can enqueue on either end, but in the example you only enqueue one way and treat it as a normal queue.

Make a Queue class using a list! Hint: You can use any Python list method you'd like! Try to write each one in as few lines as possible. Make sure you pass the test cases too!

class Queue(object):
    def __init__(self, head=None):
        self.storage = [head]

    def enqueue(self, new_element):
        self.storage.append(new_element)

    def peek(self):
        return self.storage[0]

    def dequeue(self):
        return self.storage.pop(0)

# Setup
q = Queue(1)
q.enqueue(2)
q.enqueue(3)

# Test peek
# Should be 1
print q.peek()

# Test dequeue
# Should be 1
print q.dequeue()

# Test enqueue
q.enqueue(4)
# Should be 2
print q.dequeue()
# Should be 3
print q.dequeue()
# Should be 4
print q.dequeue()
q.enqueue(5)
# Should be 5
print q.peek()

`{%hackmd theme-dark %}`