Untitled Quiz

Data Structures Overview

• Data Structures are used to organize data in a computer so it can be used efficiently
• Good programs are correct, easy to read, understand, debug, and modify
• Data management involves activities like data collection, organization, and quality assurance
• A data structure is a group of data elements under one name, defining how data is stored and organized in a computer

Basic Terminology

• A good program: Runs correctly, is easy to read/understand, easy to debug, and easy to modify
• Data management concepts are needed for writing efficient programs

Basic Terminology

• Data Management is complex, including:
  • Data collection
  • Data organization into appropriate structures
  • Procedures for quality assurance

Basic Terminology- Applications

• Data structures apply to:
  • Compiler design
  • Operating Systems
  • Statistical analysis packages
  • DBMS
  • Numerical analysis
  • Simulation
  • Artificial intelligence
  • Graphics

Basic Terminology- Problem Solving

• When selecting a data structure:
  • Analyze the problem to determine needed operations (e.g., inserting, deleting, searching)
  • Quantify resource constraints for each operation
  • Choose the best data structure to meet needs

Basic Terminology- Process

• Data structure selection is a crucial decision affecting program performance.
• Steps for building Data Structures:
  • Gather data & identify the needed operations
  • Develop data representation
  • Implement data structure/algorithm

Data Structure Organization

• Data: A value or set of values (e.g., student marks, employee name, customer address)
• Record: A collection of related data items (e.g., name, address, course, marks)
• File: A collection of related records (e.g., all students in a class, employees in an organization)
• Primary Key: A unique identifier for each record in a file (e.g., student ID, employee ID)

Classification of Data Structures

• Primitive Data Structures: Fundamental data types (integer, float, character, boolean)
• Non-primitive Data Structures: Created using primitive data to store, retrieve, manipulate data
• Linear Data Structures (elements in order): Arrays, Linked Lists, Stacks, Queues
• Non-linear Data Structures (no sequential order): Trees, Graphs, Hash Tables

Linear Data Structure

• Linear data structures store elements in a sequential manner; examples: arrays, linked lists, stacks, queues
• Arrays: Store elements consecutively in memory; have fixed size
• Linked Lists: Elements linked through pointers; have flexible size
• Stacks: Insertion and deletion at one end (LIFO - Last In, First Out)
• Queues: Insertion at one end, deletion at the other (FIFO - First In, First Out.)

Non-Linear Data Structure

• Elements are not stored sequentially. Examples include trees, graphs, hash tables.
• Trees: Hierarchical data structures with a root node; nodes connected by branches
• Graphs: Vertices (nodes) and edges (connections); connections can be complex
• Hash Tables: Data management strategy based on hashing algorithms; efficient search, insertion and deletion operation.

Arrays

• Arrays store items of the same data type sequentially in memory.

• Arrays have a fixed size; indices start from 0

• Advantages

  • Easy access to elements using indices

• Disadvantages

  • Fixed size

Linked Lists

• Linked lists have nodes consisting of data and a pointer to the next node to accommodate dynamic sizes.
• Advantages
  • Flexible size
  • Easy insertion/deletion
• Disadvantages
  • Slow search
  • More space needed

Stacks

• Last-In, First-Out (LIFO) structure; insertion and deletion only at the top.
• Operations: push (add to top), pop (remove from top), peek (view the top element)
• Applications: Function calls, undo/redo operations

Queues

• First-In, First-Out (FIFO) structure; insertion at one end, deletion at the other.
• Operations: enqueue (add to rear), dequeue(remove from front), peek (view front element)
• Used in tasks involving waiting lines, buffers.

Trees

• Non-linear Hierarchical data structures.

• Nodes organized in a tree-like structure.

• Binary Trees: Each node has at most two children (left and right).

• Root: Topmost node.

• Leaf: Nodes with no children.

• Applications: Representing hierarchies, organizing data, searching algorithms

Graphs

• Non-linear data structure with vertices (nodes) and edges connecting them.
• Nodes represent objects, edges show relationships.
• Applications: Maps, social networks, scheduling

Operations on Data Structures

• Traversing: Access each item once. (e.g., print names of all students in a class)
• Searching: Finding an item satisfying a given criterion. (e.g., finding students with 100 in Math)
• Inserting: Adding new items. (e.g., adding a new student to the list)
• Deleting: Removing an item. (e.g. removing a student who left the course)
• Sorting: Arranging items in a specific order. (e.g. alphabetical order of students names.)
• Merging: Combining two sorted lists into one.

Abstract Data Type (ADT)

• ADT is a mathematical model of data, with a set of operations defined on the data but independent of its implementation.
• Focuses on what an object does, ignoring the implementation details.