Data Structures and Program Design Using Java E-Book

Mercury Learning and Information

• Herausgeber: Packt Publishing
• Kategorie: Fachliteratur
• Sprache: Englisch

Seitenzahl: 449

Veröffentlichungsjahr: 2024

Beschreibung

This book introduces the fundamentals of data structures using Java in a self-teaching format. It covers managing large databases, effective SEO, and creating web indexing services. Real-world analogies help explain technical concepts. Each chapter includes programming tasks, theoretical questions, and multiple-choice quizzes.
The course begins with an introduction to data structures and Java, moving through arrays, linked lists, queues, searching and sorting, stacks, trees, multi-way search trees, hashing, files, and graphs. Each chapter builds on the previous one, ensuring a thorough understanding of data structures.
Understanding these concepts is crucial for managing information and optimizing web services. This book guides readers from basic to advanced techniques, blending theory with practical skills. It is an essential resource for mastering data structures with Java, enhanced by end-of-chapter exercises and real-world examples.

Leseprobe

DATA STRUCTURES AND PROGRAM DESIGN USING JAVA

A Self-Teaching Introduction

Dheeraj Malhotra, PhDNeha Malhotra, PhD

Copyright © 2020 by MERCURY LEARNING AND INFORMATION LLC. All rights reserved.

This publication, portions of it, or any accompanying software may not be reproduced in any way, stored in a retrieval system of any type, or transmitted by any means, media, electronic display or mechanical display, including, but not limited to, photocopy, recording, Internet postings, or scanning, without prior permission in writing from the publisher.

Publisher: David Pallai

MERCURY LEARNINGAND INFORMATION

22841 Quicksilver Drive

Dulles, VA 20166

[e-mail]

www.merclearning.com

[phone]

D. Malhotra and N. Malhotra. Data Structures and Program Design Using JAVA.

ISBN: 978-1-68392-464-7

The publisher recognizes and respects all marks used by companies, manufacturers, and developers as a means to distinguish their products. All brand names and product names mentioned in this book are trademarks or service marks of their respective companies. Any omission or misuse (of any kind) of service marks or trademarks, etc. is not an attempt to infringe on the property of others.

Library of Congress Control Number: 2020930984

202122321     Printed on acid-free paper in the United States of America.

Our titles are available for adoption, license, or bulk purchase by institutions, corporations, etc. For additional information, please contact the Customer Service Dept. at [phone] (toll free).Digital versions of our titles are available at: academiccourseware.com and other electronic vendors.

The sole obligation of MERCURY LEARNING AND INFORMATION to the purchaser is to replace the book and/or disc, based on defective materials or faulty workmanship, but not based on the operation or functionality of the product.

Dedicated to ourloving parents and beloved students

CONTENTS

Preface

Acknowledgments

Chapter 1 Introduction to Data Structures

1.1 Introduction

1.2 Types of Data Structures

1.2.1 Linear and Non-Linear Data Structures

1.2.2 Static and Dynamic Data Structures

1.2.3 Homogeneous and Non-Homogeneous Data Structures

1.2.4 Primitive and Non-Primitive Data Structures

1.2.5 Arrays

1.2.6 Queues

1.2.7 Stacks

1.2.8 Linked Lists

1.2.9 Trees

1.2.10 Graphs

1.3 Operations on Data Structures

1.4 Algorithms

1.4.1 Developing an Algorithm

1.5 Approaches for Designing an Algorithm

1.6 Analyzing an Algorithm

1.6.1 Time-Space Trade-Off

1.7 Abstract Data Types

1.8 Big O Notation

1.9 Summary

1.10 Exercises

1.10.1 Theory Questions

1.10.2 Multiple Choice Questions

Chapter 2 Introduction to the Java Language

2.1 Introduction

2.2 Java and Its Characteristics

2.3 Java Overview

2.4 Compiling the Java Program

2.5 Object-Oriented Programming

2.6 Character Set Used in Java

2.7 Java Tokens

2.8 Data Types in Java

2.9 Structure of a Java Program

2.10 Operators in Java

2.11 Decision Control Statements in Java

2.12 Looping Statements in Java

2.13 Break and Continue Statements

2.14 Methods in Java

2.15 Summary

2.16 Exercises

2.16.1 Theory Questions

2.16.2 Programming Questions

2.16.3 Multiple Choice Questions

Chapter 3 Arrays

3.1 Introduction

3.2 Definition of an Array

