Data exam

Here's a detailed study set for your data structures class based on your worksheets and requested topics:

Data Structures Study Set

Fundamentals

  • Data Structure: A systematic way of organizing and accessing data.

  • Algorithm: A generic step-by-step set of instructions for solving a problem.

  • Program: An implementation of an algorithm in code.

Abstract Data Types (ADTs)

  • ADT (Abstract Data Type): A theoretical model of a data structure that specifies what operations are allowed but not how they are implemented.

Big O Notation

  • Big O Notation: Describes the worst-case complexity of an algorithm.

    • O(1): Constant time – operations take the same time regardless of input size.

    • O(n): Linear time – performance scales directly with input size.

    • O(n²): Quadratic time – performance scales with the square of input size.

    • O(log n): Logarithmic time – performance scales logarithmically with input size.

    • O(bⁿ): Exponential time – performance doubles with each additional input.

    • O(n!): Factorial time – performance grows extremely fast with input size.

Python Object-Oriented Concepts

  • Inheritance: A class can inherit attributes and methods from another class.

  • Constructor (__init__): A special function that initializes an object.

  • Import: Brings in external modules to use functions or classes.

  • Functions: Blocks of reusable code that perform a task.

  • Access Control:

    • Public attributes (self.attribute): Accessible from anywhere.

    • Protected attributes (self._attribute): Conventionally private but still accessible.

    • Private attributes (self.__attribute): Name-mangled to prevent direct access.

  • __str__ Method: Defines how an object is represented as a string.

  • Naming Conventions: Use snake_case for variables/functions and PascalCase for class names.

  • self Keyword: Refers to the instance of the class.

Stack (LIFO - Last In, First Out)

  • Functions:

    • push(item): Adds an item to the top.

    • pop(): Removes and returns the top item.

    • peek(): Returns the top item without removing it.

    • size(): Returns the number of elements.

    • is_empty(): Returns True if stack is empty.

Queue (FIFO - First In, First Out)

  • Functions:

    • enqueue(item): Adds an item to the back.

    • dequeue(): Removes and returns the front item.

    • size(): Returns the number of elements.

    • is_empty(): Returns True if queue is empty.

Deque (Double-Ended Queue)

  • Functions:

    • add_front(item): Adds an item to the front.

    • add_rear(item): Adds an item to the back.

    • remove_front(): Removes and returns the front item.

    • remove_rear(): Removes and returns the back item.

    • size(): Returns the number of elements.

    • is_empty(): Returns True if deque is empty.

Node (Basic Building Block for Linked Structures)

  • Attributes:

    • data: Stores the value of the node.

    • next: Points to the next node in a linked list.

Let me know if you need any modifications or explanations! 😊