//********************************************************************//
//**************Arrays & ArrayLists - January 11th, 2017*************//
//******************************************************************//

-Well, any class starting with the Pokemon theme song can't be too bad!
-"Saikrishna Slides" (PowerPoint presentations from past TA) are available on T-Square
-------------------------------------------------------

-NOTE: "Big-O" notation CAN refer to how much space/memory an algorithm utilizes; THIS IS NOT THE DEFINITION WE USE
    -In THIS course, BIG-O notation is an "algorithmic complexity" measure of the WORST-CASE RUNTIME for a particular algorithm
        -e.g., O(n), O(nlog(n)), O(n!), etc.
    -Determined by the degree of the polynomial; O(2n) is still considered O(n), since it runs in linear time

-So, an ARRAY is a sequenced collection of variables, ALL OF THE SAME TYPE; each variable is called a CELL, and each "cell" has an index that marks its location (0, 1, 2, 3, ...)
    -The value stored in an array's cell is called an "element" of the array
    -If you know the index, accessing a particular element takes O(1)
-FOR AN ARRAY, THE CAPACITY DOES NOT EQUAL THE SIZE!!!
    -"Capacity" is the length of the array, INCLUDING null / empty cells
    -The "Size" is the number of elements within the array (check this???)
        -Confusingly, the Java ".length" variable actually gives you the capacity :(

-So, we can declare an array in a few ways:
    -Array "literal" method: int[] array = {1, 2, 3, 4}; //literally just list elements
    -Declaring it's size, then filling it: int[] array = new int[10];
-Array can store Primitives, OBJECTs, OR References to objects
    -Pretty versatile! BUT, Arrays have one big downside: They're completely static (i.e. can't be resized)

-ARRAYLISTS, on the other hand, CAN be resized, but CAN ONLY STORE OBJECTS (primitives are converted via "wrapper classes")

-Arrays can be used as a "backing structure" for the list; when it fills up, the array is resized by creating a new, larger-capacity array, then COPYING all of the elements from the old array over (USUAL METHOD; there are other possibilities)
    -This copying process takes O(n) time, which is a LOT if you're dealing with large data sets
-To ADD an element to, say, the middle of the ArrayList (index "N"), once we have a "Backing Array" with enough space for the new element, we shift ALL of the elements in front of the "n" index forward one space, then put the new element in the (now-empty) "n" space
    -Runtime-wise, this is O(# elements) + O(1) = O(# elements) = O(N)
    -So, adding something to the front, we have to move EVERYTHING forward
    -Adding to the back, we just put the element at the "back" of the array (the first null cell of the array)

-So, the FULL procedure for adding is:
    if (size >= array.length)
        resize array
    for (i = Size - 1, i > indextoPlace, i++)
        move entry forward one space

-REMOVING an element, we have to move all of the elements in the list BACKWARDS to "fill the gap," UNLESS we remove the last element, of course

-So, for an ArrayList:
    -Accessing elements takes O(1)
    -Searching, inserting, or removing from the ArrayList takes O(n) time, UNLESS adding / removing from the back, which takes O(1) time
-ArrayLists are EXTREMELY useful for retrieving information QUICKLYU, but, since it takes so much time to resize them, they're NOT that great for situations where we're adding/removing elements rapidly ("extensively manipulating the data")

-So, ArrayLists perform poorly when we have to rapidly manipulate our data; who shall be our knight in shining armor to rescue us from this foul conundrum? How about a LINKED LIST!

-"Linked Lists" are composed of "Nodes", each of which has two parts:
    -"Data", which contains all of the "useful information" for the node (e.g. the object stored there)
    -A pointer "next" to the next LinkedList

    -node example:   |-DATA | NEXT-|-->

    -example of the chain:
        |10| -|--> |5| -|--> |17| -|-->

-HOWEVER, we have nothing pointing to the first element, so let's have a reference/pointer to the first LinkedList called "HEAD", so we can access the LinkedList via the first element
    -We know we're at the end of the list when the "next" pointer is null

-So, we have to go through the WHOLE LinkedList to access an element, so getting an Element is O(n) - WORSE than ArrayLists
-Searching takes O(n), which is the same as an ArrayList...
-...BUT, ADDING a node to the front of the LinkedList is done by just creating a new Node, having it's "next" reference point to the FIRST node (the "HEAD"), then having it become the first node by having the HEAD variable point to it instead
    -This is CONSTANT TIME: O(1)!!!! (1 unit of time to create the node, 1 unit to redirect the pointer, 1 unit to redirect the head)
    -Keep in mind, of course, this is for adding to the front only
-Adding OR removing to the BACK, however, takes O(n) time, since we have to iterate through the whole list first to find the back :(

-If the HEAD variable is redirected to the new 1st node, which DOESN'T point to the old first node, then the linked list will be automatically garbage collected, since there's suddenly no way to reach it / no references in the code