ExamCheat logoExamCheat.Search
Search topic titles and note text; enter at least 2 characters.
Algorithm Design · UNIT 1

UNIT I – LINEAR DATA STRUCTURES

2 topics · A little focus. A deeper understanding.

01INTRODUCTION TO DATA STRUCTURES

1.1 What is Data?

Data means raw facts or values that do not yet have meaning by themselves.

Example: The numbers 21, "Ravi", "MCA" are just data. They become information only when we say "Ravi is 21 years old and studies in MCA."

In a computer, data is stored in variables, and a program processes this data to produce useful information.

1.2 What is a Data Structure?

A Data Structure is a way of storing, organizing, and managing data in a computer so that it can be used efficiently.

Simple definition: A data structure is a container that holds data in a particular layout, and also defines the operations (like insert, delete, search) that can be performed on that data.

Real-life analogy: Think of a cupboard.

• If you throw all your clothes in one pile, finding a specific shirt takes a long time.
• If you organize the cupboard into shelves (shirts, pants, socks), finding anything becomes fast.

A data structure is exactly this — an organized way to keep data so operations become fast and easy.

1.3 Need of Data Structures

We need data structures because:

  1. Efficient storage – Data structures decide how memory is used efficiently.

  2. Fast searching – A well-organized structure (like a sorted array or tree) allows quick searching.

  3. Efficient insertion and deletion – Some structures (like linked lists) allow fast insertion/deletion without shifting all elements.

  4. Reusability – Once a data structure is designed, it can be reused in many programs.

  5. Managing large data – Real applications (banking systems, social media, databases) handle millions of records. Without proper data structures, this would be impossible to manage.

  6. Better algorithm design – Many algorithms are built on top of specific data structures (e.g., graph algorithms need adjacency lists, sorting algorithms need arrays).

1.4 Characteristics of a Good Data Structure

  1. Correctness – It should correctly implement its intended operations.

  2. Time Complexity – Operations should run efficiently in terms of time.

  3. Space Complexity – It should use memory efficiently.

  4. Flexibility/Robustness – It should adapt to changing amounts of data (especially dynamic structures).

1.5 Classification of Data Structures

Data structures are broadly divided into two categories:

A. Primitive Data Structures

These are the basic data types directly supported by a programming language.

Examples:

• int
• float
• char
• double
• boolean

They store a single value and are the building blocks for constructing more complex (non-primitive) data structures.

B. Non-Primitive Data Structures

These are more complex structures derived from primitive data types. They store a collection of values, either of the same type or different types.

Non-primitive data structures are further divided into:

(i) Linear Data Structures

In a linear data structure, elements are arranged in a sequential order, one after another. Each element (except the first and last) has a unique predecessor and successor.

Examples:

• Array
• Stack
• Queue
• Linked List

Real-life analogy: A queue of people standing in a line at a ticket counter — one after another.

(ii) Non-Linear Data Structures

In a non-linear data structure, elements are not arranged sequentially. Each element can be connected to multiple other elements, forming a hierarchical or networked structure.

Examples:

• Tree
• Graph

Real-life analogy: A family tree, where one person can have multiple children, and the relationship is not a simple straight line.

1.6 Static vs Dynamic Data Structures

Static Data Structure

• Memory is allocated at compile time, and the size is fixed.
• Example: Array.
• Once declared, you cannot increase or decrease its size during program execution.

Advantage: Fast access using index. Disadvantage: Memory wastage if less data is stored; overflow if more data needs to be stored than the declared size.

Dynamic Data Structure

• Memory is allocated at run time, and the size can grow or shrink as needed.
• Example: Linked List.
• Uses pointers to connect elements, so memory is used only as required.

Advantage: Efficient memory usage, flexible size. Disadvantage: Extra memory needed for pointers; access is not as fast as arrays (no direct indexing).

