1 Data Structures
Data structures are specialized formats for organizing, processing, retrieving, and storing data. They define the logical and physical relationships between data elements, enabling efficient algorithms and optimized memory usage. Data structures are typically classified by their organization and access patterns.
1.1 Primitive Data Structures
Primitive data structures are the most basic types provided by programming languages, representing single values. They are the building blocks for more complex structures and are directly supported at the hardware level.
1.1.1 Integer, Float, Character, Boolean
- Integer: Represents whole numbers, both positive and negative, without fractional parts. Common sizes include 8-bit, 16-bit, 32-bit, and 64-bit, with signed and unsigned variants.
- Float: Represents real numbers with fractional parts, typically using IEEE 754 standard formats (single precision, double precision). Used for scientific and graphical computations.
- Character: Represents a single textual symbol, usually stored as an integer code (e.g., ASCII or Unicode). In many languages, characters are 8 or 16 bits.
- Boolean: Represents logical truth values:
trueandfalse. Often occupies 1 byte, though bit-level storage is possible.
1.2 Linear Data Structures
Linear data structures arrange elements sequentially, where each element has a unique predecessor (except the first) and successor (except the last). Access and traversal follow a linear order.
1.2.1 Arrays
An array is a fixed-size collection of elements of the same type, stored in contiguous memory locations. Elements are accessed via an index, enabling constant-time access (O(1)) but linear insertion and deletion (O(n)). Arrays support both one-dimensional (vectors) and multi-dimensional (matrices) arrangements.
1.2.2 Linked Lists
A linked list is a dynamic collection of nodes, each containing data and a reference to the next node. It allows efficient insertion and deletion at arbitrary positions (O(1) given a pointer) but requires sequential traversal for access (O(n)). Memory is allocated per node.
1.2.2.1 Singly Linked Lists
In a singly linked list, each node contains a single pointer to the next node. Traversal is unidirectional from head to tail. Operations like insertion at the head or removal of the head node are O(1), while removing a node with known predecessor is O(1); otherwise O(n).
1.2.2.2 Doubly Linked Lists
Doubly linked lists extend singly linked lists by adding a pointer to the previous node. This enables bidirectional traversal and O(1) deletion of a node given a pointer to it. Disadvantage: additional memory per pointer and slightly more complex maintenance.
1.2.3 Stacks
A stack is a Last-In-First-Out (LIFO) linear structure. Operations push (insert) and pop (remove) occur only at one end, called the top. Stacks are used for function call management, expression evaluation, and undo mechanisms. They can be implemented with arrays or linked lists.
1.2.4 Queues
A queue is a First-In-First-Out (FIFO) linear structure. Elements are inserted at the rear and removed from the front. Variations include circular queues (efficient fixed-size implementations) and priority queues (order by priority). Queues are used in scheduling, breadth-first search, and buffering.
1.3 Non-linear Data Structures
Non-linear data structures do not impose a sequential order. Elements may have multiple successors and/or predecessors, forming hierarchical or interconnected relationships.
1.3.1 Trees
A tree is a hierarchical structure consisting of nodes connected by edges, with a root node and no cycles. Each node has zero or more child nodes. Trees are used for representing hierarchies, sorted data, and parser syntax.
1.3.1.1 Binary Trees
A binary tree is a tree where each node has at most two children, typically called left and right. Variants include full binary trees (every node has 0 or 2 children), complete binary trees (all levels filled except possibly the last), and perfect binary trees (all internal nodes have two children and leaves are at same depth).
1.3.1.2 Binary Search Trees
A binary search tree (BST) is a binary tree where, for every node, all values in the left subtree are less than the node's value, and all values in the right subtree are greater. This property enables fast search, insertion, and deletion (O(log n) on average), but worst-case degradation to O(n) occurs with unbalanced insertion sequences.
###### 1.3.1.2.1 Balanced BST (AVL, Red-Black)
Balanced BSTs maintain near-optimal height by enforcing balancing rules after insertions and deletions.
- AVL Tree: Self-balancing through rotations that maintain height difference of at most 1 between left and right subtrees. Guarantees O(log n) operations but incurs cost of frequent rotations.
- Red-Black Tree: Uses color bits (red/black) and five invariants to ensure the longest path is no more than twice the shortest path. Offers slightly more relaxed balancing with fewer rotations than AVL, used in many standard libraries (e.g., Java TreeMap).
1.3.2 Graphs
A graph is a set of vertices (nodes) and edges connecting them. Graphs model networks, relationships, and many real-world problems. They may be cyclic or acyclic, connected or disconnected.
1.3.2.1 Directed vs Undirected
- Directed Graph (Digraph): Edges have a direction, going from one vertex to another. Example: Web page hyperlinks.
- Undirected Graph: Edges have no direction, representing symmetric relationships. Example: Friendship networks.
1.3.2.2 Graph Representations
- Adjacency Matrix: A 2D array where
matrix[i][j]indicates whether an edge exists between vertices i and j. O(1) edge lookup but O(V²) memory. - Adjacency List: Each vertex maintains a list of its neighbors. More compact for sparse graphs; edge lookup O(degree).
- Edge List: A list of all edges as pairs (u,v). Used for specialized algorithms (e.g., Kruskal's).
1.4 Hash-based Structures
Hash-based structures use a hash function to map keys to indices, enabling average-case constant-time access (O(1)) for insertion, deletion, and lookup.
1.4.1 Hash Tables
A hash table (or hash map) stores key-value pairs. The hash function computes an index from the key. Collisions (multiple keys mapping to same index) are resolved via chaining (linked lists) or open addressing (linear probing, quadratic probing, double hashing). Load factor affects performance; rehashing may be triggered when the load exceeds a threshold.
1.4.2 Hash Sets
A hash set is a collection of unique elements based on a hash table, but without associated values. It provides fast membership testing, insertion, and deletion. Intersection, union, and difference operations can be implemented efficiently. Both mutable and immutable variants exist in many libraries.
2 Program Structures
Program structures define how code is organized, executed, and managed within a software system. They encompass control flow, modular decomposition, and error handling mechanisms.
2.1 Control Structures
Control structures determine the order in which statements are executed, enabling decision-making and repetition.
2.1.1 Sequence
Sequence is the simplest control structure: statements execute one after another in the order they appear. It is the default flow unless altered by selection or iteration.
2.1.2 Selection (if-else, switch)
Selection structures allow branching based on conditions.
- if-else: Evaluates a Boolean expression; executes one block if true, another (if present) if false.
- switch: Selects among multiple cases based on the value of an expression. In many languages,
breakis required to prevent fallthrough. Modern languages also support pattern matching (e.g., Rustmatch, Pythonmatch).
2.1.3 Iteration (for, while)
Iteration structures repeat a block of code.
- for: Typically used when the number of iterations is known upfront (e.g., iterating over a range or collection).
- while: Continues as long as a condition is true. Entry-controlled loops may never execute if the condition is initially false.
- do-while: Executes the block at least once before checking the condition (available in C-family languages).
2.2 Modular Structures
Modular structures decompose a program into smaller, independent, and reusable units.
2.2.1 Functions and Procedures
A function (or procedure) is a named block of code that performs a specific task, can accept input parameters, and may return a value. Functions promote code reuse, abstraction, and testability. They can be pure (no side effects) or impure. Recursion is a technique where a function calls itself.
2.2.2 Classes and Objects
Classes are blueprints for creating objects—encapsulated units containing data (attributes) and behaviors (methods). They support inheritance, polymorphism, and encapsulation, forming the basis of object-oriented programming.
2.2.2.1 Inheritance
Inheritance allows a class (subclass) to derive properties and methods from another class (superclass). It promotes code reuse and establishes hierarchical relationships. Languages may support single inheritance (e.g., Java) or multiple inheritance (e.g., C++). Interfaces and mixins provide alternative ways to share behavior.
2.2.2.2 Polymorphism
Polymorphism enables objects of different classes to be treated as objects of a common superclass, typically through method overriding. It allows the same interface to have different implementations. Static polymorphism (compile-time) is achieved via method overloading or generics; dynamic polymorphism (runtime) is achieved via virtual methods.
2.2.3 Modules and Packages
Modules (in languages like Python, JavaScript) are files or namespaces that group related code. Packages are collections of modules organized in a hierarchical directory structure. They provide encapsulation, avoid naming conflicts, and facilitate large-scale code organization. Import mechanisms allow selective access to module contents.
2.3 Error Handling Structures
Error handling structures manage exceptional conditions that disrupt normal program execution.
2.3.1 Exception Handling
Exception handling uses try, catch (or except), and finally blocks. Code in the try block is monitored for exceptions. When an exception occurs, control transfers to an appropriate catch block based on exception type. The finally block executes regardless of whether an exception was thrown, ensuring cleanup. Some languages support throws declarations to propagate exceptions.
2.3.2 Error Codes
Error codes is an alternative approach where functions return status values (e.g., 0 for success, non-zero for failure). The caller checks the return value and responds accordingly. This method avoids runtime overhead but can clutter code with checks. It is common in low-level and C-style programming. Modern practices often combine error codes with error handling patterns (e.g., Go's multiple return values).
3 Architectural Structures
Architectural structures define the high-level organization of a software system, including component interactions, deployment strategies, and quality attributes.
3.1 Layered Architecture
Layered architecture organizes components into horizontal layers, each with a specific responsibility. Layers communicate only with adjacent layers, promoting separation of concerns and modifiability.
3.1.1 Presentation Layer
The presentation layer (or UI layer) handles user interaction and display. In web applications, this includes HTML, CSS, and JavaScript frontends; in desktop apps, it includes windows and controls. It delegates business logic to the next layer.
3.1.2 Business Logic Layer
The business logic layer (or domain layer) contains the core rules and workflows of the application. It processes data, enforces validations, and coordinates operations. It is independent of both presentation and data access specifics.
3.1.3 Data Access Layer
The data access layer (DAL) abstracts persistence mechanisms, such as databases, file systems, or third-party services. It provides CRUD operations and maps between object models and database schemas (e.g., via ORM tools).
3.2 Component-Based Architecture
Component-based architecture decomposes the system into reusable, self-contained components with well-defined interfaces.
3.2.1 Components and Interfaces
A component encapsulates a set of related functions and data; it communicates with other components solely through provided and required interfaces. Interfaces are contracts that specify operations and protocols. This promotes loose coupling and independent development/deployment.
3.2.2 Dependency Injection
Dependency injection (DI) is a technique where a component receives its dependencies from an external source rather than creating them internally. This increases testability and flexibility. DI frameworks (e.g., Spring, Guice) manage dependency resolution and lifecycle.
3.3 Microservices Architecture
Microservices architecture structures an application as a collection of small, independently deployable services, each focused on a single business capability.
3.3.1 Service Decomposition
Services are decomposed by business domain, often following the bounded context pattern from Domain-Driven Design. Each service owns its own data storage, development lifecycle, and scaling policies. Decomposition must balance granularity with complexity; overly fine-grained services lead to excessive network overhead.
3.3.2 Inter-Service Communication
Services communicate via lightweight protocols, commonly HTTP or messaging. Loose coupling is achieved through asynchronous communication when possible.
3.3.2.1 RESTful APIs
REST (Representational State Transfer) uses stateless HTTP requests with standard methods (GET, POST, PUT, DELETE) and resource-oriented URLs. Responses are typically in JSON or XML. REST is widely adopted due to simplicity and scalability.
3.3.2.2 Message Queues
Message queues (e.g., RabbitMQ, Apache Kafka) decouple service communication by buffering messages. Producers send messages to a queue; consumers process them asynchronously. This supports load leveling, fault tolerance, and eventual consistency.
3.4 Event-Driven Architecture
Event-driven architecture (EDA) is based on the production, detection, and reaction to events. It enables highly scalable, loosely coupled systems.
3.4.1 Event Producers and Consumers
Producers generate events (e.g., user registration, data change) and emit them without knowing who will process them. Consumers subscribe to specific event types and respond accordingly. This pattern allows dynamic addition of new consumers.
3.4.2 Event Bus
An event bus (or event broker) is the central mediator that routes events from producers to consumers. It can be an in-process messaging manager or a distributed stream platform (e.g., Apache Kafka). The bus may support filtering, transformation, ordering, and guaranteed delivery.