3.3 Array Declaration

3.4 Array Initialization

3.5 Calculating the Address of Array Elements

3.6 Operations on Arrays

3.7 2-D Arrays/Two-Dimensional Arrays

3.8 Declaration of Two-Dimensional Arrays

3.9 Operations on 2-D Arrays

3.10 Multidimensional Arrays/N-Dimensional Arrays

3.11 Calculating the Address of 3-D Arrays

3.12 Arrays and Their Applications

3.13 Sparse Matrices

3.14 Types of Sparse Matrices

3.15 Representation of Sparse Matrices

3.16 Summary

3.17 Exercises

3.17.1 Theory Questions

3.17.2 Programming Questions

3.17.3 Multiple Choice Questions

Chapter 4 Linked Lists

4.1 Introduction

4.2 Definition of a Linked List

4.3 Memory Allocation in a Linked List

4.4 Types of Linked Lists

4.4.1 Singly Linked List

4.4.2 Operations on a Singly Linked List

4.4.3 Circular Linked Lists

4.4.4 Operations on a Circular Linked List

4.4.5 Doubly Linked List

4.4.6 Operations on a Doubly Linked List

4.5 Header Linked Lists

4.6 Applications of Linked Lists

4.7 Polynomial Representation

4.8 Summary

4.9 Exercises

4.9.1 Theory Questions

4.9.2 Programming Questions

4.9.3 Multiple Choice Questions

Chapter 5 Queues

5.1 Introduction

5.2 Definition of a Queue

5.3 Implementation of a Queue

5.3.1 Implementation of Queues Using Arrays

5.3.2 Implementation of Queues Using Linked Lists

5.3.2.1  Insertion in Linked Queues

5.3.2.2  Deletion in Linked Queues

5.4 Operations on Queues

5.4.1 Insertion

5.4.2 Deletion

5.5 Types of Queues

5.5.1 Circular Queue

5.5.1.1  Limitation of Linear Queues

5.5.1.2  Inserting an Element in a Circular Queue

5.5.1.3  Deleting an Element from a Circular Queue

5.5.2 Priority Queue

5.5.2.1  Implementation of a Priority Queue

5.5.2.2  Insertion in a Linked Priority Queue

5.5.2.3  Deletion in a Linked Priority Queue

5.5.3 De-Queues (Double-Ended Queues)

5.6 Applications of Queues

5.7 Summary

5.8 Exercises

5.8.1 Theory Questions

5.8.2 Programming Questions

5.8.3 Multiple Choice Questions

Chapter 6 Searching and Sorting

6.1 Introduction to Searching

6.2 Linear Search or Sequential Search

6.2.1 Drawbacks of a Linear Search

6.3 Binary Search

6.3.1 Binary Search Algorithm

6.3.2 Complexity of a Binary Search Algorithm

6.3.3 Drawbacks of a Binary Search

6.4 Interpolation Search

6.4.1 Working of the Interpolation Search Algorithm

6.4.2 Complexity of the Interpolation Search Algorithm

6.5 Introduction to Sorting

6.5.1 Types of Sorting Methods

6.6 External Sorting

6.7 Summary

6.8 Exercises

6.8.1 Theory Questions

6.8.2 Programming Questions

6.8.3 Multiple Choice Questions

Chapter 7 Stacks

7.1 Introduction

7.2 Definition of a Stack

7.3 Overflow and Underflow in Stacks

7.4 Operations on Stacks

7.5 Implementation of Stacks

7.5.1 Implementation of Stacks Using Arrays

7.5.2 Implementation of Stacks Using Linked Lists

7.5.2.1  Push Operation in Linked Stacks

7.5.2.2  Pop Operation in Linked Stacks

7.6 Applications of Stacks

7.6.1 Polish and Reverse Polish Notations

7.6.2 Conversion from Infix Expression to Postfix Expression

7.6.3 Conversion from Infix Expression to Prefix Expression

7.6.4 Evaluation of a Postfix Expression

7.6.5 Evaluation of a Prefix Expression

7.6.6 Parenthesis Balancing

7.7 Summary

7.8 Exercises

7.8.1 Theory Questions

7.8.2 Programming Questions

7.8.3 Multiple Choice Questions

Chapter 8 Trees

8.1 Introduction

8.2 Definitions

8.3 Binary Tree

8.3.1 Types of Binary Trees

8.3.2 Memory Representation of Binary Trees