1.7 Real-Life Examples of Data Structures

  1. Stack → Pile of plates in a canteen (you add and remove from the top only).

  2. Queue → Line at a movie ticket counter (first person in line is served first).

  3. Tree → Organization hierarchy chart (CEO → Managers → Employees).

  4. Graph → Google Maps road network (cities connected by roads).

  5. Array → A row of lockers numbered 1 to 50.

1.8 Advantages of Using Data Structures

  1. Efficient use of memory.

  2. Faster data processing.

  3. Efficient searching and sorting.

  4. Reusability of code.

  5. Better data management for large-scale applications.

1.9 Applications of Data Structures

  1. Operating Systems (process scheduling uses queues).

  2. Databases (indexing uses trees).

  3. Compilers (syntax parsing uses stacks).

  4. Networking (routing uses graphs).

  5. Artificial Intelligence (search trees, decision trees).

  6. Web browsers (history uses stacks).

02ABSTRACT DATA TYPES (ADT)

2.1 Definition

An Abstract Data Type (ADT) is a mathematical/logical model of a data structure that defines:

  1. What data it holds.

  2. What operations can be performed on it.

...but it does not define how these operations are implemented internally.

In simple words: ADT tells you WHAT a data structure does, not HOW it does it.

2.2 Real-Life Analogy

Think about a TV remote control.

• You know that pressing the "Volume Up" button increases volume (this is the operation/interface).
• You do NOT need to know the internal circuit design that makes the volume increase (this is the implementation).

The remote control is the ADT — it hides the internal complexity and only exposes the operations you need.

2.3 Need of ADT

  1. It separates interface (what operations are available) from implementation (how they work internally).

  2. It allows programmers to use a data structure without worrying about internal details.

  3. It supports data abstraction and data hiding, two important principles of good software design.

  4. It makes code more maintainable, because the internal implementation can change without affecting the program that uses the ADT.

2.4 Features of ADT

  1. Abstraction – Hides implementation details from the user.

  2. Encapsulation – Bundles data and operations together.

  3. Well-defined interface – A fixed set of operations is provided (e.g., push, pop for stack).

  4. Independent of implementation – Can be implemented using array or linked list; the user does not need to know which one is used.

2.5 ADT vs Data Structure

Many students get confused between these two terms. Here is the clear difference explained point by point (no table, just clear comparison):

• ADT is a concept/design; Data Structure is the actual implementation. ADT is like a blueprint. Data Structure is the real building constructed from that blueprint.

• ADT specifies WHAT operations are possible (e.g., a Stack ADT says push, pop, peek are possible). Data Structure specifies HOW these operations are carried out internally (e.g., using array or linked list).

• ADT is language-independent — it is a logical/mathematical model. Data Structure is language-dependent — it must be written in a specific programming language (C, Java, Python, etc.).

• Example: "Stack" as a concept (LIFO behavior, push/pop operations) is an ADT. The actual C program implementing stack using an array is the data structure implementation.

2.6 Why ADT is Important

  1. It promotes modularity — programs can be broken into independent components.

  2. It hides complexity from the end user of the data structure.

  3. It allows multiple implementations of the same ADT (e.g., Stack can be implemented using array or linked list, but the user's code that calls push()/pop() does not change).

  4. It improves code reusability and reduces maintenance cost.

2.7 Common ADT Examples

  1. List ADT – operations: insert, delete, traverse, search.

  2. Stack ADT – operations: push, pop, peek, isEmpty, isFull.

  3. Queue ADT – operations: enqueue, dequeue, front, isEmpty, isFull.

  4. Tree ADT, Graph ADT, Map/Dictionary ADT.

2.8 Advantages of ADT

  1. Simplifies program design.

  2. Increases code reusability.

  3. Improves security through data hiding.

  4. Makes debugging and maintenance easier.

  5. Encourages good software engineering practice.

2.9 Applications of ADT

  1. Used to design Stack, Queue, List, Tree, Graph as logical models before coding.

  2. Used heavily in Object-Oriented Programming (classes are practical implementations of ADT concepts).

  3. Used in designing standard libraries (e.g., Java Collections Framework, C++ STL are built on ADT principles).