| Home | Thoughts

Arrays & Strings

November 23, 2020

    Advantages:

  1. 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
  2. Appending is quick: Adding a new element to the end of the array take O(1) time
  3. Disadvantages:

  4. Fixed size: When creating an array you have to decide how many elements are going to be stored.
  5. 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

Inserting

insert-array

To insert a new element in the array, we need to first make space by scooting from the index we are inserting into

Deleting

delete-array

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.