8.4 Binary Search Tree

8.4.1 Operations on Binary Search Trees

8.4.2 Binary Tree Traversal Methods

8.4.3 Creating a Binary Tree Using Traversal Methods

8.5 AVL Trees

8.5.1 Need of Height-Balanced Trees

8.5.2 Operations on an AVL Tree

8.6 Summary

8.7 Exercises

8.7.1 Theory Questions

8.7.2 Programming Questions

8.7.3 Multiple Choice Questions

Chapter 9 Multi-Way Search Trees

9.1 Introduction

9.2 B-Trees

9.3 Operations on a B-Tree

9.3.1 Insertion in a B-Tree

9.3.2 Deletion in a B-Tree

9.4 Application of a B-Tree

9.5 B+ Trees

9.6 Summary

9.7 Exercises

9.7.1 Review Questions

9.7.2 Multiple Choice Questions

Chapter 10 Hashing

10.1 Introduction

10.1.1 Difference between Hashing and Direct Addressing

10.1.2 Hash Tables

10.1.3 Hash Functions

10.1.4 Collision

10.1.5 Collision Resolution Techniques

10.1.5.1  Chaining Method

10.1.5.2  Open Addressing Method

10.2 Summary

10.3 Exercises

10.3.1 Review Questions

10.3.2 Multiple Choice Questions

Chapter 11 Files

11.1 Introduction

11.2 Terminologies

11.3 File Operations

11.4 File Classification

11.5 C vs C++ vs Java File Handling

11.6 File Organization

11.7 Sequence File Organization

11.8 Indexed Sequential File Organization

11.9 Relative File Organization

11.10 Inverted File Organization

11.11 Summary

11.12 Exercises

11.12.1 Review Questions

11.12.2 Multiple Choice Questions

Chapter 12 Graphs

12.1 Introduction

12.2 Definitions

12.3 Graph Representation

12.3.1 Adjacency Matrix Representation

12.3.2 Adjacency List Representation

12.4 Graph Traversal Techniques

12.4.1 Breadth First Search

12.4.2 Depth First Search

12.5 Topological Sort

12.6 Minimum Spanning Tree

12.6.1 Prim’s Algorithm

12.6.2 Kruskal’s Algorithm

12.7 Summary

12.8 Exercises

12.8.1 Theory Questions

12.8.2 Programming Questions

12.8.3 Multiple Choice Questions

Answers to Multiple Choice Questions

Index

PREFACE

Data structures are the building blocks of computer science. The objective of this text is to emphasize the fundamentals of data structures as an introductory subject. It is designed for beginners who would like to learn the basics of data structures and their implementation using the Java programming language. With this focus in mind, we present various fundamentals of the subject, well supported with real-world analogies to enable a quick understanding of the technical concepts and to help in identifying appropriate data structures to solve specific, practical problems. This book will serve the purpose of a text/reference book and will be of immense help especially to undergraduate or graduate students of various courses in information technology, engineering, computer applications, and information sciences.

Key Features

Practical Applications: Real world analogies as practical applications are given throughout the text to quickly understand and connect the fundamentals of data structures with day to day, real-world scenarios. This approach, in turn, will assist the reader in developing the capability to identify the most appropriate and efficient data structure for solving a specific, real-world problem.

Frequently Asked Questions: Frequently asked theoretical/practical questions are integrated throughout the content of the book, within related topics to assist readers in grasping the subject.

Algorithms and Programs: To better understand the fundamentals of data structures at a generic level-followed by its object-oriented implementation in Java, syntax independent algorithms, as well as implemented programs in Java, are discussed throughout the book. This presentation will assist the reader in getting both algorithms and their corresponding implementation within a single book.

Numerical and Conceptual Exercises: To assist the reader in developing a strong foundation of the subject, various numerical and conceptual problems are included throughout the text.

Multiple Choice Questions: To assist students for placement-oriented exams in various IT fields, several exercises are suitably chosen and are given in an MCQ format.

Dr. Dheeraj MalhotraDr. Neha MalhotraFebruary 2020

ACKNOWLEDGMENTS

We are indeed grateful to Chairman VIPS- Dr. S.C. Vats, respected management, Chairperson VSIT, and Dean VSIT of Vivekananda Institute of Professional Studies (GGS IP University). They are always a source of inspiration for us, and we feel honored because of their faith in us.

