**Data Structures Notes**

In these “* Data Structures Notes PDF*”, you will be developing the ability to use basic data structures like array, stacks, queues, lists, trees and hash tables to solve problems. C++ is chosen as the language to understand implementation of these data structures.

The topics we will cover will be taken from the following list:

**Arrays: **single and multi-dimensional arrays, analysis of insert, delete and search operations in arrays (both linear search and binary search), implementing sparse matrices, applications of arrays to sorting

**Sorting:** selection sort, insertion sort, bubble sort, comparison of sorting techniques via empirical studies. Introduction to Vectors.

**Linked Lists: **Singly- linked, doubly-linked and circular lists, analysis of insert, delete and search operations in all the three types, implementing sparse matrices. Introduction to Sequences.

**Queues: **Array and linked representation of queue, de-queue, comparison of the operations on queues in the two representations. Applications of queues.

**Stacks: **Array and linked representation of stacks, comparison of the operations on stacks in the two representations, implementing multiple stacks in an array.

**Applications of Stacks:** prefix, infix and postfix expressions, utility and conversion of these expressions from one to another; applications of stacks to recursion: developing recursive solutions to simple problems, advantages and limitations of recursion.

**Trees**: Introduction to tree as a data structure; binary trees, binary search trees, analysis of insert, delete, search operations, recursive and iterative traversals on binary search trees. Height-balanced trees (AVL), B trees, analysis of insert, delete, search operations on AVL and B trees.

**Heaps:** Introduction to heap as a data structure. analysis of insert, extract-min/max and delete-min/max operations, applications to priority queues.

**Hash Tables**: Introduction to hashing, hash tables and hashing functions -insertion, resolving collision by open addressing, deletion, searching and their analysis, properties of a good hash function.

A data structure is a way of storing data in a computer so that it can be used efficiently and it will allow the most efficient algorithm to be used. The choice of the data structure begins from the choice of an abstract data type (ADT). A well-designed data structure allows a variety of critical operations to be performed, using as few resources, both execution time and memory space, as possible.

Data structure introduction refers to a scheme for organizing data, or in other words it is an arrangement of data in computer’s memory in such a way that it could make the data quickly available to the processor for required calculations.

A data structure should be seen as a logical concept that must address two fundamental concerns.

1. how the data will be stored

2. what operations will be performed on it.

Data structure is a scheme for data organization so the functional definition of a data structure should be independent of its implementation. The functional definition of a data structure is known as ADT (Abstract Data Type) which is independent of implementation.

The way in which the data is organized affects the performance of a program for different tasks. Computer programmers decide which data structures to use based on the nature of the data and the processes that need to be performed on that data. Some of the more commonly used data structures include lists, arrays, stacks, queues, heaps, trees, and graphs.

.