Unit 1
Introduction: Overview of Data Structures – A Philosophy of Data Structures – The Need for Data Structures – Cost and Benefits – Abstract Data Types and Data Structures – Principles, and Patterns. Basic complexity analysis – Best, Worst, and Average Cases – Asymptotic Analysis – Analyzing Programs – Space Bounds, Arrays, Linked Lists and Recursion: Using Arrays – Lists – Array based List Implementation – Linked Lists – LL ADT – Singly Linked List – Doubly Linked List – Circular Linked List – recursion – linear, binary, and multiple recursions.
Unit 2
Stacks and Queues: Stack ADT – Array based Stacks, Linked Stacks – Implementing Recursion using Stacks, Queues – ADT, Array based Queue, Linked Queue, Doubleended queue, Circular queue. Trees: Tree Definition and Properties – Tree ADT – Basic tree traversals – Binary tree – Data structure for representing trees – Linked Structure for Binary Tree – Array based implementation. Priority queues: ADT – Implementing Priority Queue using List – Heaps. Maps and Dictionaries: Map ADT – List based Implementation – Hash Tables – Dictionary ADT – Skip List – Complexity.