We also take this opportunity to extend our gratitude to our mentors Dr. O.P. Rishi (University of Kota), Dr. Sushil Chandra (DRDO, GOI), and Dr. Udyan Ghose (GGS IP University) for their motivation to execute this project.

We are profoundly thankful to Ms. Stuti Suthar (VIPS, GGSIPU) and Mr. Deepanshu Gupta (Tech Mahindra Ltd.) for helping us in proofreading and compiling the codes in this manuscript.

It is not possible to complete a book without the support of a publisher. We are thankful to David Pallai and Jennifer Blaney of Mercury Learning and Information for their enthusiastic involvement throughout the tenure of this project.

Our heartfelt regards to our parents, siblings and family members who cheered us in good times and encouraged us in bad times.

Lastly, we have always felt inspired by our readers especially in the USA, Canada, and India. Their utmost love and positive feedback for our first two titles of Data Structures using C and C++, both published with MLI, helped us to further improve the current title.

Dr. Dheeraj MalhotraDr. Neha MalhotraFebruary 2020

CHAPTER 1

INTRODUCTION TO DATA STRUCTURES

1.1Introduction

A data structure is an efficient way of storing and organizing data elements in the computer memory. Data means a value or a collection of values. Structure refers to a method of organizing the data. The mathematical or logical representation of data in the memory is referred as a data structure. The objective of a data structure is to store, retrieve, and update the data efficiently. A data structure can be referred to as elements grouped under one name. The data elements are called members, and they can be of different types. Data structures are used in almost every program and software system. There are various kinds of data structures that are suited for different types of applications. Data structures are the building blocks of a program. For a program to run efficiently, a programmer must choose appropriate data structures. A data structure is a crucial part of data management. As the name suggests, data management is a task which includes different activities like the collection of data, the organization of data into structures, and much more. Some examples where data structures are usedinclude stacks, queues, arrays, binary trees, linked lists, hash tables, and so forth.

A data structure helps usto understand the relationship of one element to another element and organize it within the memory. It is a mathematical or logical representation or organization of data in memory. Data structures are extensively applied in the following areas:

Compiler Design

Database Management Systems (DBMS)

Artificial Intelligence

Network and Numerical Analysis

Statistical Analysis Packages

Graphics

Operating Systems (OS)

Simulations

As we see in the previous list, there are many applications in which different data structures are used for their operations. Some data structures sacrifice speed for efficient utilization of memory, while others sacrifice memory utilization and result in faster speed. In today’s world programmers aim not just to build a program but instead to build an effective program. As previously discussed, for a program to be efficient, a programmer must choose appropriate data structures. Hence, data structures are classified into various types. Now, let us discuss and learn about different types of data structures.

Frequently Asked Questions

1. Define the term data structure.

Ans: A data structure is an organization of data in a computer’s memory or disk storage. In other words, a logical or mathematical model of a particular organization of data is called a data structure. A data structure in computer science is also a way of storing data in a computer so that it can be used efficiently. An appropriate data structure allows a variety of important operations to be performed using both resources, that is, memory space and execution time, efficiently.

1.3Operations on Data Structures

Here we will discuss various operations which are performed on data structures.

Creation: It is the process of creating a data structure. Declaration and initialization of the data structure are done here. It is the first operation.

Insertion: It is the process of adding new data elements in the data structure, for example, to add the details of an employee who has recently joined an organization.

Deletion: It is the process of removing a particular data element from the given collection of data elements, for example, to remove the name of an employee who has left the company.

Updating: It is the process of modifying the data elements of a data structure. For example, if the address of a student is changed, then it should be updated.

Searching: It is used to find the location of a particular data element or all the data elements with the help of a given key, for example, to find the names of people who live in New York.

Sorting: It is the process of arranging the data elements in some order, that is, either an ascending or descending order. An example is arranging the names of students of a class in alphabetical order.

Merging: It is the process of combining the data elements of two different lists to form a single list of data elements.

Traversal: It is the process of accessing each data element exactly once so that it can be processed. An example is to print the names of all the students of a class.

Destruction: It is the process of deleting the entire data structure. It is the last operation in the data structure.

1.4Algorithms

An algorithm is a systematic set of instructions combined to solve a complex problem. It is a step-by-finite-step sequence of instructions, each of which has a clear meaning and can be executed with a minimum amount of effort in finite time. In general, an algorithm is a blueprint for writing a program to solve the problem. Once we have a blueprint of the solution, we can easily implement it in any high-level language like C, C++, Java, and so forth. It solves the problem into the finite number of steps. An algorithm written in a programming language is known as a program. A computer is a machine with no brain or intelligence. Therefore, the computer must be instructed to perform a given task in unambiguous steps. Hence, a programmer must define his problem in the form of an algorithm written in English. Thus, such an algorithm should have following features:

