Classic Data Structures

Book Preface

Data structures are commonly used in many program designs. The study of data structures, therefore, rightly forms th.e central course of any curriculum i.n computer science and engineering. Today, most curricula computer science courses cover topics such as “Introduction to Computing”, “Principles _in of Programming Languages”, “Programming Methodologies”, “Algorithms”, etc. The study of these topics is not possible without first acquiring a thorough knowledge of data structures. Today’s computer world bas become unimaginably fast. To use the full strength of computing power to solve all sons of complicated problems through elegant program design, a good knowledge of the data structures is highly essential. To be more precise, writing efficient programs and managing different types of real and abstract data is an art; and data structure is the only ingredient to promote this an. In-depth concepts of data structures help in mastering their applications in real software projects.

In the last few years, there has been a tremendous progress in the field of data structures. and its related algorithms. This book offers a deep understanding of the essential concepts of data structures. The book exposes the reader to different types of data structures such as arrays, linked lists, stacks, queues, tables, trees, graphs, and sets for a good grounding in each area. These data structures are known as classic data structures, as with the help of these any abstract data which fits with real world applications can be implemented.

The study of data structures remains incomplete if their computer representations and operational details are not covered. The books currently avai.lable on data structures present the operational details with raw codes, which many readers, especially those new to the field, find difficult to understand. In the present title, operations on data structures are described in English-like constructs, which are easy to comprehend by students new to the computer science discipline.

This text is designed primarily for use i.n undergraduate engineering courses, but its clear analytic cllplanations in simple language also make it suitable for study by polytechnic students. The book can also be used as a self-study course on data structures. The !x>k is designed to be both versatile and complete, in the sense that for each type of data structure three imponant topics are elucidated. First, various ways of representing a structure are explained. Second, the different operations to manage a structure are presented. Finally, the applications of a data structure with focus on its engineering issues are discussed. More than 300 figures have been used to make the discussions comprehensive and lucid. There a.re numerous section-wise exercises as “Assignment” in each chapter so that the readers can test their understanding of the subject. Also, the problems under the heading “Problems to Ponder” in each chapter, are planned for the advanced readers who can judge their grasp of the subject. A few references are included at the end of each chapter for advanced study.

As prerequisites, the students are expected to have experience of a programming language, a little understanding of recursive procedures, introductory concepts of compiler, operating system, etc. The students are advised to go for generic implementation of algorithms with C++ so that once the data structures are programmed, they can be subsequently used in many different applications.
It is very difficult to avoid errors completely from a book of this nature. In spite of the immense amount of effort a.nd auention to minute details. some errors might have still crept in. The author would welcome and greatly appreciate suggestions from the readers on making improvements to the book.

I would like to express my sincere gratitude to my friends and colleagues who contributed in many ways towards completion of the present work. I am grateful to the staff of North Eastern Regional lnstitute of Science and Technology (NERIST), Nirjuli, and Indian Institute of Technology Kbaragpur who extended their help during the preparation of this book. My most heartfelt thanks go to Y. Usha for drawing all the figures in the book, and 10 N. Chetri and P. Kuli for typing the text. I also wish to express my gratitude to the staff at Prentice-Hall of India, New Delhi for a masterful job of producing the finished volume. Finally, I thank my wife Monalisa, a faculty member in the Department of Computer Science and Engineering, NERIST, who checked the manuscript with painstaking auention. Her sincere cooperation and involvement has made this work a reality. Our daughter Jl.nanya grudgingly allowed me to sit with the computer to do the work. I affectionately dedicate this work to them.