Introduction to Data Structures PDF

Introduction to Data Structures Module 1 9/17/2024 Prof. Shweta Dhawan Chachra 1  Data Data can be numeric or character When we process this data, it becomes information. Eg- MH32V2126, – A string, sequence of character t...

Introduction to Data Structures Module 1 9/17/2024 Prof. Shweta Dhawan Chachra 1  Data Data can be numeric or character When we process this data, it becomes information. Eg- MH32V2126, – A string, sequence of character type data – But when it represents the car registration number then it is processed data – I.e. information. 9/17/2024 Prof. Shweta Dhawan Chachra 2  DATA STRUCTURES Data may be organized in many different ways. The logical or mathematical model of a particular organization of data is called a Data Structure. Or In other words, a Data Structure is a way of organizing all the data items that considers not only the elements stored but also the relationship between them. 9/17/2024 Prof. Shweta Dhawan Chachra 3  Data Structure Data Structure is a way to organize the data in some way so we can perform operations on these data in effective ways. Eg-List, Stack, Queue, Tree 9/17/2024 Prof. Shweta Dhawan Chachra 4  Selection/choice of data structures The choice of Data Structure model depends on two considerations- 1) It must be rich enough in structure to mirror the actual relationships of the data in the real world. 2) The structure should be simple enough that one can effectively process the data when necessary, i.e. the type of operation to be performed. 9/17/2024 Prof. Shweta Dhawan Chachra 5  Data Structure Data Structures affects the design of both the structural and functional aspects of a program. 9/17/2024 Prof. Shweta Dhawan Chachra 6  Data Structure ALGORITHM+DATA STRUCTURE=PROGRAM Algorithm is a step by step procedure to solve a particular problem. To develop a program we should select an appropriate data structure for that algorithm. Thus , algorithm and its associated data structure form a program. 9/17/2024 Prof. Shweta Dhawan Chachra 7 CLASSIFICATION OF DATA STRUCTURES Data Structure Non- Primitive Primitive Data Data Structure Structure Integer Float Character Double Linear Non-Linear Array Lists Stack Queues Trees Graphs 9/17/2024 Prof. Shweta Dhawan Chachra 8  PRIMITIVE DATA STRUCTURES These are basic data structures and are directly operated upon by the machine level instructions. Primitive data structures of any programming language are the data types that are predefined in that programming language. The type and size of those data types are defined already. 9/17/2024 Prof. Shweta Dhawan Chachra 9  PRIMITIVE DATA STRUCTURES These in general have different representations on different computers. Integers, floating point numbers, character constants, double etc fall in this category. 9/17/2024 Prof. Shweta Dhawan Chachra 10 NON-PRIMITIVE DATA STRUCTURES These are more sophisticated data structures. These are derived from the basic data types. The non-primitive data structures emphasize on structuring of a – group of homogenous(same type) or – heterogenous (different type) data items. Eg- Arrays, lists, trees etc. 9/17/2024 Prof. Shweta Dhawan Chachra 11 NON-PRIMITIVE DATA STRUCTURES Classified as – Linear data structures – Non- Linear data structures 9/17/2024 Prof. Shweta Dhawan Chachra 12  Linear Data Structures A data structure is said to be linear – if its elements form a sequence or a linear list. Here elements are arranged in one dimension or linear fashion. All one-one relation can be handled through linear data structures. Eg- Lists, stacks and queues 9/17/2024 Prof. Shweta Dhawan Chachra 13  Arrays An array can be defined as a collection of homogenous data type. An array can store either all integers, all floating point numbers, all characters or any other complex data type. Declaration of an integer array is as follows- int a; 9/17/2024 Prof. Shweta Dhawan Chachra 14 Lists Linked lists are special lists of some data elements linked to one another. The logical ordering is represented by having each element pointing to the next element. Each element is called a node, which has two parts, INFO part which stores the information and pointer which points to the next element. 9/17/2024 Prof. Shweta Dhawan Chachra 15 Stacks 9/17/2024 Prof. Shweta Dhawan Chachra 16 Stacks  It could be thought of just like a stack of plates placed on table in a party,  a guest always takes off a fresh plate from the top, and  the new plates are placed on the top of the stack. 9/17/2024 Prof. Shweta Dhawan Chachra 17 Stacks  The plate which is at the top is the first one to be removed,  The plate which has been placed at the bottommost position remains in the stack for the longest period of time.  So, it can be simply seen to follow LIFO(Last In First Out)/FILO(First In Last Out) order. 9/17/2024 Prof. Shweta Dhawan Chachra 18 Stacks Stack is a linear data structure which follows a particular order in which the operations are performed. The order may be LIFO(Last In First Out) or FILO(First In Last Out). 9/17/2024 Prof. Shweta Dhawan Chachra 19 Stacks A Stack is an ordered collection of elements , but it has a special feature that deletion and insertion of elements can be done only from one end, called the top of the stack(TOP). 9/17/2024 Prof. Shweta Dhawan Chachra 20 Operation on Stacks Push operation-The insertion of an element into stack Pop operation - Deletion of an element from the stack In stack we always keep track of the last element present in the list with a pointer called top. 9/17/2024 Prof. Shweta Dhawan Chachra 21 Applications of stack: Expression evaluation and syntax parsing Balancing of symbols, paranthesis Infix to Postfix /Prefix conversion Reverse a String using Stack Redo-undo features at many places like editors, photoshop. Forward and backward feature in web browsers Used in many algorithms like Tower of Hanoi, tree traversals, stock span problem, histogram problem. 9/17/2024 Prof. Shweta Dhawan Chachra 22  Applications of stack: Backtracking – Backtracking is an algorithmic-technique for solving problems recursively by trying to build a solution incrementally, one piece at a time, removing those solutions that fail to satisfy the constraints of the problem at any point of time – Other applications can be Backtracking, Knight tour problem, rat in a maze, N queen problem and sudoku solver 9/17/2024 Prof. Shweta Dhawan Chachra 23  Backtracking-Finding the correct path in a maze. There are a series of points, from the starting point to the destination. We start from one point. To reach the final destination, there are several paths. Suppose we choose a random path. After following a certain path, we realise that the path we have chosen is wrong. So we need to find a way by which we can return to the beginning of that path. 9/17/2024 Prof. Shweta Dhawan Chachra 24  Backtracking-Finding the correct path in a maze. This can be done with the use of stacks. With the help of stacks, we remember the point where we have reached. This is done by pushing that point into the stack. In case we end up on the wrong path, we can pop the top point from the stack and thus return to the last point and continue our quest to find the right path. 9/17/2024 Prof. Shweta Dhawan Chachra 25  Applications of stack: Depth-first search – The prototypical example of a backtracking algorithm is depth-first search, which finds all vertices of a graph that can be reached from a specified starting vertex. In Graph Algorithms like Topological Sorting and Strongly Connected Components 9/17/2024 Prof. Shweta Dhawan Chachra 26  Applications of stack: Compile time memory management Almost all calling conventions 9/17/2024 Prof. Shweta Dhawan Chachra 27  Function calls using stack  Compile time memory management  A number of programming languages are stack-oriented,  meaning they define most basic operations as taking their arguments from the stack, and placing any return values back on the stack.  Eg- adding two numbers, printing a character 9/17/2024 Prof. Shweta Dhawan Chachra 28  Function calls using stack Stacks are an important way of supporting nested or recursive function calls. 9/17/2024 Prof. Shweta Dhawan Chachra 29  Function calls using stack The ways in which subroutines receive their parameters and return results—use a special stack (the "call stack") 9/17/2024 Prof. Shweta Dhawan Chachra 30  Function calls using stack Call stack holds information about procedure/function calling and nesting in order to switch to the context of the called function and restore to the caller function when the calling finishes. 9/17/2024 Prof. Shweta Dhawan Chachra 31  Applications of stack: Efficient algorithms – The nearest-neighbor chain algorithm, – Graham scan, an algorithm for the convex hull of a two-dimensional system of points. A convex hull of a subset of the input is maintained in a stack, which is used to find and remove concavities in the boundary when a new point is added to the hull Security – Some computing environments use stacks in ways that may make them vulnerable to security breaches and attacks. – Programmers working in such environments must take special care to avoid the pitfalls of these implementations. 9/17/2024 Prof. Shweta Dhawan Chachra 32 Data Structures | Stack | Question 2 Which one of the following is an application of Stack Data Structure? (A) Managing function calls (B) The stock span problem (C) Arithmetic expression evaluation (D) All of the above 9/17/2024 Prof. Shweta Dhawan Chachra 33 Data Structures | Stack | Question 2 Which one of the following is an application of Stack Data Structure? (A) Managing function calls (B) The stock span problem (C) Arithmetic expression evaluation (D) All of the above Answer: (D) 9/17/2024 Prof. Shweta Dhawan Chachra 34  Queues 9/17/2024 Prof. Shweta Dhawan Chachra 35  Real life Examples of Queue The people standing in a railway reservation row are an example of queue. Each new person comes and stands at the end of the row (rear end of queue) and persons getting their reservations confirmed , get out of the row from the front end. 9/17/2024 Prof. Shweta Dhawan Chachra 36  Real life Examples of Queue Our software queues have counterparts in real world queues. We wait in queues – to buy pizza, – to enter movie theaters, – to drive on a turnpike, and – to ride on a roller coaster. 9/17/2024 Prof. Shweta Dhawan Chachra 37 Queues A Queue is a linear structure which follows a particular order in which the operations are performed. The order is FIFO, Queues are first in first out type of data structures( FIFO). In a queue new elements are added to the queue from one end called Rear end and the elements are always removed from the other end called the Front end. 9/17/2024 Prof. Shweta Dhawan Chachra 38  Operations on Queue: Enqueue: – Adds an item to the queue – Enter or Insert an item from Rear end Dequeue: – Removes an item from the queue. – Service or Delete From the Front end 9/17/2024 Prof. Shweta Dhawan Chachra 39  Applications of Queue: Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU. Disk Scheduling 9/17/2024 Prof. Shweta Dhawan Chachra 40  Applications of Queue: CPU scheduling- When multiple processes require CPU at the same time, various CPU scheduling algorithms are used which are implemented using Queue data structure. 9/17/2024 Prof. Shweta Dhawan Chachra 41  Applications of Queue: CPU scheduling- 9/17/2024 Prof. Shweta Dhawan Chachra 42  Applications of Queue: When things don’t have to be processed immediately, but have to be processed in First In First Out order like Breadth First Search. When data is transferred asynchronously (data not necessarily received at same rate as sent) between two processes. Examples include IO Buffers, pipes, file IO, etc. Queue are used to maintain the play list in media players in order to add and remove the songs from the play-list. Courtesy:https://www.javatpoint.com/data-structure-queue 9/17/2024 Prof. Shweta Dhawan Chachra 43  Queue Example Accessing printer in multiuser environment-  If a printer is in process and more than one user wants to access the printer then  it maintains the queue for user requesting access and serves in FIFO manner for giving access. 17-09-2024 Prof. Shweta Dhawan Chachra 44 Difference between Stacks and Queues The difference between stacks and queues is in removing. – In a stack, we remove the item which was most recently added; – In a queue, we remove the item which was least recently added. 9/17/2024 Prof. Shweta Dhawan Chachra 45  Difference between Stacks and Queues 9/17/2024 Prof. Shweta Dhawan Chachra 46  Non-Linear Data Structures A data structure is said to be non-linear if traversal of nodes is non-linear in nature. Data elements are not arranged sequentially or linearly are called non-linear data structures. In a non-linear data structure, single level is not involved. Therefore, we can’t traverse all the elements in single run only. 9/17/2024 Prof. Shweta Dhawan Chachra 47  Non-Linear Data Structures A non-linear data structure has no set sequence of connecting all its elements and each element can have multiple paths to connect to other elements. 9/17/2024 Prof. Shweta Dhawan Chachra 48  Non-Linear Data Structures All one-many, many-one or many-many relations are handled through non-linear data structures. Every data element can have a number of predecessors as well as successors. Trees, graphs and tables are its examples. 9/17/2024 Prof. Shweta Dhawan Chachra 49  Linear Vs Non Linear Data Structures 9/17/2024 Prof. Shweta Dhawan Chachra 50 Trees A tree is a non- linear data structure used to represent hierarchical relationship existing among several data items. 9/17/2024 Prof. Shweta Dhawan Chachra 51  Tree Represents Hierarchy For eg- The organization structure of an Corporation 17-09-2024 Prof. Shweta Dhawan Chachra 52 Trees It is a finite set of one or more data items such that- There is a special data item called the root of the tree. Its remaining data items are partitioned into number of mutually exclusive subsets, each of which is itself a tree, and they are called subtrees. 9/17/2024 Prof. Shweta Dhawan Chachra 53  Applications of Tree Data Structure Store hierarchical data, like folder structure, organization structure, XML/HTML data. Binary Search Tree is a tree that allows fast search, insert, delete on a sorted data. It also allows finding closest item Heap is a tree data structure which is implemented using arrays and used to implement priority queues. 9/17/2024 Prof. Shweta Dhawan Chachra 54  Applications of Tree Data Structure B-Tree and B+ Tree : They are used to implement indexing in databases. Syntax Tree: Used in Compilers. Spanning Trees and shortest path trees are used in routers and bridges respectively in computer networks 9/17/2024 Prof. Shweta Dhawan Chachra 55  Applications of Tree Data Structure Trie : Used to implement dictionaries with prefix lookup. 9/17/2024 Prof. Shweta Dhawan Chachra 56 Graphs Graph is a non-linear data structure capable of representing many kinds of physical data structures. It has found its application in diverse fields like Geography, Chemistry and Engineering Sciences. 9/17/2024 Prof. Shweta Dhawan Chachra 57 Graphs A graph G(V,E) is a set of vertices V and a set of edges E. An edge connects a pair of vertices and many have weight such as length, cost etc. Vertices =point or circles Edges=arcs or line segment. Edge E=(V,W) where V and W are pair of vertices. 9/17/2024 Prof. Shweta Dhawan Chachra 58  GRAPHS Representation : Graph representation of a road network A road network is a simple example of a graph, Vertices represents cities and road connecting them are correspond to edges. 9/17/2024 Prof. Shweta Dhawan Chachra 59  GRAPHS Representation : V= { Delhi, Chenai, Kolkata, Mumbai, Nagpur } E= { (Delhi, Kolkata), (Delhi, Mumbai}, (Delhi, Nagpur), (Chenai, Kolkata), (Chenai, Mumbai), (Chenai, Nagpur), (Kolkata, Nagpur), (Mumbai, Nagpur) } 9/17/2024 Prof. Shweta Dhawan Chachra 60  Applications of Graph Data Structure ? 9/17/2024 Prof. Shweta Dhawan Chachra 61  Applications of Graph Data Structure Google maps Facebook World Wide Web Operating System 9/17/2024 Prof. Shweta Dhawan Chachra 62  Applications of Graph Data Structure Google maps – – ? 9/17/2024 Prof. Shweta Dhawan Chachra 63  Applications of Graph Data Structure In Computer science graphs are used to represent the flow of computation. Google maps – – uses graphs for building transportation systems, – where intersection of two(or more) roads are considered to be a vertex and – the road connecting two vertices is considered to be an edge, – thus their navigation system is based on the algorithm to calculate the shortest path between two vertices. 9/17/2024 Prof. Shweta Dhawan Chachra 64  Applications of Graph Data Structure In Facebook, – ? 9/17/2024 Prof. Shweta Dhawan Chachra 65  Social Network Analysis In Facebook, – users are considered to be the vertices and – if they are friends then there is an edge running between them. – Facebook’s Friend suggestion algorithm uses graph theory. – Facebook is an example of undirected graph. 9/17/2024 Prof. Shweta Dhawan Chachra 66  Social Network Analysis So, for Facebook, we can think of a node as a friend and the edge as the relationship that links the friends together. Below is a basic illustration of some friends in a network: 9/17/2024 Prof. Shweta Dhawan Chachra 67  Social Network Analysis From here we can start to measure centrality of the graph or the influence among friends. 9/17/2024 Prof. Shweta Dhawan Chachra 68  Social Network Analysis 9/17/2024 Prof. Shweta Dhawan Chachra 69  Social Network Analysis Degree centrality is a calculation of how many direct friends that any individual friend in the network has. Friends with a high degree of centrality are not necessary the most powerful or influential, but they act as hubs within the network. 9/17/2024 Prof. Shweta Dhawan Chachra 70  Social Network Analysis Brenda is acting as the hub in this social network since she has the most connections or highest degree within the network. 9/17/2024 Prof. Shweta Dhawan Chachra 71  Social Network Analysis Closeness Centrality- Calculates the shortest paths between all nodes, then assigns each node a score based on its sum of shortest paths. When to use it: For finding the individuals who are best placed to influence the entire network most quickly. Closeness centrality can help find good ‘broadcasters’ 9/17/2024 Prof. Shweta Dhawan Chachra 72 Applications of Graph Data Structure In World Wide Web, – web pages are considered to be the vertices. – There is an edge from a page u to other page v if there is a link of page v on page u. – This is an example of Directed graph. – It was the basic idea behind Google Page Ranking Algorithm. 9/17/2024 Prof. Shweta Dhawan Chachra 73 Applications of Graph Data Structure In Operating System, – we come across the Resource Allocation Graph where each process and resources are considered to be vertices. 9/17/2024 Prof. Shweta Dhawan Chachra 74 Applications of Graph Data Structure Edges are drawn from – resources to the allocated process, or – from requesting process to the requested resource. If this leads to any formation of a cycle then a deadlock may occur. 9/17/2024 Prof. Shweta Dhawan Chachra 75  Resource Allocation Graph With A Deadlock Suppose P3 requests for R2, Since no resource instance is free, a request edge P3->R2 is added So, Now Two cycles exist – P1->R1->P2->R3->P3->R2->P1 P2->R3->P3->R2->P2 P1,P2,P3 are deadlocked 9/17/2024 Prof. Shweta Dhawan Chachra 76  GATE CS 2004 The best data structure to check whether an arithmetic expression has balanced parentheses is a (GATE CS 2004) a) queue b) stack c) tree d) list 9/17/2024 Prof. Shweta Dhawan Chachra 77  GATE CS 2004 The best data structure to check whether an arithmetic expression has balanced parentheses is a (GATE CS 2004) a) queue b) stack c) tree d) list Answer(b) 9/17/2024 Prof. Shweta Dhawan Chachra 78