An algorithm should be simple and concise.

It should be efficient and effective.

It should be free of ambiguity; that is, the logic must be clear.

Similarly, an algorithm must have following characteristics:

Input: It reads the data of the given problem.

Output:  The desired result must be produced.

Process/Definiteness:  Each step or instruction must be unambiguous.

Effectiveness:  Each step should be accurate and concise. The desired result should be produced within a finite time.

Finiteness: The number of steps should be finite.

1.4.1Developing an Algorithm

To develop an algorithm, some steps are suggested:

Defining or understanding the problem.

Identifying the result or output of the problem.

Identifying the inputs required by the problem and choosing the best input.

Designing the logic from the given inputs to get the desired output.

Testing the algorithm for different inputs.

Repeating the previous steps until it produces the desired result for all the inputs.

1.5Approaches for Designing an Algorithm

A complicated algorithm is divided into smaller units which are called modules. Then these modules are further divided into sub-modules. Thus, in this way, a complex algorithm can easily be solved. The process of dividing an algorithm into modules is called modularization. There are two popular approaches for designing an algorithm:

Top-Down Approach

Bottom-Up Approach

Now let us understand both approaches.

Top-Down Approach: A top-down approach states that the complex/complicated problem/algorithm should be divided into smaller modules. These smaller modules are further divided into sub-modules. This process of decomposition is repeated until we achieve the desired output of module complexity. A top-down approach starts from the topmost module, and the modules are incremented accordingly until level is reached where we don’t require any more sub-modules, that is, the desired level of complexity is achieved.

Figure 1.8.

Top-down approach.

Bottom-Up Approach: A bottom-up algorithm design approach is the opposite of a top-down approach. In this kind of approach, we first start with designing the basic modules and proceed further toward designing the high-level modules. The sub-modules are grouped together to form a module of a higher level. Similarly, all high-level modules are grouped to form more high-level modules. Thus, this process of combining the sub-modulesis repeated until we obtain the desired output of the algorithm.

Figure 1.9.

Bottom-up approach.

1.6Analyzing an Algorithm

An algorithm can be analyzed by two factors, that is, space and time. We aim to develop an algorithm that makes the best use of both these resources. Analyzing an algorithm measures the efficiency of the algorithm. The efficiency of the algorithm is measuredin terms of speed and time complexity. The complexity of an algorithm is a function that measures the space and time used by an algorithm in terms of input size.

Time Complexity: The time complexity of an algorithm is the amount of time taken by an algorithm to run the program completely. It is the running time of the program. The time complexity of an algorithm depends upon the input size. The time complexity is commonly represented by using big O notation. For example, the time complexity of a linear search is O(n).

Space Complexity: The space complexity of an algorithm is the amount of memory space required to run the program completely. The space complexity of an algorithm depends upon the input size.

Time complexity is categorized into three types:

Best-Case Running Time: The performance of the algorithm will be best under optimal conditions. For example, the best case for a binary search occurs when the desired element is the middle element of the list. Another example can be of sorting; that is, if the elements are already sorted in a list, then the algorithm will execute in best time.

Average-Case Running Time: It denotes the behavior of an algorithm when the input is randomly drawn from a given collection or distribution. It is an estimate of the running time for “average” input. It is usually assumed that all inputs of a given size are likely to occur with equal probability.

Worst-Case Running Time: The behavior of the algorithm in this case concerns the worst possible case of input instance. The worst-case running time of an algorithm is an upper bound on the running time for any input. For example, the worst case for a linear search occurs when the desired element is the last element in the list or when the element does not exist in the list.

Frequently Asked Questions

6. Define time complexity

Ans: Time complexity is a measure which evaluates the count of the operations performed by a given algorithm as a function of the size of the input. It is the approximation of the number of steps necessary to execute an algorithm. It is commonly represented with asymptotic notation, that is, O(g) notation, also known as big O notation, where g is the function of the size of the input data.

1.6.1Time-Space Trade-Off

