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

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