Basic Concepts in Data Structures

INDEX

CHAPTER-1:  DATA STRUCTURES     1

1.1 Introduction to Data Structures      1

1.1.1 Definition        1

1.1.2 Importance of Data Structures     1

1.1.3 Classification of Data Structures     2

1.1.4 Applications of Data Structures     4

1.1.5 Advantages of Data Structures     4

Abstract Data Types (ADTs)      5

1.2.1 ADT         5

1.2.2 Specifications of ADTs      6

1.2.3 Features of ADT       6

1.2.4 Advantages        7

1.2.5 Disadvantages       7

1.3 Arrays         8

1.3.1 Characteristics of an Array      8

1.3.2 Array Types        9

1.3.3 Advantages of Arrays      11

1.3.4 Disadvantages of Arrays      11

1.4 Searching Techniques       12

1.5 Sorting Techniques       15

CHAPTER-2:  LINKED LISTS      18

2.1 Linked Lists        18

2.1.1 Representation of Linked List in Memory    18

2.2 Types of Linked Lists       19

2.2.1. Single Linked List (SLL)      19

2.2.2. Circular Linked List (CLL)      23

2.2.3. Double Linked List       26

2.3 Comparison between Array and Linked List    30

2.4 Applications of Linked List      31

CHAPTER-3:  STACKS       32

3.1 Stacks         32

3.2 Representation of Stack       32

3.2.1. Array Representation of a Stack     33

3.2.2. Linked List Representation of a Stack    35

3.3 Applications of Stack       37

3.3.1. Factorial Calculation      38

3.3.2. Infix to Postfix Conversion      38

3.3.3. Evaluation of Postfix Expression     40

3.3.4. Reversing List of Elements      41

CHAPTER-4:  QUEUES & DEQUES     42

4.1 Queues         42

4.2 Representation of Queue       42

4.2.1. Representation of Queue Using Arrays    42

4.2.2. Representation of Queue Using Linked List   45

4.3 Various Queue Structures       50

4.3.1. Circular Queues       50

4.3.2. Deque        52

CHAPTER-5:  TREES       56

5.1 Basic Terminology       56

5.2 Tree         58

5.3 Binary Tree        58

5.3.1 Two Special Cases of Binary Tree     58

5.4 Properties of Binary Trees      60

5.5 Representation of Binary Tree      61

5.5.1. Linear (Or) Sequential Representation Using Arrays  61

5.5.2. Linked List Representation of Binary Tree Using Pointers 62

5.6 Binary Tree Traversals       64

5.6.1. Preorder Traversal       64

5.6.2. Inorder Traversal       64

5.6.3. Postorder Traversal       64

5.7 Recursive Binary Tree Traversals      65

5.8 Creation of Binary Tree from Its Tree Traversals   66

5.9 Types of Binary Tress       69

5.10 Binary Search Tree       69

UNIT - I

DATA STRUCTURES

1.1 INTRODUCTION TO DATA STRUCTURES:-

1.1.1 Definition:

A data structure is a specialized format for organizing, processing, retrieving and storing data.

(or)

A data structure is a way of organizing and storing data in a computer so that it can be accessed and used efficiently. It refers to the logical or mathematical representation of data, as well as the implementation in a computer program.

(or)

A data structure is a group of data elements that provides the most straightforward way to store and perform various operations on computer data. A data structure is an effective technique to arrange data in a computer.

(or)

In computer terms, a data structure is a Specific way to store and organize data in a computer's memory so that these data can be used efficiently later.

Why should we learn Data Structures?

›  Data Structures and Algorithms are two of the key aspects of Computer Science.

›  Data Structures allow us to organize and store data, whereas Algorithms allow us to process that data meaningfully.

›  Learning Data Structures and Algorithms will help us become better Programmers.

›  We will be able to write code that is more effective and reliable.

›  We will also be able to solve problems more quickly and efficiently.

1.1.2 Importance of Data Structures:

❖  Efficiency: Data structures are essential for writing efficient code. They help optimize algorithms by providing means to manage large amounts of data efficiently, ensuring operations like insertion, deletion, and searching are performed quickly.

❖  Data Management: They provide a systematic way to organize and manage data. Proper use of data structures ensures data can be accessed and modified effectively.

❖  Reusability: Well-designed data structures can be reused across multiple programs and projects, reducing redundancy and improving maintainability.

❖  Abstraction: They allow for abstraction, which hides the complexities of data management and provides a simpler interface for users to interact with data.

❖  Algorithm Performance: Choosing the right data structure is crucial for the performance of an algorithm. Different algorithms require different data structures for optimal performance.

❖  Memory Management: Efficient data structures help in managing memory allocation and deallocation, preventing memory leaks and enhancing the performance of applications.

❖  Real-world Application: Data structures are the backbone of various real-world applications, from databases and operating systems to networking and artificial intelligence.

1.1.3 Classification of Data Structures:

A data structure provides a structured set of variables that are associated with each other in different ways. It forms a basis of programming tool that represents the relationship between data elements and helps programmers to process the data easily.

Data structure can be classified into two categories:

A. Primitive data structure

B. Non-primitive data structure

Figure 1.1 shows the different classifications of data structures.

Fig.1.1 Classifications of data structures

––––––––

A. Primitive Data Structure

Primitive data structures consist of the numbers and the characters which are built in