Data Structures

1. Data Structures: Overview

Data structures are specific ways of organizing and storing data in a computer to enable efficient access and modifications.

Primitive Data Structures
- Integers, characters, floats, etc.
- Basic types directly supported by programming languages.
Non-Primitive Data Structures
- Linear Structures
  - Arrays: Fixed-size collections of elements.
  - Linked Lists: Collections of elements linked via pointers.
  - Stacks: Last-in-first-out (LIFO) storage.
  - Queues: First-in-first-out (FIFO) storage.
- Non-linear Structures
  - Trees: Hierarchical structures (e.g., binary trees, AVL trees).
  - Graphs: Collections of nodes and edges.

Basic Operations on Data Structures
- Insertion: Adding elements.
- Deletion: Removing elements.
- Traversal: Accessing elements in a systematic way.
- Searching: Finding elements (e.g., linear search, binary search).
- Sorting: Arranging elements (e.g., quicksort, mergesort).

Definition: Cache friendliness refers to how well a data structure or algorithm utilizes the CPU cache to minimize latency and improve performance.

Locality of Reference
- Temporal Locality: If a data location is accessed, it is likely to be accessed again soon.
- Spatial Locality: If a data location is accessed, nearby data locations are likely to be accessed soon.
Cache Hierarchy
- Modern CPUs have multiple cache levels (L1, L2, L3).
- Data structures should fit within cache lines to leverage fast memory access.

Contiguous Memory Allocation: Arrays are generally more cache-friendly than linked lists as they store elements in contiguous memory locations.
Data Structure Size: Smaller structures that fit in cache are preferable.
Access Patterns: Sequential access patterns (e.g., traversing an array) are usually better than random access patterns.

Efficient cache usage can reduce memory access time significantly, leading to overall faster program execution.