## Data Structure Notes

- Data is simply a value or a set of values which represents some fact or figure. Initially we have raw data. To use it properly, we have to process this data in a meaningful way.
- When data has single value, it is called data item.
- When data can further be categorized in sub items, it is called group item.
- A file is a collection of logically related records that can be treated as a unit.
- An entity is an independent object about which data is being collected. It is a generalized class of people, places, or things (objects) for which data is collected, stored, and maintained.
- Entity set is a collection of similar entities.
- A key is a field or set of fields in a record that is used to identify the record. It is unique in a file.
- The processed data is known as information. From raw data, we extract data according to our requirements. This data is meaningful and is known as information. Information helps in decision making.
- Data structure refers to the ways of assembling or organizing data so that it can be used efficiently. i.e. the logical or mathematical model of organizing data is called data structure.
- In a linear data structure, the data items are arranged in a linear sequence so that processing of elements is possible in a linear manner.
- A data structure whose elements do not form a sequence so there is no unique successor or predecessor is called non-linear data structure.
- In homogeneous data structures all elements are of same data type.
- In non-homogeneous data structure the elements may or may not be of same type.
- The data structure that are atomic (indivisible) are called primitive.
- The data structure that are not atomic are called non-primitive.
- Static data structures are ones where size of structure & its associated memory location is fixed when the program is compiled.
- Those data structures where size of structure & its associated memory location is not fixed i.e. it may vary are called as Dynamic Data Structures.
- An Array is a collection of homogeneous data items stored under a same name and at contiguous memory locations. Homogeneous data elements mean data elements of same type. It is a group of related data items which have common name.
- a linked list is a dynamic data structure in the sense that we don’t require size of linked list in advance. Each node has at least two parts: Info Part It contains data in the node. This data may be some scalar value or a complete record. And Link Part It contains the address of the next node. The last node contains ‘null’ value which indicates that it is the end of list.
- A stack is a list of elements in which an element may be inserted or deleted only at one end, called the Top. This means, that elements are inserted to as well as removed from the top of stack. Push and Pop are the two basic operations that are performed on the Stack.
- Queues are also called " first-in first-out " (FIFO) list since the first element in a queue will be the first element out of the queue. In other words, the order in which elements enter in a queue is the order in which they leave. Enqueue and Dequeue are the two basic operations that are performed on the queue.
- A tree consist of a distinguished node r , called the root and zero or more (sub) tree t1 , t2 , ... tn each of whose roots are connected by a directed edge to r . It is a non linear data structure.
- A graph consists of a number of data items, each of which is called a vertex. Any vertex may be connected to any other, and these connections are called edges. It is a non linear data structure.
- Insertion, Deletion, Traversal, Searching, Sorting, Merging, Concatenation and Copying are among some of the major operations that are applied on the Data Structure.
- Algorithm is a sequence of steps which when followed in a particular order gives us desired results. It is used to develop logic for a program without considering the syntax of the programming language.
- Properties of Algorithm include Input & Output, Definiteness, Sequence, Finiteness, Flexibility, Generality, Effectiveness.
- To analyze an algorithm is to determine the amount of resources (such as time and storage) necessary to execute it. Most algorithms are designed to work with inputs of arbitrary length. Usually the efficiency or complexityof an algorithm is stated as a function relating the input length to the number of steps (time complexity) or storage locations (space complexity).
- The choice of a particular algorithm depends on following performance analysis and measurements : Space complexity and Time complexity
- When we analyze an algorithm it depends on the input data, the efficiency of an algorithm ‘s complexity is measured for three cases namely Best case, Average case and Worst case.
- Abstract data types or ADTs are a mathematical specification of a set of data and the set of operations that can be performed on the data. They are abstract in the sense that the focus is on the definitions of the constructor that returns an abstract handle that represents the data, and the various operations with their arguments.