Array

Characteristics

• Fixed size
• Stores similar elements
• Contiguous indices
• Stored contiguously
• Allows random access

Operations

	Add	Remove
Beginning	O(n)	O(n)
Middle	O(n)	O(n)
End	O(1)	O(1)

• Because beginning and middle require all elements after to be shifted

Pros/Cons

• Pros
  • Constant access time
  • Direct relationship between indices and pointers
• Cons
  • Expensive for adding/removing elements from the front

Dynamic Length Arrays

• Can resize automatically when full
• Resize $O(n)$
• Resize not counted in worst case