Introduction to Data Structures

Introduction to Data Structures

An intro to the most common data structures found in day-to-day software engineering

Start

Objectives

Gain a holistic understanding of data structures and be able to answer the following questions:

• Why do we use data structures?
• What are some types of data structures & how do they work?
• What are some metrics used to measure data structure efficiency?

What is a Data Structure?

Index

Why do we need Data Structures?

This is what we will be covering in this lesson

Common Data Structures

Measuring Data Structures

Quiz

What is a Data Structure

A data structure is a way of organizing, storing, and managing data so that it can be accessed and modified efficiently. It defines the relationship between data elements and the operations that can be performed on them. They are broadly categorized into the two follow ing categories:

Non-Linear

Linear

Why do we need Data Structures?

Optimized Performance

Efficient Data Management

Considering the sheer amount of computations a computer is making, every bit of optimization matters.

Every process ran on a computer needs to process some sort of data. Without data structues, there would be no organization for it.

Essential for Computing

Certain applications and algorithms require specific data structures to be implemented. Without them, many of the common essentials wouldn't be possible.

Arrays

Fixed-sized elements stored in contiguous memory

Common Data Structures

Stacks

Usually backed by an array, they employ Last-in-First-Out principles for data storage

These are just some of the more common data structures. A more complete list can be found here

Trees

Data Structures

Hierarchical structure with nodes connecting data elements

How do we measure data structures?

We select data structures from their use cases, which has 2 main underlying factors:

Time Complexity

Space Complexity

It is important to note that data structure implementations can differ across programming languages

Review

Data Structures are an important aspect of computer science that allow us to organize, structure, and use different data elements in an efficient manner.

Evaluation

1/4

Evaluation

2/4

Evaluation

3/4

Evaluation

4/4

Thank you for completing the lesson

Time Complexity

Time complexity refers to the amount of time it takes to complete a specific action on the data structure with input size (n). It is typically expressed using Big-O notation (O-notation), which describes the worst-case scenario. Some example for actions are add, remove, etc. Some examples for time complexities are O(1), O(n), O(logn), etc.

Optimized Performance

Data Structures allow us to optimize around the intended use cases. They allow us to implement complex algorithms that further improve computational efficiency and help manage memory efficiently.

Arrays

A data structure that stores a fixed-size collection of elements, all of the same data type, in contiguous memory locations. Each element in the array is accessed using an index, starting from 0 in most programming languages.

Key Elements Include

• Fixed Size (In most languages)
• Can be 1 to 3 dimensional
• Index-Based Access (for example array[0] is the first element of the array)

• Commonly used in databases, image processing, etc.

Stacks

A stack is a linear data structure that follows the Last In, First Out (LIFO) principle, meaning the last element added to the stack is the first one to be removed. Think of a stack of plates—you add plates to the top and remove them from the top.

Key Elements Include

• LIFO Order: The last element inserted is the first to be removed.
• Restricted Access: Elements can only be added (pushed) or removed (popped) from the top of the stack

• Used in function calls for programs, undo-redo functionality, browser history management

Trees

A non-linear data structure that organizes data in a hierarchical manner. It consists of nodes connected by edges, with a root node at the top and branches extending downward.

Key Elements Include

• LIFO Order: The last element inserted is the first to be removed.
• Restricted Access: Elements can only be added (pushed) or removed (popped) from the top of the stack

• Used in function calls for programs, undo-redo functionality, browser history management

Efficient Data Management

Data Structures allow for programs to:

• Store large amounts of data in an organized way.
• Have quick access and modification of data.
• Reduce redundancy and improves performance.

Space Complexity

Space complexity measures the amount of memory required by an algorithm based on the input size n. It includes: Auxiliary Space: Extra space used by the algorithm. Input Space: Memory occupied by input data itself. It is still represented with Big-O notation similar to time complexity

Linear Data Structures

Data Structure where elements are arranged sequentially.Used in secenarios where the specific order of data needs to be maintained (music in a queue, changes in a text editor, etc.)

Non-Linear Data Structures

Data Structure where elements are arranged in a hierarchical manner.Used in secenarios where there can be multiple connections between elements (data storage in a file system, route planning for a map, etc.)