In computer science, time-space trade-off is a way of solving a particular problem either in less time and more memory space or in more time and less memory space. But if we talk in practical terms, designing such an algorithm in which we can save both space and time is a challenging task. So, we can use more than one algorithm to solve a problem. One may require less time, and the other may require less memory space to execute. Therefore, we sacrifice one thing for the other. Hence, there exists a time-space or time-memory trade-off between algorithms. Thus, this time-space trade-off gives the programmer a rational choice from an informed point of view. So, if time is a big concern for a programmer, then he or she might choose a program which takes less or the minimum time to execute. On the other hand, if space is a prime concern for a programmer, then, in that case, he or she might choose a program that takes less memory space to execute at the cost of more time.

1.7Abstract Data Types

An abstract data type (ADT) is a popular mathematical model of the data objects which define a data type along with various functions that operate on these objects. To understand the meaning of an abstract data type, we will simply break the term into two parts, that is, “data type” and “abstract.” The data type of a variable is a collection of values which a variable can take. There are various data types in Java that include integer, float, character, long, double, and so on. When we talk about the term “abstract” in the context of data structures, it means apart from detailed specification. It can be considered as a description of the data in a structure with a list of operations to be executed on the data within the structure. Thus, an abstract data type is the specification of a data type that specifies the mathematical and logical model of the data type.For example, when we use stacks and queues, then at that point of time our prime concern is only with the data type and the operations to be performed on those structures. We are not worried about how the data will be stored in the memory. Also, we don’t bother about how push () and pop () operations work. We just know that we have two functions available to us, so we have to use them for insertion and deletion operations.

1.9Summary

A data structure determines a way of storing and organizing the data elements in the computer memory. Data means a value or a collection of values. Structure refers to a way of organizing the data. The mathematical or logical representation of data in the memory is referred as a data structure.

Data structures are classified into various types which include linear and non-linear data structures, primitive and non-primitive data structures, static and dynamic data structures, and homogeneous and non-homogeneous data structures.

A linear data structure is one in which the data elements are stored in a linear or sequential order; that is, data is stored in consecutive memory locations. A non-linear data structure is one in which the data is not stored in any sequential order or consecutive memory locations.

A static data structure is a collection of data in memory which is fixed in size and cannot be changed during runtime. A dynamic data structure is a collection of data in which memory can be reallocated during execution of a program.

Primitive data structures are fundamental data structures or predefined data structures which are supported by a programming language. Non-primitive data structures are comparatively more complicated data structures that are created using primitive data structures.

A homogeneous data structure is one that contains all data elements of the same type. A non-homogeneous data structure contains data elements of different types.

An array is a collection of homogeneous (similar) types of data elements in contiguous memory.

A queue is a linear collection of data elements in which the element inserted first will be the element taken out first, that is, a FIFO data structure. A queue is a linear data structure in which the first element is inserted from one end called the REAR end and the deletion of the element takes place from the other end called the FRONT end.

A linked list is a sequence of nodes in which each node contains one or more than one data field and an address field that stores the address of the next node.

A stack is a linear collection of data elements in which insertion and deletion take place only at one end called the TOP of the stack. A stack is a Last In First Out (LIFO) data structure, because the last element added to the top of the stack will be the first element to be deleted from the top of the stack.

A tree is a non-linear data structure in which the data elements or the nodes are represented in a hierarchical order. Here, an initial node is designated as the root node of the tree, and the remaining nodes are partitioned into two disjointed sets such that each set is a part of a subtree.

A binary tree is the simplest form of a tree. A binary tree consists of a root node and two subtrees known as the left subtree and right subtree, where both the subtrees are also binary trees.

A graph is a general tree with no parent-child relationship. It is a non-linear data structure which consists of vertices or nodes and the edges which connect those vertices with one another.

An algorithm is a systematic set of instructions combined to solve a complex problem. It is a step-by-finite-step sequence of instructions, each of which has a clear meaning and can be executed in a minimum amount of effort in finite time.

The process of dividing an algorithm into modules is called modularization.

The time complexity of an algorithm is described as the amount of time taken by an algorithm to run the program completely. It is the running time of the program.

The space complexity of an algorithm is the amount of memory space required to run the program completely.

An ADT (Abstract Data Type) is a mathematical model of the data objects which define a data type as well as the functions to operate on these objects.

Big O notation is one of the most popular analysis characterization schemes, since it provides an upper bound on the complexity of an algorithm.

1.10Exercises

1.10.1 Theory Questions

How do you define a good program?

Explain the classification of data structures.

What is an algorithm? Discuss the characteristics of an algorithm.

