Introduction to Algorithms and Data Structures

1. Basic Concepts

What is a Data Structure?

  • A way of organizing and storing data efficiently.

  • Built from primitive data types (e.g., int, char) or user-defined data types.

What is an Algorithm?

  • A step-by-step process to manipulate data and solve problems.

  • Must be finite, provide an output, and follow a structured approach.

2. Abstract Data Types (ADTs)

  • Definition: Logical description of data storage and operations without implementation details.

  • Examples:

    • Stack (LIFO - Last In, First Out)

      • push() – Adds an item.

      • pop() – Removes and returns the last item.

      • empty() – Checks if the stack is empty.

    • Queue (FIFO - First In, First Out)

      • enqueue() – Adds an item.

      • dequeue() – Removes and returns the first item.

    • Other ADTs: Linked lists, priority queues, trees, graphs, hash tables.

3. ADTs in Programming Languages

Language

ADT Implementation

Python

Built-in: list, tuple, dict, set. Extra: collections module.

C++

No built-in ADTs, but STL (vector, queue, map, etc.) supports them.

Java

Provides ADTs via java.util (LinkedList, Stack, Queue, etc.).

Go

Basic support for arrays, slices, and maps. Other ADTs via struct.

4. Linear vs. Non-Linear Data Structures

Linear Structures (Sequential Order)

  • Array: Fixed-size collection of elements.

  • Linked List: Sequence of nodes pointing to the next.

  • Stack: LIFO structure.

  • Queue: FIFO structure.

Non-Linear Structures (No Sequential Order)

  • Tree: Hierarchical data structure (e.g., binary tree).

  • Graph: Consists of vertices (nodes) and edges (connections).

5. Static vs. Dynamic Data Structures

Type

Description

Example

Static

Fixed size, declared at creation.

Arrays

Dynamic

Can grow/shrink as needed.

Lists, linked lists

  • Memory fragmentation occurs when dynamic structures continuously allocate/deallocate memory.

6. Common Operations on Data Structures

  • Traversing: Visiting all elements (e.g., tree traversal).

  • Searching: Finding an element using a key.

  • Modifying: Adding/removing elements.