Arrays

What are arrays?

Arrays are a fundamental data structure and building block. Arrays are a fixed length container that can hold multiple values. Each value is called an element or item. All values are of a single type. Values in an array do not necessarily have to be unique. Arrays are stored in continuous memory location - no gaps.

Applications

• Strings (arrays of characters)
• Hash tables
• Indexing
• Text processing
• Image storage
• Model training

Structure

The structure of an array may be different depending on the language or the implementation. We'll keep it simple

• NAME - name of array
• TYPE - type of each element
• CAPACITY - maximum number of elements in an array
• COUNT - the number of elements in the array

Array allocation

Total allocated size

• Capacity x size of each element (TYPE) i.e int
• Set count to 0
• Array capacity is fixed
  • We can't change it once we have allocated it, we can only get rid of it

Operations

• Indexing

  • Each element can be referenced by a positive integer (index)
  • Index range is 0 to capacity - 1
  • Starts with a reference to the array i.e
  • Element is located at reference plus an index offset i.e
  • Offset is equal to index times size of each element i.e
  • Index Operator i.e
  • Complexity order O(1)
  • Array index assignment
    • Set element at a given index
    • Use the index operator to specify the index i.e
    • Replace existing element with new value i.e
    • Operation is O(1)

• Count

  • A count variable keeps track of the number of element
  • Count variable is updated depending on operations that change the count of elements in the array
  • Constant time complexity: O(1)
  • More efficient than a dynamic count function, which would be O(n)
  • Example:
    • Count variable refers to the number of elements in the array
    • Elements at or beyond the count variable are not considered

• Append

  • Place a new value at the end of an array
  • Algorithm
    1. Assign value to array with array count as index i.e
    2. Increment count i.e
  • Complexity order O(1)

• Delete

  • Delete element from an array at a specified index
  • Algorithm
    1. Overwrite the element at the index through shifting
       • Starting index is delete index plus one i.e
       • Shift element to the left i.e
       • End index is the count i.e
    2. Decrement the count variable i.e

       cases	complexity	description
       best case	O(1)	delete last element
       average case	O(n)	delete middle element
       worst case	O(n)	delete first element

• Insert

  • Insert a value at a given index in an array
  • Algorithm
    1. Make space in array by shifting elements
       • Shift to the right (descending) i.e
       • Starting index is count minus 1 i.e
       • Ending index is insert index i.e
    2. Assign value at the insert index i.e
    3. Increment count i.e

       cases	complexity	description
       best case	O(1)	insert before last element
       average case	O(n)	insert in the middle
       worst case	O(n)	insert as the first element

• Search

Complexity

Array operations complexity

Topics

• Big O notation
• Dynamic Arrays