📏 Arrays

👉 What is an Array?

An array is a fundamental data structure that stores a collection of items, typically of the same type, in a contiguous block of memory. Each item, or element, is identified by an index or a key, allowing for direct calculation of its position in memory.

• Key Feature: The ability to access any element directly using its index. This is known as random access.
• Structure: Think of it as a set of numbered boxes, where each box holds one item and you can jump to any box if you know its number.

🐍 Arrays in Python

In Python, the most common implementation of an array is the built-in list type. It’s important to know that a Python list is actually a dynamic array, not a traditional fixed-size array. This means it can automatically resize itself when you add or remove elements.

• Dynamic Arrays (list): The default and most flexible array-like structure in Python.
• array module: Python also has an array module that provides space-efficient storage of basic C-style data types like integers and floats. These are type-constrained and use less memory than lists.

⭐ Basic Operations & Complexity (on Python Lists)

Understanding the efficiency of common operations is key to using arrays effectively.

• Access by Index: Reading or writing to an index (e.g., my_list[i]).

  • Complexity: O(1) (Constant time)

• Insertion/Deletion at the End: Using .append() or .pop().

  • Complexity: O(1) (Amortized constant time)

• Insertion/Deletion at the Beginning/Middle: Using .insert() or .pop(0).

  • Complexity: O(n) (Linear time), because all subsequent elements must be shifted.

• Search: Finding an element in the list (e.g., value in my_list).

  • Complexity: O(n) (Linear time), as you may need to check every element in the worst case.

👍 Advantages

• Fast Access: Reading elements by index is extremely fast (O(1)).
• Memory Efficiency: Good cache locality since elements are stored contiguously, which can improve performance.

👎 Disadvantages

• Slow Inserts/Deletes: Adding or removing elements from anywhere other than the end is slow (O(n)).
• Fixed Size (in traditional arrays): While Python’s list handles this automatically, traditional arrays in languages like C or Java have a fixed size and require creating a new, larger array to grow.