data structure computer science class notes

Unit – I Syllabus: • Data Structures - Definition, Classification of Data Structures, Operations on Data Structures, Abstract Data Type (ADT), Preliminaries of algorithms. Time and Space complexity. • Searching - Linear search, Binary search, Fibonacci search. • Sorting- Insertion sort, Selection sort, Exchange (Bubble sort, quick sort), distribution (radix sort), merging (Merge sort) algorithms.  A data structure is a particular way of storing and organizing data in a computer so that it can be used efficiently.  Some common examples of data structures are arrays, linked lists, queues, stacks, binary trees, and hash tables  Today computer programmers do not write programs just to solve a problem but to write an efficient program.  When selecting a data structure to solve a problem, the following steps must be performed. 1. Analysis of the problem to determine the basic operations that must be supported. 2. Quantify the resource constraints for each operation. 3. Select the data structure that best meets these requirements.  The term data means a value or set of values. It specifies either the value of a variable or a constant (e.g., marks of students, name of an employee, address of a customer, value of pi, etc.).  A record is a collection of data items. For example, the name, address, course, and marks obtained are individual data items. But all these data items can be grouped together to form a record.  A file is a collection of related records. For example, if there are 60 students in a class, then there are 60 records of the students. All these related records are stored in a file.  Data structures are generally categorized into two classes: primitive and non-primitive data structures. Primitive and Non-primitive Data Structures:  Primitive data structures are the fundamental data types which are supported by a programming language. Some basic data types are integer, real, character, and boolean. The terms ‘data type, basic data type’, and ‘primitive data type’ are often used interchangeably. INTRODUCTION: CLASSIFICATION OF DATA STRUCTURES: www.Jntufastupdates.com 2  Non-primitive data structures are those data structures which are created using primitive data structures. Examples of such data structures include linked lists, stacks, trees, and graphs.  Non-primitive data structures can further be classified into two categories: linear and non-linear data structures. Linear and Non-linear Structures:  If the elements of a data structure are stored in a linear or sequential order, then it is a linear data structure. o Examples include arrays, linked lists, stacks, and queues. o Linear data structures can be represented in memory in two different ways. One way is to have to a linear relationship between elements by means of sequential memory locations. The other way is to have a linear relationship between elements by means of links.  If the elements of a data structure are not stored in a sequential order, then it is a non-linear data structure. o The relationship of adjacency is not maintained between elements of a non-linear data structure. Examples include trees and graphs. Arrays:  An array is a collection of similar data elements. These data elements have the same data type. The elements of the array are stored in consecutive memory locations and are referenced by an index (also known as the subscript).  In C, arrays are declared using the following syntax: datatype name[size]; Ex: int marks[10]; limitations: o Arrays are of fixed size. o Data elements are stored in contiguous memory locations which may not be always available. o Insertion and deletion of elements can be problematic because of shifting of elements from their positions.