Data Structures
c
Using
Second Edition
Reema Thareja
Assistant Professor
Department of Computer Science
Shyama Prasad Mukherjee College for Women
University of Delhi
, 3
Oxford University Press is a department of the University of Oxford.
It furthers the University’s objective of excellence in research, scholarship,
and education by publishing worldwide. Oxford is a registered trade mark of
Oxford University Press in the UK and in certain other countries.
Published in India by
Oxford University Press
YMCA Library Building, 1 Jai Singh Road, New Delhi 110001, India
© Oxford University Press 2011, 2014
The moral rights of the author/s have been asserted.
First Edition published in 2011
Second Edition published in 2014
All rights reserved. No part of this publication may be reproduced, stored in
a retrieval system, or transmitted, in any form or by any means, without the
prior permission in writing of Oxford University Press, or as expressly permitted
by law, by licence, or under terms agreed with the appropriate reprographics
rights organization. Enquiries concerning reproduction outside the scope of the
above should be sent to the Rights Department, Oxford University Press, at the
address above.
You must not circulate this work in any other form
and you must impose this same condition on any acquirer.
ISBN-13: 978-0-19-809930-7
ISBN-10: 0-19-809930-4
Typeset in Times New Roman
by Pee-Gee Graphics, New Delhi
Printed in India by Radha Press, New Delhi 110031
,I dedicate this book to my family
and
my uncle Mr B.L. Thareja
, Preface to the First Edition
A data structure is defined as a group of data elements used for organizing and storing data. In order
to be effective, data has to be organized in a manner that adds to the efficiency of an algorithm, and
data structures such as stacks, queues, linked lists, heaps, and trees provide different capabilities
to organize data.
While developing a program or an application, many developers find themselves more interested
in the type of algorithm used rather than the type of data structure implemented. However, the
choice of data structure used for a particular algorithm is always of the utmost importance. Each
data structure has its own unique properties and is constructed to suit various kinds of applications.
Some of them are highly specialized to carry out specific tasks. For example, B-trees with their
unique ability to organize indexes are well-suited for the implementation of databases. Similarly,
stack, a linear data structure which provides ‘last-in-first-out’ access, is used to store and track
the sequence of web pages while we browse the Internet. Specific data structures are essential
components of many efficient algorithms, and make possible the management of large amounts of
data, such as large databases and Internet indexing services. C, as we all know, is the most popular
programming language and is widespread among all the computer architectures. Therefore, it is
not only logical but also fundamentally essential to start the introduction and implementation of
various data structures through C. The course data structures is typically taught in the second or
third semester of most engineering colleges and across most engineering disciplines in India. The
aim of this course is to help students master the design and applications of various data structures
and use them in writing effective programs.
About the Book
This book is aimed at serving as a textbook for undergraduate engineering students of computer
science and postgraduate level courses of computer applications. The objective of this book is to
introduce the concepts of data structures and apply these concepts in problem solving. The book
provides a thorough and comprehensive coverage of the fundamentals of data structures and the
principles of algorithm analysis. The main focus has been to explain the principles required to
select or design the data structure that will best solve the problem.
A structured approach is followed to explain the process of problem solving. A theoretical
description of the problem is followed by the underlying technique. These are then ably supported
by an example followed by an algorithm, and finally the corresponding program in C language.
The salient features of the book include:
∑ Explanation of the concepts using diagrams
∑ Numerous solved examples within the chapters
∑ Glossary of important terms at the end of each chapter
∑ Comprehensive exercises at the end of each chapter
∑ Practical implementation of the algorithms using tested C programs
∑ Objective type questions to enhance the analytical ability of the students
c
Using
Second Edition
Reema Thareja
Assistant Professor
Department of Computer Science
Shyama Prasad Mukherjee College for Women
University of Delhi
, 3
Oxford University Press is a department of the University of Oxford.
It furthers the University’s objective of excellence in research, scholarship,
and education by publishing worldwide. Oxford is a registered trade mark of
Oxford University Press in the UK and in certain other countries.
Published in India by
Oxford University Press
YMCA Library Building, 1 Jai Singh Road, New Delhi 110001, India
© Oxford University Press 2011, 2014
The moral rights of the author/s have been asserted.
First Edition published in 2011
Second Edition published in 2014
All rights reserved. No part of this publication may be reproduced, stored in
a retrieval system, or transmitted, in any form or by any means, without the
prior permission in writing of Oxford University Press, or as expressly permitted
by law, by licence, or under terms agreed with the appropriate reprographics
rights organization. Enquiries concerning reproduction outside the scope of the
above should be sent to the Rights Department, Oxford University Press, at the
address above.
You must not circulate this work in any other form
and you must impose this same condition on any acquirer.
ISBN-13: 978-0-19-809930-7
ISBN-10: 0-19-809930-4
Typeset in Times New Roman
by Pee-Gee Graphics, New Delhi
Printed in India by Radha Press, New Delhi 110031
,I dedicate this book to my family
and
my uncle Mr B.L. Thareja
, Preface to the First Edition
A data structure is defined as a group of data elements used for organizing and storing data. In order
to be effective, data has to be organized in a manner that adds to the efficiency of an algorithm, and
data structures such as stacks, queues, linked lists, heaps, and trees provide different capabilities
to organize data.
While developing a program or an application, many developers find themselves more interested
in the type of algorithm used rather than the type of data structure implemented. However, the
choice of data structure used for a particular algorithm is always of the utmost importance. Each
data structure has its own unique properties and is constructed to suit various kinds of applications.
Some of them are highly specialized to carry out specific tasks. For example, B-trees with their
unique ability to organize indexes are well-suited for the implementation of databases. Similarly,
stack, a linear data structure which provides ‘last-in-first-out’ access, is used to store and track
the sequence of web pages while we browse the Internet. Specific data structures are essential
components of many efficient algorithms, and make possible the management of large amounts of
data, such as large databases and Internet indexing services. C, as we all know, is the most popular
programming language and is widespread among all the computer architectures. Therefore, it is
not only logical but also fundamentally essential to start the introduction and implementation of
various data structures through C. The course data structures is typically taught in the second or
third semester of most engineering colleges and across most engineering disciplines in India. The
aim of this course is to help students master the design and applications of various data structures
and use them in writing effective programs.
About the Book
This book is aimed at serving as a textbook for undergraduate engineering students of computer
science and postgraduate level courses of computer applications. The objective of this book is to
introduce the concepts of data structures and apply these concepts in problem solving. The book
provides a thorough and comprehensive coverage of the fundamentals of data structures and the
principles of algorithm analysis. The main focus has been to explain the principles required to
select or design the data structure that will best solve the problem.
A structured approach is followed to explain the process of problem solving. A theoretical
description of the problem is followed by the underlying technique. These are then ably supported
by an example followed by an algorithm, and finally the corresponding program in C language.
The salient features of the book include:
∑ Explanation of the concepts using diagrams
∑ Numerous solved examples within the chapters
∑ Glossary of important terms at the end of each chapter
∑ Comprehensive exercises at the end of each chapter
∑ Practical implementation of the algorithms using tested C programs
∑ Objective type questions to enhance the analytical ability of the students
