Arrays Flashcards
Definition
it’s a contiguous area of memory consisting of equal sized elements indexed by contiguous integers
what is special about an array?
it has constant time access and write O(1)
how to calculate the position of an element in an array
array_add + element_size * (i - first_element)
first_element can be 0 or 1
how are multi-dimensional arrays are laid out in memory?
Row major or column major
Times for common operations? Beginning , middle , end to add or remove element
Add Remove Beginning O(N) O(N) because we need to shift all the elements Middle O(N) O(N) because again we need to shift elements End O(1) O(1)
Characteristics Of simple array?
it’s a collection of same type elements
Fixed size
Zero indexed
Same Data type
why choose a simple array?
because the more constraints u have on your data structure the smaller it will get meaning it will be faster
What are arrays in java?
it’s an object consisting of a numbered list of variable each one can be a primitive type or a reference to an object
what is a multidimensional array?
it’s an array of arrays
what is a dynamic array?
instead of storing the size of the array we just keep track of the pointer pointing to the array and when we need to resize the array we just make it point to another location of memory but we must simulate it like a real array meaning the normal operations like get and set and remove to be of constant time
what are the common implementations of dynamic array in c++ , java , python
vector , arraylist , list and python doesn’t have static arrays
what r the runtimes of dynamic arrays like get , set , pushback , remove , size
O(1) , O(1) , O(N) , O(N) , O(1)
what is a jagged array?
it’s like a multidimensional array but each row has a different number of data and it’s uses like different days of each month in two dimensional array
what are the five requirements in any data structure?
access , insert , delete , find , sort
do programming languages always use the same sorting algorithm for the array?
No, they look at the size of the array like .NET uses insertion , heap , quick depending on the size of the array
what are the general types of sorting arrays?
u can do an in place sorting or copy the entire array to another one
can u sort a custom array of objects using the language built in functionality?
No, u must provide an implementation of your own sorting algorithm
how to search in an array?
Linear which is O(N) and sometimes when u search for something u move the variable found to the beginning which will make the algorithm a little bit better and most built in searching uses this and there is binary search which is O(LOG N)
how to do a linear search?
u go over every item in the array checking for the value
how to do binary search?
u can’t do a binary search on an unordered data set …. u go to the middle of the array if the number is larger u move to the right half and discard the left until u find an element or u don’t
