DS final

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.

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

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.

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.

Function

Blocks of reusable code that perform a task.

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

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle.

Queue

A queue is a linear data structure that follows the First In, First Out (FIFO) principle.

Deque

A deque is a data structure that allows insertions and deletions from both the front and back.

Node

A fundamental building block of linked data structures, consisting of a data field and a reference to the next node.

AVL Tree

A self-balancing binary search tree.

LL rotation

Needed in AVL trees when a node is left-heavy after deletion and its left child has a balance factor ≥ 0.

RR rotation

Needed in AVL trees when a node is right-heavy after deletion and its right child has a balance factor ≤ 0.

LR rotation

Needed in AVL trees when a left child is right-heavy after deletion.

RL rotation

Needed in AVL trees when a right child is left-heavy after deletion.

Balance Factor

The difference in heights between the left and right subtrees of a node.

Stable Sort

A sorting algorithm that maintains the relative order of records with equal keys.