Module 1 PDF - Data Structures and Algorithms

UNIT 1 – OVERVIEW OF DATA STRUCTURES Data has to be examined carefully so that the most appropriate data type can be used. DATA STRUCTURES AND ALGORITHMS Basically...

UNIT 1 – OVERVIEW OF DATA STRUCTURES Data has to be examined carefully so that the most appropriate data type can be used. DATA STRUCTURES AND ALGORITHMS Basically, anything that can store data can be It is important to know how data is represented in called as a data structure, hence Integer, Float, memory (data structure) and how it is represented Boolean, Char, etc., all are data structures. They on the disk (file structure). are known as Primitive Data Structures or Basic DATA STRUCTURE Type. is a way of collecting and organizing data in such a way that we can perform operations on these data in an effective and sometimes efficient way. In order to solve problems efficiently one can do the following: 1. Analyze the problem to determine the resource constraints a solution must meet. 2. Determine the operations that must be supported (e.g., record search, insertion, deletion, etc.) BASIC DATA TYPE OR PRIMITIVE DATA 3. Quantify the constraints for each operation (e.g., STRUCTURES search operations must be very fast) represent a set of individual data and is 4. Select data structure that best meet these frequently used to create a program. requirements. Sometimes called atomic data structure as they represent a form where data can no longer be COST AND BENEFITS divided or have no parts. This group can be Each data structures requires spaces for each data further divided into Simple Type and Pointer item it stores, time to perform each operation, and Type. some programming effort to implement it. SIMPLE TYPE Every data structure has costs and benefits. Rarely Simple type is the most basic data type which is one data structure is better than another in all usually declared according to the syntax rule of a situations. One may permit faster search (or programming language. insertion or deletion) operations than the other Most common data types fall under this group. but that does not mean that it is better. INTEGER TYPE DATA STRUCTURES, DATA TYPE AND represents integers or whole numbers where in ABSTRACT DATA TYPE the maximum or minimum value is the unit of This notion of data structures involves: data that a computer can process at one time § a set of data elements; and is determined by the length of one word. § the way the data elements are logically related; REAL NUMBER TYPE § and a set of allowable operations on the data represent fixed-point and floating-point numbers elements. CHARACTER TYPE From this notion, data structures are structures comprised of alphabets, numerals, and symbols programmed to store ordered data, so that various as characters. A character code is expressed as a operations can be performed on it easily. binary number inside a computer. LOGICAL TYPE It represents the knowledge of data to be organized in memory, both primary and secondary. sometimes referred to as Boolean type where It should be designed and implemented in such a the values are used in performing logical way that it reduces the complexity and increases operations such as AND, OR, and NOT. the efficiency. ENUMERATION TYPE a data type that enumerates all possible values of variables. PARTIAL TYPE used to specify an original-value subset by constraining existing data types, that is identifying upper and lower limits of a variable. POINTER TYPE Pointer type are addresses that are allocated in a main memory unit. Pointer types are used to refer to variables, file records, or functions. DATA TYPE term usually used synonymously with data structures but in itself is different from data structures. It is a set of values from which a variable, constant, function, or other expression may take its value. Data type can be thought of as a set of the “same kind” of data processed by the computer.  STRUCTURE TYPE OR SIMPLE DATA STRUCTURE is a data structure that contains a basic data type or any of the defined data types as its elements. Arrays, strings, and records are examples of Structure Type. They represent a collection of data elements. ARRAY TYPE OR ARRAY Defining an ADT depends on the application one is simply a finite set of elements having the same is making and there are different definitions for type referenced under a common name. If this the same application. type is a character type, we refer to it as a string An ADT hides implementation details providing STRING different implementations for the same ADT. or a collection of character elements. When the ADT is given, its data type can be used RECORD TYPE by the programmer (e.g., string and math also a set of elements but this time of different libraries in C). When the implementation data types referenced under a common name. This changes, the programs need not changed. is useful if we would like to organized a collection of data but do not want to manage them CLASSIFICATION OF DATA STRUCTURES BASED separately (individually). ON CHARACTERISTICS The different data structures can also be ABSTRACT DATA TYPE classified on the basis of their characteristics. Abstract Data Type is a part of Basic Data Structure The following table presents the different characteristics and but represents those under Problem- oriented how they are described: Data Structure. CHARACTERISTIC DESCRIPTION ADT is almost always synonymous to Data Structures but represents more of a logical LINEAR In linear data structures, the data items are description (abstract) rather than actual arranged in a linear implementation. sequence. ADT is basically a mathematical model where a set Example: Array of data values and its associated operations are precisely specified independent of any particular NON-LINEAR For non-linear data implementation. structures, the data items are not in sequence. Example: Tree, Graph HOMOGENEOUS Homogeneous data structures represent a ADT is a kind of data abstraction where a type’s structure whose internal form is hidden (information hiding) behind elements are of the a set of access functions. same type. By data abstraction, we mean any implementation Example: Array of data in which the implementation details are NON- In Non-homogeneous hidden (abstracted) from the user. Hiding data on HOMOGENEOUS data structure, the the level of data type is often called data elements may or may encapsulation. not be of the same type. Think of ADT as a black box where inputs and Example: Structures outputs are known but how things are STATIC Static data structures programmed are not (ADTs hide implementation are those whose sizes details). This idea keep internal calculations private and structures providing better modularity and allows for localize associated memory changes and better division of labor. locations are fixed, at A data structure is the implementation of an ADT compile time. where the operations associated with the ADT are Example: Array implemented by one or more functions. DYNAMIC Dynamic structures are LOGICAL AND PHYSICAL FORMS those which expands or Every data items have both a logical and physical shrinks depending upon form. the program need and LOGICAL FORM its execution. Also, their definition of the data item within an ADT (e.g. associated memory integers in mathematical sense: +,-, *, / locations changes. (operations) Example: Linked List PHYSICAL FORM created using pointers. implementation of the data item (e.g. 16 or 32 bit integers)  TYPES OF DATA STRUCTURES In programming, they help organize code and Data structure types are determined by what types data, with examples like Python's lists and of operations are required or what kinds of dictionaries or JavaScript's arrays and objects. algorithms are going to be applied. Essential in software designing by facilitating the These types include: storage and retrieval of information. ARRAYS IMPORTANCE OF DATA STRUCTURES An array stores a collection of items at adjoining Vital for efficiently managing large data sets, memory locations. aiding in memory allocation, data relationships, Items that are the same type get stored together and processing. They play a key role in systems so that the position of each element can be like databases and indexing services. calculated or retrieved easily. Selecting the appropriate data structure is Arrays can be fixed or flexible in length. crucial, as an unsuitable choice can lead to slow STACKS runtimes or unresponsive code. A stack stores a collection of items in the linear Factors to consider when choosing a data order that operations are applied. structure include the type of data being stored, This order could be last in first out (LIFO) or first in data placement, sorting requirements, and first out (FIFO). memory allocation needs. QUEUES A queue stores a collection of items similar to a stack However, the operation order can only be first in first out. FIFO LINKED LISTS A linked list stores a collection of items in a linear order. Each element, or node, in a linked list contains a data item as well as a reference, or link, to the next item in the list. TREES A tree stores a collection of items in an abstract, hierarchical way. Each node is linked to other nodes and can have multiple sub-values, also known as children. GRAPHS A graph stores a collection of items in a non-linear fashion. Graphs are made up of a finite set of nodes, also known as vertices, and lines that connect them, also known as edges. These are useful for representing real-life systems such as computer networks. TRIES A trie, or keyword tree, is a data structure that stores strings as data items that can be organized in a visual graph. HASH TABLES A hash table, or a hash map, stores a collection of items in an associative array that plots keys to values. A hash table uses a hash function to convert an index into an array of buckets that contain the desired data item. § These are considered complex data structures as they can store large amounts of interconnected data. Examples of primitive, or basic, data structures are integers, floats, Booleans and characters. USES OF DATA STRUCTURES Data structures are used to implement the physical forms of abstract data types, enabling various applications such as representing relational databases as binary trees.