Data structures and program design using java : a self-teaching introduction

Data structures provide a means to managing large amounts of information such as large databases, usingSEO effectively, and creating Internet/Web indexing services. This book isdesigned to present fundamentals of data structures for beginners using the Javaprogramming language in a friendly, self-teaching format. Practical analogiesusing real world applications are integrated throughout the text to explaintechnical concepts. The book includes a variety of end-of-chapter practiceexercises, e.g., programming, theoretical, and multiple-choice. Features: Covers data structure fundamentals using Java Numerous tips, analogies, and practical applications enhance understanding of subjects under discussion "Frequently Asked Questions" integrated throughout the text clarify and explain concepts Includes a variety of end-of-chapter exercises, e.g., programming, theoretical, and multiple choice 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 "Data structures provide a means to managing large amounts of information such as large databases, using SEO effectively, and creating Internet/Web indexing services. This book is designed to present fundamentals of data structures for beginners using the Java programming language in a friendly, self-teaching format. Practical analogies using real world applications are integrated throughout the text to explain technical concepts. The book includes a variety of end-of-chapter practice exercises, e.g., programming, theoretical, and multiple-choice." -- provided by publisher Data structures provide a means to manage large amounts of information, such as large databases, using SEO, and create Internet/Web indexing services. This book presents the fundamentals of data structures for beginners using the Java programming language in a friendly, self-teaching format.