Introduction.pdf

DATA STRUCTURES Introduction Prof. Khalil Al-Shqeerat CS Dept. – Qassim University  Basic concepts Classification of data structures OUTLINE Linear and non-linear data structures Operations on data structure How to choose a data structure? INTRODU...

DATA STRUCTURES Introduction Prof. Khalil Al-Shqeerat CS Dept. – Qassim University  Basic concepts Classification of data structures OUTLINE Linear and non-linear data structures Operations on data structure How to choose a data structure? INTRODUCTION What is data? Quantities, characters or symbols on which operations are performed by a computer Stored on external memory May be and transmitted in the form of electrical signals. Example: C = A + B (A & B is data) When data becomes information? If data is arranged in a systematic way then it gets a structure and become meaningful. MEANINGFUL OR PROCESSED DATA IS CALLED INFORMATION. DATA Values or set of values. A data item refers to a single unit of values. Data items that are divided into sub items are group items; those that are not are called elementary items. For example, an employee’s name may be divided into three sub items – first name, middle name and last name An entity has specific attributes or properties that may be assigned values. The values may be either numeric or non-numeric. EXAMPLE WHAT IS A DATA STRUCTURE? A data structure is the systematic way to organize data so that it can be used efficiently. It is a group of data elements stored together under one name Example: arrays Instead of creating multiple variables of same type. Storing strings is equivalent of storing a sequence of characters. It is also referred as “Abstract Data Type (ADT)” ADT is a type (or class) for objects whose behavior is defined by a set of values and a set of operations The challenge is to select the most appropriate data structure for the problem CLASSIFICATION OF DATA STRUCTURES The data structure can be classified into two categories primitive data structure Storing the value of only one data type Non-primitive data structure. Storing the value of more than one data type PHYSICAL DATA STRUCTURES Actual implementations of data structures in memory. Array, Linked list Array Linked list LOGICAL DATA STRUCTURES Logical implementation of data over physical memory. Stack, Queue, Tree Tree Queue Stack STATIC VS. DYNAMIC DATA STRUCTURES Static data structure Collection of data in memory which have a fixed size It can store a limited amount of elements or data in memory. Array is an example of static data structure. Dynamic Data Structure Collection of data in memory which do not have a fixed size Its size can be modified during the operations performed on it It can store a variable amount of elements or data in memory. Linked List is an example of dynamic data structure. LINEAR DATA STRUCTURES Data elements are arranged sequentially or linearly Every element is attached to its previous and next adjacent Single level is involved. It can traverse all the elements in single run only. Easy to implement because computer memory is arranged in a linear way. Array, Stack, Queue, Linked list are examples of Linear data structures. NON-LINEAR DATA STRUCTURES Data elements are not arranged sequentially or linearly. Hierarchical multiple levels are involved. It can’t traverse all the elements in single run only. Its implementation is complex. It utilizes computer memory efficiently in comparison to a linear data structure. Its examples are trees and graphs SUMMARY DATA STRUCTURE OPERATIONS Different types of operations can be performed for the manipulation of data in every data structure. Traversal: accessing each record/node exactly once so that certain items in the record may be processed. Search: Finding the location of the desired node with a given key value, or to satisfy one or more conditions. Insertion: Adding a new node/record to the structure. Deletion: Removing a node/record from the structure. Sort: arranging all data items in a particular order. Merge: combining the data items of two different sorted list into a single sorted list. HOW TO CHOOSE A DATA STRUCTURE? The choice of a appropriate data structure depends on the following factors: Based on the operations that will be performed A linked list used to perform insertions and deletions. An array is used to perform indexing. Based on the time complexity of the operations For example, to perform searches frequently, a binary search tree is used. Based on the space complexity of the operations For example, to store a lot of data, you should use an array. based on the amount of memory used For example, to store a lot of data in memory, you should use a linked list