- Arrays are the building blocks of data structures
- To find the size of the the array we use .length()
- The size of an array needs to be declared
- You can think of the data structure as boxes with objects inside ordered beggining at index 0
- An array can contains primitives (int,char,double,long etc..) As well as objects (non-primitves)
Java: One Dimensional Arrays
- Quick Lookups: Retrieiving an element at a given index takes O(1) regardless if the array has a length of 1 or a 1,000,000,000
- Appending is quick: Adding a new element to the end of the array take O(1) time
- Fixed size: When creating an array you have to decide how many elements are going to be stored.
- Inserting Elements and Deleting : In order to manipulate an element in the array you need to scoot/swap elements our worst case scenario can take O(n) time
Advantages:
Disadvantages:
Inserting
To insert a new element in the array, we need to first make space by scooting from the index we are inserting into
Deleting
To delete an element we need to fill the gap by scooting all the elements after.
---------------------------------------------------------------------------------------------------------------------------------------------Declaring an array looks something like this.
First declare type, then the name.
type var-name[];
type[] var-name;
In-Place Algorithm
An in-place function manipulates the data structure without the help of an external data structure handling the input, the changes are made internally which can be useful for memory, and space effeciency. Ussually has an O(1) space cost
Be very very careful though to alter the source, which can impact code outside the function that may be coupled to that array
Though there is a need for creating additional variables that are O(1) space
Dynamic Array
A dynamic array is an array that has automatic resizing
No more specifying the number of elements ahead of time.
- Fast lookups : Just like daddy arrays retrieving the element at a given index takes O(1) time