What is a Data Structure

A data structure is a way of organizing and storing data in a computer so that it can be used efficiently. Choosing the right data structure determines how fast your program runs.

Why Data Structures Matter

Imagine you have millions of data items to search through. Without the right data structure, a search can take a very long time. With the correct data structure, the same search can finish in milliseconds.

Abstraction vs Concrete

• Abstract data structure: The logical definition of the operations that can be performed (e.g., Stack, Queue, Map).
• Concrete data structure: A real implementation in memory (e.g., Array, Linked List, Hash Table).

One abstraction can have many concrete implementations.

Data Structure Classification

Time Complexity

Time complexity measures how quickly an operation completes as the amount of data grows. Big O notation is used to describe it:

• O(1): Constant, unaffected by the amount of data.
• O(log n): Logarithmic, very fast.
• O(n): Linear, proportional to the amount of data.
• O(n log n): Slower than linear.
• O(n²): Quadratic, slow for large amounts of data.

# Simple example: finding an element
# O(n) - linear search
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# O(log n) - binary search (data must be sorted)
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

Choosing the right data structure is the theme of this entire tutorial. Let's start with the most basic data structure: the Array.