What are the various operations that can be performed on data structures? Explain each of them with an example.

Differentiate an array with a linked list.

Explain the terms time complexity and space complexity.

Write a short note on graphs.

What is the process of modularization?

Differentiate between stacks and queues with examples.

What is meant by abstract data types (ADT)? Explain in detail.

How do you define the complexity of an algorithm? Discuss the worst-case, best-case, and average-case time complexity of an algorithm.

Write a brief note on trees.

Explain how you can develop an algorithm to solve a complex problem.

Explain time-memory trade-off in detail.

1.10.2Multiple Choice Questions

Which of the following data structures is a FIFO data structure?

(a) Array

(b) Stacks

(c) Queues

(d) Linked List

How many maximum children can a binary tree have?

(a) 0

(b) 2

(c) 1

(d) 3

Which of the following data structures uses dynamic memory allocation?

(a) Graphs

(b) Linked Lists

(c) Trees

(d) All of these

In a queue, deletion is always done from the ________.

(a) Front end

(b) Rear end

(c) Middle

(d) None of these

Which data structure is used to represent complex relationships between the nodes?

(a) Linked Lists

(b) Trees

(c) Stacks

(d) Graphs

Which of the following is an example of a heterogeneous data structure?

(a) Array

(b) Structure

(c) Linked list

(d) None of these

In a stack, insertion and deletion takes place from the ________.

(a) Bottom

(b) Middle

(c) Top

(d) All of these

Which of the following is not part of the Abstract Data Type (ADT) description?

(a) Operations

(b) Data

(c) Both (a) and (b)

(d) None of the above

Which of the following data structures allows deletion at one end only?

(a) Stack

(b) Queue

(c) Both (a) and (b)

(d) None of the above

Which of the following data structures is a linear type?

(a) Trees

(b) Graphs

(c) Queues

(d) None of the above

Which one of the following is beneficial when the data is stored and has to be retrieved in reverse order?

(a) Stack

(b) Linked List

(c) Queue

(d) All of the above

A binary search tree whose left and right subtree differ in height by 1 at most is a ________.

(a) Red Black Tree

(b) M way search tree

(c) AVL Tree

(d) None of the above

The operation of processing each element in the list is called ________.

(a) Traversal

(b) Merging

(c) Inserting

(d) Sorting

Which of the following are the two primary measures of the efficiency of an algorithm?

(a) Data & Time

(b) Data & Space

(c) Time & Space

(d) Time & Complexity

Which one of the following cases does not exist/occur in complexity theory?

(a) Average Case

(b) Worst Case

(c) Best Case

(d) Minimal Case

CHAPTER 2

INTRODUCTION TO THE JAVA LANGUAGE

2.1 Introduction

Java is a widely used programming language that was originally created by James Gosling, Mike Sheridan, Chris Warth, Ed Frank, and Patrick Naughton at Sun Microsystems in 1991. Sun Microsystems released the first public implementation of Java 1.0 in 1996. The primary motivation for developing Java was the need for a platform-independent language that could be used to create software that could be embedded in different electronic devices, such as washing machines, remote controls, televisions, and so on. There are various types of CPUs available which are used as controllers that are mainly designed to be compiled only for a specific target with the help of C, C++, Java, and other programming languages. But one limitation is the time-consuming process of creating the compilers; in addition, the compilers are too expensive. Hence, to overcome this limitation and to find an easier and more cost-efficient solution, James Goslings along with his coworkers began their work on a portable and platform-independent language that could be used to produce code that would run on a variety of CPUs under different environments, which ultimately led to the creation of the Java language. Mainly, there were three primary goals in the creation of the Java language, which are as follows:

It must be simple, object-oriented, and a familiar language.

It must be portable, distributed, and platform independent.

It must be robust, secure, and reliable.

2.2 Java and Its Characteristics

Although Java derives many of its characteristics from C and C++, it is not an enhanced version of C++. It uses the syntax of the C language and echoes the object-oriented features of the C++ language. Java is a very powerful language and it is known as a language for professional programmers. There are several different characteristics of the Java programming language. Some of them are as follows:

Java is a very simple language that is very easy to learn, and its syntax is simple and easy to understand.

Java is an object-oriented programming language. Everything in Java is an object.

Java is best known for its security. Since everything in Java is considered as an object, it increases its security. Also, Java is secure because it does not use explicit pointers and because Java programs run inside a virtual machine sandbox.

