[[[ [] ], [], []], [node5, node6]]
Binary Tree
"root"
/ \
node1 node2
/ \ / \
node3 node4 node5 node6
Mr. Stack
First In Last Out (FILO)
push 3 -
push 2 - \ - elements of the stack
push 1 - /
_________
Mr. Stack = 3 (HEAD)
2
1
_
pop Mr. Stack -> 3 (2 is now HEAD)
pop Mr. Stack -> 2 (1 is now HEAD)
pop Mr. Stack -> 1 (HEAD is now empty)
Mr. Stack = _
Mr. Array vs Mr. Stack
Arrays have linked listed elements
Array[3] -> returns the element at the third index (which is the fourth element in the array b/c of 0 indexing).
Array = [0,1,2,3], Array[3] -> 3
item 0 "linked" -> item 1 "linked" -> item 2 "linked" -> item 3
Locating an element at index 3 for Array, is a O(n) operation, meaning it has to traverse every element in the linked list,
until it finds the element whose index value is the index we gave (3).
O(n^2) for each element n, perform another lookup
Array = [[a, b, c], [b, c, d], [c, d, e]]
Array[2][2] O(n) * O(n) = O(n^2)
So if you have a Array with 1,000,000 elements, finding the 1,000,000 element indexed in that array, will require traversing the entire Array's elements' linked list.
Stacks have stack frames, but we can only ever see and work with the Head of the stack
We can pop (which retrieves the Head).
We can push (which adds a new element as the HEAD).