Definition: Arrays is a data structure that is structured as a contiguous memory spaces for data values.

Types

• Static arrays
• Dynamic arrays

Common operations

• Access
• Set
• Traverse/Search
• Copy
• Insert
  • at beginning
  • at end
  • somewhere in middle
• Remove
  • at beginning
  • at end
  • somewhere in middle

Big O

Action	Time	Space
Access	O(1)	O(1)
Set	O(1)	O(1)
Traverse/Search	O(n)	O(1)
Copy	O(n)	O(n)
Insert
at the beginning	O(n)	O(1)
at the end	O(1)	O(1)
somewhere in middle	O(n)	O(1)
Remove
at the beginning	O(n)	O(1)
at the end	O(1)	O(1)
somewhere in middle	O(n)	O(1)