Data Structures Overview

Data Structures

• Data structure is a specific way of arranging data in a computer for efficient use.
• Data structures are crucial components of algorithms, enabling efficient data handling and enhancing software performance.
• Data structures are used across various computer science aspects, including operating systems, compilers, artificial intelligence, and graphics.
• Data structures are fundamental to effectively storing and retrieving user data in software.

Data Structures Examples

• Arrays: Fixed-size structures holding elements of the same data type. Random access is possible due to indexing.
• Linked Lists: Sequential structures with items linked to each other. Data is accessed sequentially, and random access is not possible.
• Stacks: LIFO (Last-In, First-Out) structure; useful in many programming languages. Elements are added (pushed) and removed (popped) from the same end.
• Queues: FIFO (First-In, First-Out) structure; useful in queuing operations. Elements are added (enqueued) at one end and removed (dequeued) from the other end.
• Trees: Hierarchical data structures where data is organized hierarchically. Different from linked lists, which link items linearly.
• Graphs: Consisting of a finite set of vertices (or nodes) and a set of edges connecting these vertices.

Elementary Data Organization

• Data: Elementary value (e.g., student's name, roll number)
• Group Items: Data items with subordinate data items (e.g., student's first and last name)
• Records: Collection of various data items (e.g., student's name, address, course, marks)
• Files: Collections of records of one type (e.g., a list of employees in a bank).
• Entities: Person, place, thing, event, or concept.

Data Structures vs. Data Types

• Data type: Describes data that share a common characteristic. (e.g., integer, string).
• Data structure: Describes a particular way of organizing data so that operations and algorithms are more easily applied (e.g., arrays, linked lists).

Categories of Data Structures

• Primitive Data Structures: Supported at the machine level (e.g., integer, floating point, character, boolean).
• Non-Primitive Data Structures: Derived data structures built from primitive structures.
• Linear Data Structures: Data elements are arranged sequentially (e.g., arrays, stacks, queues, linked lists).
• Non-linear Data Structures: Data elements are not arranged sequentially (e.g., trees, graphs).

Data Structures Operations

• Traversing: Accessing each data item exactly once
• Searching: Finding the location of a data item (if present)
• Inserting: Adding a new data item
• Deleting: Removing an existing data item
• Sorting: Arranging data items in a specific order (e.g., ascending or descending)
• Merging: Combining two sorted files into a single sorted file

Data Structure Applications

• Used in efficient searching and retrieving of data.
• Used in CPU job scheduling and disk scheduling.
• Useful for text editors (e.g., undo/redo functions)
• Used in symbolic tables for balancing parenthesis.
• Useful in representing sparse matrices.
• Used in shortest path algorithms, computer games, maps, satellite navigation systems.

Algorithms

• Step-by-step procedures defining instructions to achieve a desired output.
• Categories include searching, sorting, inserting, updating, and deleting data.
• Important characteristics include unambiguous steps, clear and unique meanings, finite steps, and well-defined inputs and outputs.

Algorithm Characteristics

• Unambiguous: Clear, unambiguous steps, unambiguous input/outputs
• Input: Zero or more well-defined inputs
• Output: One or more well-defined outputs matching the desired output
• Finiteness: Terminates after a finite number of steps
• Feasibility: Should be feasible with the available resources.
• Independent: Should have step-by-step directions independent of any programming code.

Algorithm Complexity

• Time Factor: Number of key operations (e.g., comparisons in sorting).
• Space Factor: Maximum memory space required by the algorithm.
• Complexity (f(n)): Describes the running time or storage space based on input size (n).
• Space Complexity: Amount of memory space required by an algorithm during its life cycle. Components include fixed part (independent of problem size) and variable part (dependent on problem size).

String Operations

• strlen(): Computes string length
• strcpy(): Copies a string to another
• strcat(): Concatenates two strings.
• strcmp(): Compares two strings
• strlwr(): Converts to lowercase
• strupr(): Converts to uppercase

Arrays

• Array is a container holding a fixed number of items of the same type.
• Element: Each item in the array.
• Index: Numerical identifier for each element's location within the array.
• Basic Operations (e.g., traversal, insertion, deletion, search)

Multi-Dimensional Arrays

• Arrays with more than one dimension. Often used to represent tables or matrices.

Parallel Arrays

• Collection of multiple arrays of the same size; array elements are related to each other.

Sparse Matrices

• Matrices with fewer non-zero elements than zero elements. Efficient representations are required.

Linked Lists

• Nodes: Items in the linked list. Each node contains data and a link to the next node.
• Linked List Representations: Use variables for storing data and the address of the next node's address in memory.

Array vs. Linked List

• Arrays: Contiguous memory locations; random access; fixed size; slower insertion/deletion
• Linked Lists: Non-contiguous memory locations; sequential access; dynamic size; faster insertion/deletion

Linked List Operations

• Traversal: Visiting each node
• Insertion: Adding a new node
• Deletion: Removing an existing node
• Searching: Locating a specific node

Header Linked Lists

• Contains a special node at the beginning.
• Used to store the size of the linked list efficiently.

Two-way Linked Lists (Doubly Linked Lists)

• Links to both the next and previous node.
• Navigation possible in both directions (forward and backward).

Circular Linked Lists

• The last node points to the first node, forming a loop.
• Used for traversing the list without ending conditions.

Stacks

• LIFO (Last-In, First-Out): Elements added and removed from the same end.
• Operations: push (add to stack), pop (remove from stack), peek (view the top element without removing)
• Implementation: Array, Linked List

Queues

• FIFO (First-In, First-Out): Elements added at one end and removed from the other.
• Operations: enqueue (add to queue), dequeue (remove from queue), peek (view the front element without removing)
• Implementation: Array, Linked List

Priority Queues

• Queue extension; elements have associated priorities. Higher priorities are served first.
• Implementation: Use queue or heap for efficient prioritizing.

Circular Queues

• Elements wrap around (first position follows last position) to manage memory use more efficiently.
• Operations similar to regular queues.

Graph Terminology

• Vertex (Node): A point in a graph.
• Edge: A connection between two vertices.
• Adjacency: Two vertices are adjacent if connected by an edge.
• Path: A sequence of edges connecting two vertices.
• Directed Graph: Edges have direction; (u,v) does not imply (v,u).
• Undirected Graph: Edges do not have direction.

Graph Representations

• Adjacency Matrix: 2D array representing vertex connections via 1s and 0s.
• Adjacency List: An array of linked lists; each index corresponds to a vertex; adjacent vertices are stored in a linked list at that index.

Graph Operations

• Checking for element: Verifying if an element is part of the graph.
• Graph Traversal: Visiting all vertices systematically.
• Adding edges/vertices: Modifying the graph.
• Finding paths: Identifying paths between vertices.

Trees

• Nodes: Elements in the tree.
• Edges: Connections between nodes.
• Root: The topmost node.
• Parent: A node connected to another via an edge above it in the hierarchy.
• Child: A node connected to another via an edge below it in the hierarchy.
• Leaf: A node with no children.

Binary Trees

• Trees where each node has at most 2 children.
• Left child & Right child: Children
• Operations include searching, insertion, deletion, traversal

Binary Search Trees (BSTs)

• Binary trees where nodes satisfy the following properties: 
  • Left subtree contains only nodes with keys smaller than the key of the current node.
  • Right subtree contains only nodes with keys greater than the key of the current node.
• Operations include searching, insertion, and deletion.
• Traversal methods are used to traverse the whole structure.

Expression Trees

• Trees structure that represent arithmetic/logical expressions
• Nodes can be either operators or operands
• Used in evaluating expressions and converting notations

Graph Traversals

• Depth-First Search (DFS): Explores as far as possible along each branch before backtracking. 
• Breadth-First Search (BFS): Explores all neighbors at the current level before moving to the next level.

Sorting Algorithms

• Bubble Sort: Simple comparison-based algorithm. Repeatedly steps through the list, compares adjacent elements and swaps them if they are in the wrong order. (O(n^2))
• Insertion Sort: An in-place comparison-based sorting algorithm. Maintains a sorted sub-list and iteratively inserts new elements into their appropriate position within the sub-list. (O(n^2))
• Selection Sort: In-place comparison-based algorithm that divides the array into a sorted portion and an unsorted portion. Repeatedly selects the minimum element from the unsorted part and swaps it with the element at the beginning of the unsorted part. (O(n^2))

Hashing

• Technique for converting key values to array-like indexes.
• Used for fast access of data in a hash table.
• Hash functions map key values to unique indexes.
• Hash table is a data structure that stores data based.

This quiz provides an overview of various data structures, essential for efficient data handling in computer science. Explore the fundamental concepts of arrays, linked lists, stacks, and queues, and understand their applications in software performance and algorithms.