Introduction to Data Structures

# CHAPTER 1

Introduction to Data Structures #

1. Introduction #

2. Learning Objectives #

• Define what a data structure is and explain why it is essential.

• Differentiate between Primitive and Non-Primitive data types.

• Classify Linear vs. Non-Linear data structures.

• Understand real-world applications of various data structures in software engineering.

3. Why Data Structures Matter #

• Speed: Searching through 1 million unsorted customer records takes time. Using a data structure like a *Hash Table* reduces search time from seconds to milliseconds.

• Memory Efficiency: If you need to store temporary task executions, using a *Stack* ensures you are using memory predictably and efficiently.

• Interview Success: Every major tech company (FAANG/MAANG) tests Data Structures and Algorithms (DSA) extensively during interviews because they demonstrate a candidate's ability to solve complex problems efficiently.

4. Classification of Data Structures #

#### 4.1 Primitive Data Structures These are the basic data types natively supported by the programming language. They hold a single value.

• Integer (int): Whole numbers.

• Float (float): Decimal numbers.

• Character (char): Single letters or symbols.

• Boolean (bool): True or False.

#### 4.2 Non-Primitive Data Structures These are complex structures created using primitive data types. They are designed to hold multiple values. They are further divided into Linear and Non-Linear structures.

5. Linear vs Non-Linear Data Structures #

#### 5.1 Linear Data Structures Data elements are arranged sequentially (in a straight line). Each element is attached to its previous and next adjacent elements. Memory is often traversed in a single run.

• Arrays: Elements stored in contiguous memory locations.

• Linked Lists: Elements stored randomly in memory but linked via pointers.

• Stacks: LIFO (Last In, First Out) structure. Think of a stack of plates.

• Queues: FIFO (First In, First Out) structure. Think of a line at a ticket counter.

Visual Representation of a Linear Structure (Array):

Index:  [0]   [1]   [2]   [3]
Data:  | 10 | 25 | 30 | 45 |

#### 5.2 Non-Linear Data Structures Data elements are not arranged sequentially. An element can be connected to multiple other elements. Memory traversal involves multiple paths.

• Trees: Hierarchical structure with a root node and child nodes (e.g., Folder structure in your OS).

• Graphs: A network of interconnected nodes (e.g., Google Maps, Facebook Friends network).

Visual Representation of a Non-Linear Structure (Tree):

        [Root]
       /      \
   [Node A]  [Node B]
    /    \
[Leaf 1][Leaf 2]

6. Real-World Applications #

• Arrays: Storing pixels of an image.

• Stacks: The "Undo" mechanism in Microsoft Word or web browsers.

• Queues: Printer job scheduling; CPU task scheduling.

• Linked Lists: Implementing music player playlists (Next/Previous song).

• Trees: Auto-complete dictionaries, HTML DOM manipulation.

• Graphs: GPS navigation systems finding the shortest path.

7. Mini Project: Student Record Organizer Structure #

// C Example: Using a struct
#include <stdio.h>

struct Student {
    int id;
    char grade;
    float gpa;
};

int main() {
    struct Student s1 = {101, &#039;A&#039;, 3.8};
    printf("Student %d has GPA: %.1f\n", s1.id, s1.gpa);
    return 0;
}

// C++ Example: Using a class/struct
#include <iostream>
using namespace std;

struct Student {
    int id;
    char grade;
    float gpa;
};

int main() {
    Student s1 = {101, &#039;A&#039;, 3.8};
    cout << "Student " << s1.id << " has GPA: " << s1.gpa << endl;
    return 0;
}

// Java Example: Using a Class
public class Student {
    int id;
    char grade;
    float gpa;

    public Student(int id, char grade, float gpa) {
        this.id = id;
        this.grade = grade;
        this.gpa = gpa;
    }

    public static void main(String[] args) {
        Student s1 = new Student(101, 'A', 3.8f);
        System.out.println("Student " + s1.id + " has GPA: " + s1.gpa);
    }
}

# Python Example: Using a Class
class Student:
    def __init__(self, student_id, grade, gpa):
        self.id = student_id
        self.grade = grade
        self.gpa = gpa

s1 = Student(101, 'A', 3.8)
print(f"Student {s1.id} has GPA: {s1.gpa}")

8. Complexity Analysis (High-Level) #

9. Common Mistakes #

• Assuming arrays solve everything: Beginners often use standard Arrays for every problem. If you need to constantly insert data at the *beginning* of a massive list, an Array will physically move every other element, causing massive performance lag. A Linked List handles this instantly.

• Ignoring Memory Allocation: High-level languages like Python and Java hide memory management. However, not understanding how data is mapped to physical RAM will lead to highly inefficient software designs.

10. Best Practices #

• Data Structure drives Algorithm: Always pick the Data Structure *before* writing the Algorithm. The structure of the data heavily dictates how efficient the algorithm can be.

• Understand the Trade-offs: There is no "perfect" data structure. A Hash Map is incredibly fast for searching, but terrible for maintaining sorted order. A Tree maintains order, but is slower to search than a Hash Map. Engineering is about trade-offs.

11. Exercises #

1. 1. Categorize the following as Primitive or Non-Primitive: int, Array, float, Graph, Tree, boolean.

1. 2. Categorize the following as Linear or Non-Linear: Linked List, Tree, Stack, Graph, Queue.

1. 3. Provide one real-world software feature that would utilize a Queue.

12. MCQs with Answers #

13. Interview Preparation #

• *Conceptual:* Contrast Linear and Non-Linear Data Structures. Provide two examples of each and explain how memory traversal differs between them.

• *Conceptual:* Describe a scenario where you would explicitly choose a Queue over a Stack.

• *Conceptual:* What is the fundamental difference between a Primitive and a Non-Primitive data type? How are Non-Primitives physically constructed in memory?

Common Pitfalls:

• Using colloquial terms instead of computer science terminology during interviews (e.g., calling a "Tree" a "List with branches"). Be precise with your vocabulary.

14. FAQs #

15. Summary #

16. Next Chapter Recommendation #