A Textbook of Data Structures and Algorithms, Volume 1: Mastering Linear Data Structures

Description

Cover Title Page Copyright Page Contents Preface Acknowledgments Chapter 1. Introduction 1.1. History of algorithms 1.2. Definition, structure and properties of algorithms 1.2.1. Definition 1.2.2. Structure and properties 1.3. Development of an algorithm 1.4. Data structures and algorithms 1.5. Data structures – definition and classification 1.5.1. Abstract data types 1.5.2. Classification 1.6. Algorithm design techniques 1.7. Organization of the book Chapter 2. Analysis of Algorithms 2.1. Efficiency of algorithms 2.2. Apriori analysis 2.3. Asymptotic notations 2.4. Time complexity of an algorithm using the O notation 2.5. Polynomial time versus exponential time algorithms 2.6. Average, best and worst case complexities 2.7. Analyzing recursive programs 2.7.1. Recursive procedures 2.7.2. Apriori analysis of recursive functions 2.8. Illustrative problems Chapter 3. Arrays 3.1. Introduction 3.2. Array operations 3.3. Number of elements in an array 3.3.1. One-dimensional array 3.3.2. Two-dimensional array 3.3.3. Multidimensional array 3.4. Representation of arrays in memory 3.4.1. One-dimensional array 3.4.2. Two-dimensional arrays 3.4.3. Three-dimensional arrays 3.4.4. N-dimensional array 3.5. Applications 3.5.1. Sparse matrix 3.5.2. Ordered lists 3.5.3. Strings 3.5.4. Bit array 3.6. Illustrative problems Chapter 4. Stacks 4.1. Introduction 4.2. Stack operations 4.2.1. Stack implementation 4.2.2. Implementation of push and pop operations 4.3. Applications 4.3.1. Recursive programming 4.3.2. Evaluation of expressions 4.4. Illustrative problems Chapter 5. Queues 5.1. Introduction 5.2. Operations on queues 5.2.1. Queue implementation 5.2.2. Implementation of insert and delete operations on a queue 5.2.3. Limitations of linear queues 5.3. Circular queues 5.3.1. Operations on a circular queue 5.3.2. Implementation of insertion and deletion operations in circular queue 5.4. Other types of queues 5.4.1. Priority queues 5.4.2. Deques 5.5. Applications 5.5.1. Application of a linear queue 5.5.2. Application of priority queues 5.6. Illustrative problems Chapter 6. Linked Lists 6.1. Introduction 6.1.1. Drawbacks of sequential data structures 6.1.2. Merits of linked data structures 6.1.3. Linked lists – structure and implementation 6.2. Singly linked lists 6.2.1. Representation of a singly linked list 6.2.2. Insertion and deletion in a singly linked list 6.3. Circularly linked lists 6.3.1. Representation 6.3.2. Advantages of circularly linked lists over singly linked lists 6.3.3. Disadvantages of circularly linked lists 6.3.4. Primitive operations on circularly linked lists 6.3.5. Other operations on circularly linked lists 6.4. Doubly linked lists 6.4.1. Representation of a doubly linked list 6.4.2. Advantages and disadvantages of a doubly linked list 6.4.3. Operations on doubly linked lists 6.5. Multiply linked lists 6.6. Unrolled linked lists 6.6.1. Retrieval of an element 6.6.2. Insert an element 6.6.3. Delete an element 6.7. Self-organizing lists 6.8. Applications 6.8.1. Addition of polynomials 6.8.2. Sparse matrix representation 6.9. Illustrative problems Chapter 7. Linked Stacks and Linked Queues 7.1. Introduction 7.1.1. Linked stack 7.1.2. Linked queues 7.2. Operations on linked stacks and linked queues 7.2.1. Linked stack operations 7.2.2. Linked queue operations 7.2.3. Algorithms for Push/Pop operations on a linked stack 7.2.4. Algorithms for insert and delete operations in a linked queue 7.3. Dynamic memory management and linked stacks 7.4. Implementation of linked representations 7.5. Applications 7.5.1. Balancing symbols 7.5.2. Polynomial representation 7.6. Illustrative problems References Index Summaries of other volumes EULA