Contents

1. Introduction to Data Structure

1. Introduction

2. Need for Data Structures

2.1 Definition of Data Structure

2.2 Implementation of a Data Structure

3. Data Representation

3.1 Abstract Data Type

3.2 Classification of Data Structure

3.3 Atomic Type

4. Data Types

5. Operations on Data Structures

6. Different Approaches for Designing an algorithm

7. Performance Analysis

7.1 Space Complexity

7.2 Time Complexity

8. BIG ‘O’ Notation-Asymptotic Notation

8.1 Big ‘O’ Notation

8.2 Formal Definition – Big O Notation

2. Sorting and Searching

1. Introduction

2. Sorting

3. SORTING TECHNIQUES

3.1 Bubble Sort

3.2 Selection Sort

3.3 Insertion Sort

3.4 Quick Sort

3.5 Merge Sort

3.6 Shell Sort

3.7 Radix Sort

4. Searching

4.1 Sequential / Linear Search

4.2 Binary Search

Solved Examples

3. Stacks

1. Introduction

1.1 Stack

1.2 Stack as an Abstract Data Type (ADT)

2. Implementation of Stack

2.1 Implementation of a Stack using Array (Static Implementation)

2.2 Representation of Stack using Linked List

2.3 Comparing Static and Dynamic Implementation

3. Applications of Stack

4. Expression Evaluation and Conversion

4.1 Expression Conversions (Manual)

4.2 Conversion and Evaluation Algorithms

5. Postfix to Infix Conversion

6. Prefix to Postfix Conversion

5. Recursion Using Implicit Stack

5.1 Simulation of Recursion using Explicit Stack

6. Reversing a String

Solved Examples

4. Queue

1. Introduction

2. Operations on a Queue

3. Queue as ADT

3.1 Explanation of the ADT

4. Types of Queues

4.1 Linear Queue

4.2 Circular Queue

4.3 Doubly Ended Queue

4.4 Priority Queue

5. Applications of Queue

Solved Examples

5. Linked List

1. Introduction

2. Concept of Linked List

3. Linked List Implementation

3.1 Static Representation

3.2 Dynamic Representation

4. Types of Linked Lists

5. Operations on a Linked List

6. Dynamic Implementation of a Singly Linked List

6.1 Operations on Singly Linked List

7. Doubly Linked List

7.1 Comparing Singly and Doubly Linked List

8. Circular List

9. Applications of Linked List

10. Stack using Linked List

11. Queue using a Linked List

Solved Problems

6. Trees

1. Introduction

2. Tree Terminology

3. Representation of Binary Trees

3.1 Sequential Representation

3.2 Linked Representation

4. Creating a Binary Search Tree

5. Tree Traversals

5.1 Non-recursive Tree Traversals

6. Operations on Trees

6.1 Searching an element in the Binary Search Tree

6.2 Inserting an element in the Binary Search Tree

6.3 Deleting an Element from a Binary Search Tree

6.4 Computing the height of a tree and level-wise Display of a Tree

6.5 Copying a Tree

6.6 Comparing Two Binary Search Trees

6.7 Mirroring a Given Tree

6.8 Counting the Total Nodes in a Tree

6.9 Counting the Leaf Nodes of a Tree

7. Applications of Tree

8. Height Balanced Trees

Solved Problems

7. Graph and Hashing

1. Graph

1.1 Definitions and Terminology

2. Graph Representation

2.1 Sequential Representation of Graph

2.2 Linked Representation of Graphs

3. Traversal of Graphs

3.1 Depth First Search

3.2 Breadth First Search

4. Applications of Graph

Solved Problems

5. Hashing

6. Concept of Hashing

7. Hashing Terminology

8. Hashing Function

8.1 Desirable Characteristics of a Hashing Function

8.2 Uniform Hashing Functions

9. Collision Resolution Techniques

9.1 Open Addressing

9.2 Chaining

Solved Examples