Data Structures and Program Design Using JAVA

Cover
Title
Copyright page
Dedication
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 Notaiton
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 Inrtroduction
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 Introductiion
10.1.1 Difference between Hashing and Direct Addressing
10.1.2 Hasg Tabs
10.1.3 Hasg 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