Lesson 1 - Introduction to Data Structures

A bookshelf

Real world example of an array

data structure

is a way to store and organize data in a computer so that it can be used efficiently.

data structure

is a mathematical or logical way of organizing data in memory that considers not only the items stored but also the relationship of each item to the other items.”

A line of people

Real world example of an queue

A stack of plates

Real world example of an stack

A treasure hunt with clues

Real world example of a linked list

Efficient Problem Solving

Optimal Resource Usage

Coding Interviews and Competitions

Scalable Software

Why is DSA Important?

Efficient Problem Solving:

DSA provides tools to solve problems efficiently by choosing the right data structure and algorithm for the job.

Optimal Resource Usage

Helps programs use memory and processing time effectively, ensuring minimal resource consumption.

Coding Interviews and Competitions

DSA knowledge is essential for technical interviews and programming contests.

Scalable Software

Well-chosen data structures allow applications to handle large amounts of data without slowing down.

time, memory, and simplicity

what are the constraints of the system?

Linear and Non-Linear data structures.

Types of Data Structures

Linear Data Structures

data elements are arranged in a sequential order, and each element is connected to its previous and next element (except the first and last).

Array:

A fixed-size, ordered collection of elements of the same data type, stored in contiguous memory locations and accessed using an index.

Linked List

A collection of nodes where each node contains data and a reference (pointer) to the next node, allowing dynamic memory allocation.

Stack

A linear structure that follows the Last-In-First-Out (LIFO) principle. Elements are added and removed from only one end (the top).

Queue

A linear structure that follows the First-In-First-Out (FIFO) principle. Elements are added at the rear and removed from the front.

Non-Linear Data Structures

data elements are not arranged sequentially. Instead, elements may be connected to multiple other elements, forming hierarchical or networked relationships.

Tree

A hierarchical structure consisting of nodes connected by edges, with one node designated as the root.

Binary Trees, Binary Search Trees, AVL Trees, and Heaps.

Examples of trees

Graphs

A collection of nodes (vertices) connected by edges, used to represent networks such as social connections, maps, and web page links.

directed or undirected, weighted or unweighted.

Types of graphs

social networks, maps, web page links

Examples of graphs

Hash Table

A structure that maps keys to values using a hash function, allowing for very fast data retrieval, insertion, and deletion (on average, constant time).

data type

defines the kind of value a variable can hold and the set of operations that can be performed on it.

Primitive (built-in) and Non-Primitive (derived/user-defined) types.

Data types are generally classified into?

Primitive data types

the basic, built-in data types provided directly by a programming language. They are not composed of other data types and typically represent a single value.

integer (int)

whole numbers without fraction/decimal component.

floating-point (float/double)

numbers that include fractional/decimal component

character (char)

a single letter, digit, or symbol.

boolean (bool)

represents one of two values: true or false

Non-primitive data types

built using primitive data types (or other non-primitive types) and can store collections of values or more complex structures.

array, structure/record, union, class/abstract data type

List non-primitive data types

structure/record

a user defined type that groups related fields, which may be of different data types.

union

a special data type that allows storing different data types in the same memory location (only one at a time)

class/abstract data type

a blueprint that combines data (attributes) and behavior (methods/operations) into a single unit, often used in object-oriented programming.

Time and space complexity

metrics used in Data Structures and Algorithms (DSA) to measure the performance, efficiency and scalability of an algorithm

Evaluate Efficiency,Compare Algorithms,Scalability

Why Complexity Analysis?

Evaluate Efficiency

Complexity analysis helps measure an algorithm's efficiency by evaluating running time (time complexity) and memory usage (space complexity).

Compare Algorithms

It helps compare different algorithms and choose the most optimal one for a given problem.

Scalability

It ensures that an algorithm can handle large inputs efficiently without degrading performance.

Best Case O(1)

The target is found immediately (e.g. it is the very first element checked.) This gives the minimum possible time.

Average Case - O(n)

The target is found somewhere in the middle of the data on average—this reflects the expected running time.

Worst case - O(n)

The target is found at the very last position, or not found at all—this represents the maximum possible time.

Big-O Notation

describes how an algorithm's running time or space usage grows as input size

increases.

Common time complexities

these notations describe how the running time of an algorithm grows with the input size(n)

Constant - O(1)

takes the same amount of time, no matter how much data there is.

Logarithmic - O(log n)

reduce the amount of data to check each step. It is very fast for large data.

binary search

example of logarithmic

linear - O(n)

the time increases as the number of items increases. It may need to check each item.

searching through a list one by one

example of linear

linearithmic - O(n log n)

does more work than O(n), but is still efficient for large data.

merge sort

example of linearithmic

Quadratic - O(n²)

the amount of work grows much faster as the data gets larger, often involving two loops.

comparing every item with every other item

example of quadratic