Data structure Basic ,Fundamentals, Types

Data structure introduction

1. Introduction to Data Structures Presented by : Mrs.Vijaya Lakshmi A Research Scholar , Department of Computer Science and Engineering, Pondicherry University

2. Data Structures Data structures are fundamental building blocks in computer science. They are essential for organizing, storing, and retrieving data efficiently. Understanding data structures is crucial for writing effective algorithms and building efficient software.

3. What are Data Structures? Data structures are ways to organize and store data in a computer's memory. Organization Data is arranged in specific relationships, like a sequence or hierarchy, which allows for easy access and manipulation. Efficiency Different data structures have varying efficiency for different operations like searching, insertion, and deletion. Memory Management Data structures manage memory allocation and deallocation for efficient storage and retrieval of data.

4. Types of Data Structures Data structures can be categorized into different types based on their underlying organization and operations. Linear Data elements are arranged sequentially, like in a list or queue. 2 Non-linear Data elements have hierarchical relationships, like in trees or graphs. 3 Static Fixed size structures with predefined capacity. 4 Dynamic Structures that can grow or shrink based on the data they hold. 1

5. Arrays Arrays are the simplest data structures that store a collection of elements of the same data type. Advantage Efficient random access Disadvantage Fixed size, inefficient insertion/deletion

6. Linked Lists Linked lists are dynamic data structures that consist of nodes connected in a sequence. Node Each node contains data and a pointer to the next node. Head Points to the first node in the list. Tail Points to the last node in the list .

7. Stacks and Queues Stacks and queues are linear data structures that follow specific access patterns. Stack (LIFO) Last-In, First-Out; data is added and removed from the top. Push Pop Peek Queue (FIFO) First-In, First-Out; data is added at the rear and removed from the front. Enqueue Dequeue Peek

8. Trees Trees are hierarchical data structures where elements are connected in a parent child relationship. Root The topmost element of the tree . Nodes Each element in the tree . Edges Connections between nodes. Leaves Nodes with no children .

9. Graphs Graphs are non-linear data structures consisting of nodes (vertices) connected by edges. Nodes Represent data points or entities. Edges Represent relationships or connections between nodes. Directed Edges Edges with a specific direction. Undirected Edges Edges with no directionality.

10. Understanding the Shortest Path Problem Origin and Destination The shortest path problem involves finding the shortest route between a designated origin node and a specific destination node in a graph. This path represents the most efficient route, minimizing distance, time, or any other specified cost. Weighted Edges In weighted graphs, each edge has an associated weight, representing a value associated with traversing that edge. For example, in a road network, edge weights could represent the distance between two intersections. Real-World Applications Shortest path problems are encountered in various real-world scenarios, including route planning, network routing, and transportation optimization. The algorithm helps find the most efficient path for navigating complex networks.

11. Single-Source Shortest Path problem Dijkstra algorithm and Bellman Ford Single-Pair Shortest Path problem A* algorithm All-Pairs Shortest Path problem Warshall-Floyd algorithm

12. Dijkstra's algorithm Dijkstra's algorithm - is a solution to the single-source shortest path problem in graph theory.    Works on both directed and undirected graphs. However, all edges must have nonnegative weights. Input: Weighted graph G={E,V} and source vertex v ∈ V , such that all edge weights are nonnegative   Output: Lengths of shortest paths (or the shortest paths themselves) from a given source vertex v ∈ V to all other vertices

13. Dijkstra pseudocode Dijkstra(v1, v2): for each vertex v : // Initialization v's distance := infinity. v's previous := none. v1's distance := 0. List := {all vertices}. while List is not empty: v := remove List vertex with minimum distance. mark v as known. for each unknown neighbor n of v : dist := v's distance + edge ( v , n)'s weight. if dist is smaller than n's distance: n's distance := dist. n's previous := v . reconstruct path from v2 back to v1, following previous pointers.

14. Time Complexity: Using List The simplest implementation of the Dijkstra's algorithm stores vertices in an ordinary linked list or array Good for dense graphs (many edges) |V| vertices and |E| edges Initializati on O(|V|) While loop O(|V|) Find and remove min distance vertices O(|V|) Potentially |E| updates Update costs O(1) Total time O(|V 2 | + |E|) = O(|V 2 | )

15. Time Complexity: Priority Queue For sparse graphs, (i.e. graphs with much less than |V 2 | edges) Dijkstra's implemented more efficiently by priority queue Initializati on O(|V|) using O(|V|) buildHeap While loop O(|V|) Find and remove min distance vertices O(log |V|) using O(log |V|) deleteMin Potentially |E| updates Update costs O(log |V|) using decreaseKey Total time O(|V|log|V | + | E|log|V |) = O(|E|log|V |) |V| = O(|E|) assuming a connected graph