Java is a robust language because it uses strong memory management concepts and contains an automatic garbage collection mechanism. It also supports powerful exception handling. All these features make Java robust.

Java is portable because the Java code can be run on any platform. It doesn’t require any further implementation.

Java is faster than other traditional interpreted programming languages because Java bytecode is very “close” to the native code, and thus it offers high performance.

Java is a distributed, multi-threaded, and dynamic language.

2.3 Java Overview

In Java, initially all the source code is written into plaintext files ending with the .java (dot java) extension. All the source files are then compiled into .class files by the java c compiler. A .class file does not contain the code that is native to your processor; instead it contains bytecode, which is the machine language of the Java Virtual Machine (JVM). Finally, the java launcher tool then runs the application with an instance of the JVM. As the JVM is available on different operating systems, the same .class files are capable of running on different operating systems like Windows, macOS, Linux, and so forth.

Figure 2.1.

Overview of Java SE process.

2.4 Compiling the Java Program

Each file in Java uses the .java filename extension. Also, in Java all the code must be inside a class. The most important task is that, by convention, the name of the class should match the name of the file that holds the program.

To compile a program, open the command prompt in your system. Run the compiler javac (Java compiler), specifying the source file on the following command prompt:

The source file is compiled into a .class file by the compiler. Now, the Filename.class file will be created, which will contain the bytecode of the program. To run the program, use the Java Launcher tool also known as java.

Finally, when the program is executed, the output is displayed as:

2.5 Object-Oriented Programming

Object-oriented programming is the core of the Java programming language. Object-oriented programming (OOP) is so integral to Java that it is best to understand its basic principles. OOP organizes a program around its data and a set of well-defined interfaces to that data. The following are the various features or characteristics of object-oriented programming:

Objects: An object is a container in which the data is stored in a combination of variables, methods, and data structures. An object is that component of a program that interacts with the other parts/pieces of the program. Objects are the fundamental runtime entities of a program.

Classes: The building block of Java that leads to object-oriented programming is a class. A class is actually a user-defined data type that holds its own data members and member methods. It is a way to bind the data members and methods together. A class can be accessed by creating an object of that class. Classes provide a convenient method for packing together a group of logically related data items and methods that work on them.

Encapsulation: Encapsulation is a process of wrapping up data members and member methods into a single unit. It is the mechanism which keeps the code and the data safe from external interference. It implies that there is no direct access granted to the data; that is, it is hidden. So, in order to access that data, we must interact with the object that is responsible for the data. This is also known as data hiding. The process of encapsulation makes the data of the system more secure and reliable.

Practical Application

The most common example of encapsulation is a capsule. In a capsule, all the medicines are encapsulated inside a single capsule.

Inheritance: Inheritance is the process of deriving a new class from the existing one. The existing class is known as the “base class,” “parent class,” or “superclass.” The new classis known as the “derived class,” “child class,” or “subclass.” The process of inheritance allows the child classes to inherit all the features, that is, variables and methods, of their parent class. Thus, the derived classes will have all the features of their base class, and the programmer can add some new features specific to the derived class. There are three types of inheritances supported in Java, which are as follows:

Single Inheritance: A class derived from a single base class is known as a single inheritance.

Multilevel Inheritance: Classes derived from the already derived classes are known as multilevel inheritances.

Multiple Inheritance: A class derived from more than one base class is known as a multiple inheritance. It is not achieved directly through classes in Java. It is achieved with the help of interfaces which will be covered in the upcoming chapters.

Frequently Asked Questions

1. What is the difference between the base and derived class?

Ans: When creating a class, instead of writing completely new data members and member methods, the programmer can designate that the new class should inherit the members of an existing class. This existing class is known as a base class, and the new class is known as a derived class. A class can be derived from more than one class, which means it can inherit data and methods from multiple base classes.

Practical Application

The most common real-life example of inheritance is your family, in which your grandfather is one head of the family (base class/parent class), your father is the child of the grandfather (derived class/child class), and you are the child of your father (another derived class).

Polymorphism: The word polymorphism is derived from the word poly, which means many, and the word morph, which means forms. Therefore, anything that exists in more than one form is referred to as a polymorph. Thus, polymorphism means the ability to make more than one form. Polymorphism usually occurs when there is a hierarchy of classes and the classes are related by inheritance. Polymorphism is considered as one of the most important features of object-oriented programming. Polymorphism is of two types: