Introduction to Data Structures PDF

Module 1 Introduction to Data Structures Presenter: Er. Bandani kumari Basic Terminologies: Elementary Data Organizations What is a Data Structure? 1. A data structure is a specific way of arranging the data in a computer so that its usage is more effective and efficient. 2....

Module 1 Introduction to Data Structures Presenter: Er. Bandani kumari Basic Terminologies: Elementary Data Organizations What is a Data Structure? 1. A data structure is a specific way of arranging the data in a computer so that its usage is more effective and efficient. 2. Data structures are a set of algorithms. 3. They are useful to store data in a way that makes it extremely accessible and easy to manipulate. Basic Terminologies: Data Data: Data can be defined as an elementary value or the collection of values, for example, student's name and its id are the data about the student. Data items that are not able to divide into sub-items are called Elementary items. For example: age, city-name Data items that are divided into sub-items are called Group items (Composite Items). ○ For Example: An Employee Name may be divided into three subitems- first name, middle name, and last name. Basic Terminologies: Entity Entity: An entity is a real-world object that has certain attributes or properties which may be assigned values. The values may be either numeric or non-numeric. ○ For Example: Attributes- Names, Age, Sex, SSN Values- Rohan, 34, M, 134-34-5533 Entities with similar attributes form an entity set. Each attribute of an entity set has a range of values (domain), the set of all possible values that could be assigned to the particular attribute. Basic Terminologies: Field, Record, File Field is a single elementary unit of information representing an attribute of an entity. Record is the collection of field values of a given entity. File is the collection of records of the entities in a given entity set. Database is the collection of files. Key is a data field that uniquely identifies a record. For example: Roll no. of a student. Basic Terminologies: Records Records may also be classified according to length. A file can have fixed-length records or variable-length records. In fixed-length records, all the records contain the same data items with the same amount of space assigned to each data item. In variable-length records file records may contain different lengths. Variable-length records have a minimum and a maximum length. Basic Terminologies: Data Types Data Type defines the type of data - the collection of values it can take and a set of operations that can be performed on these values. Data type determines how much space is required by a particular variable. ABSTRACT DATA TYPE: It defines a set of values and what operations can be performed on them but hides the implementation details of these operations. ○ For example: Stack ADT has operations Push and Pop. Data Structures V/S Abstract Data Type Data Structures Abstract Data Type 1. It actually holds data. 1. It is only a concept, and is 2. It deals with concrete data-less. representation of a data type. 2. It deals with logical description 3. It deals with processing time of a data type. and storage space required. 3. It does not deal with running time or memory space 4. A Data Structure tells how an required. ADT is implemented and tells 4. ADT hides implementation how operations work. details (deals with what is to be done, not how it is done). Basic Terminologies: Data Structures Data Structure can be defined as the group of data elements which provides an efficient way of storing and organising data in the computer so that it can be used efficiently. Some examples of Data Structures are arrays, Linked List, Stack, Queue, etc. Data Structures are widely used in almost every aspect of Computer Science i.e. Operating System, Compiler Design, Artificial intelligence, Graphics and many more. Basic Terminologies: Data Structures (Contd…) The logical or mathematical model of a particular organization of data is called a Data Structure. Data Structures are the main part of many computer science algorithms as they enable the programmers to handle the data in an efficient way. It plays a vital role in enhancing the performance of a software or a program as the main function of the software is to store and retrieve the user's data as fast as possible. Data Structures: Advantages Efficiency: Data is organized to form a data structure in such a way that all items are not required to be searched and required data can be searched instantly. Reusability: Data structures are reusable, i.e. once we have implemented a particular data structure, we can use it at any other place. Abstraction: Data structure is specified by the ADT which provides a level of abstraction. The client program uses the data structure through interface only, without getting into the implementation details. Classification of Data Structures Figure 1: Classification of Data Structures Classification of Data Structures Data structures are generally classified into : 1. Primitive data Structures: Primitive data structures are the fundamental data types which are supported by a programming language. Basic data types such as integer, real, character and Boolean are known as Primitive data Structures. These data types consists of characters that cannot be divided and hence they also called simple data types. 2. Non- Primitive data Structures: Non-primitive data structures are those data structures which are created using primitive data structures. Examples of non-primitive data structures is the processing of complex numbers, linked lists, stacks, trees, and graphs. Classification of Non-primitive Data Structures (Contd…) 1) Linear Data Structure: A data structure is said to be linear if its elements form a sequence or a linear list. The common examples of linear data structure are Arrays, Queues, Stacks, Linked lists. Classification of Non-linear Data Structures (Contd…) 2) Non-linear Data Structure: A data structure is said to be non-linear if the data are not arranged in sequence or a linear. The insertion and deletion of data is not possible in linear fashion. This structure is mainly used to represent data containing a hierarchical relationship between elements. Trees and graphs are the examples of non-linear data structure. Linear Data Structures 1) Arrays: An array is a collection of similar type of data items and each data item is called an element of the array. The data type of the element may be any valid data type like char, int, float or double. The elements of array share the same variable name but each one carries a different index number known as subscript. The array can be one dimensional, two dimensional or multidimensional. Figure 2: Representation of an Array Linear Data Structures (Contd…) 2) Linked List: Linked list is a linear data structure which is used to maintain a list in the memory. It can be seen as the collection of nodes stored at non-contiguous memory locations. Each node of the list contains a pointer to its adjacent node. Figure 3: Example of Linked List Linear Data Structures (Contd…) 3) Stack: Stack is a linear list in which insertion and deletions are allowed only at one end, called top. A stack is an abstract data type (ADT), can be implemented in most of the programming languages. It is named as stack because it behaves like a real-world stack, for example: - piles of plates or deck of cards etc. Figure 4: Example of Stacks Linear Data Structures (Contd…) 4) Queue: Queue is a linear list in which elements can be inserted only at one end called rear and deleted only at the other end called front. It is an abstract data structure, similar to stack. Queue is opened at both end therefore it follows First-In-First-Out (FIFO) methodology for storing the data items. Figure 5: Queue Data Structure Non-Linear Data Structures 1) Trees: Trees are multilevel data structures with a hierarchical (parent-child) relationship among its elements known as nodes. The bottom-most nodes in the hierarchy are called leaf node while the topmost node is called root node. Each node contains pointers to point adjacent nodes. Each node in the tree can have more than one children except the leaf nodes whereas each node can have at most one parent except the root node. Figure 6: Tree Data Structure Non-Linear Data Structures 2) Graphs: Graphs can be defined as the pictorial representation of the set of elements (represented by vertices) connected by the links known as edges. A graph is different from tree in the sense that a graph can have cycle while the tree can not have the one. Figure 7: Graph Data Structure Operations on data structure ❖ Traversing: Every data structure contains the set of data elements. Traversing the data structure means visiting each element of the data structure in order to perform some specific operation like searching or sorting. ❖ Insertion: Insertion can be defined as the process of adding the elements to the data structure at any location. If the size of data structure is n then we can only insert n-1 data elements into it. ❖ Deletion:The process of removing an element from the data structure is called Deletion. We can delete an element from the data structure at any random location. Operations on data structure (Contd…) ❖ Searching: The process of finding the location of an element within the data structure is called Searching. There are two algorithms to perform searching, Linear Search and Binary Search. ❖ Sorting: The process of arranging the data structure in a specific order is known as Sorting. There are many algorithms that can be used to perform sorting, for example, insertion sort, selection sort, bubble sort, etc. ❖ Merging: When two lists List A and List B of size M and N respectively, of similar type of elements, clubbed or joined to produce the third list, List C of size (M+N), then this process is called merging. REFERENCES 1. “Data Structures with C (Schaum's Outline Series)”, Seymour Lipschutz, 1st edition,McGraw Hill 2. “Fundamentals of Data Structures”, Illustrated Edition by Ellis Horowitz, SartajSahni, Computer Science Press. 3. Algorithms, Data Structures, and Problem Solving with C++”, Illustrated Edition by Mark Allen Weiss, Addison-Wesley Publishing Company