Introduction.pdf
Document Details
Uploaded by Deleted User
Full Transcript
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