Data - more nodes!

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)

• Definition: A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, where the last element added is the first to be removed.

• 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)

• Definition: A queue is a linear data structure that follows the First In, First Out (FIFO) principle, where the first element added is the first to be removed.

• 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)

• Definition: A deque (double-ended queue) is a data structure that allows insertions and deletions from both the front and back.

• 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

• Definition: A node is a fundamental building block of linked data structures, consisting of a data field and a reference (pointer) to the next node.

• Attributes:

  • data: Stores the value of the node.

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

• Creating and Manipulating Nodes:

  • Creating a Node:

    class Node:
        def __init__(self, data=None):
            self.data = data
            self.next = None  # Pointer to the next node
    

  • Interacting with Nodes:

    n1 = Node("A")
    n2 = Node("B")
    n1.next = n2  # Link first node to the second
    

  • Accessing Node Data:

    print(n1.data)  # Outputs: A
    print(n1.next.data)  # Outputs: B
    

  • Adding a New Node Before Another:

    n3 = Node("C")
    n3.next = n1
    

  • Updated Linked List Diagram:

    n3 ("C") --> n1 ("A") --> n2 ("B") --> None