Lecture on Data Structures

Introduction to Data Structures

• Definition: A data structure is a way of organizing data to be used efficiently.

• Importance:

  • Essential for creating fast algorithms.
  • Helps manage and organize data naturally.
  • Makes code cleaner and easier to understand.

  Abstraction of Data Structures

  • Abstract Data Types (ADT): An abstraction of a data structure that provides only the interface without details on implementation.
  • Example: Modes of transportation as an ADT for a journey from point A to B.
  • Implementations:
    • Lists: Dynamic arrays, Linked lists
    • Queues, Maps: Various implementations including stack-based queues

Computational Complexity

• Big O Notation: Standard way to describe time and space complexity.
  • Focuses on worst-case scenarios.
• Questions:
  • Time: How long to complete?
  • Space: How much space required?
• Common Time Complexities:
  • Constant: O(1)
  • Logarithmic: O(log n)
  • Linear: O(n)
  • Quadratic/Cubic/etc.: O(n^2), O(n^3)
  • Exponential: O(2^n), O(n!)
• Ignore Constants & Multiplicative Factors: Focus on dominant terms when n becomes large.
• Properties of Big O:
  • Ignore constants in theoretical analysis.
  • Long expression reduces to most dominant term.
  • Examples: Constant time is O(1), Linear time is O(n).

Arrays as Data Structures

• Static Arrays:
  • Fixed length container with elements indexed from 0 to n-1.
  • Indexable: Each slot can be referenced by a number.
  • Contiguous Memory: Memory addresses adjacent to each other.
• Dynamic Arrays:
  • Can grow and shrink in size as needed.
  • Operations and complexity similar to static arrays with additional resizing considerations.
• Common Uses:
  • Temporarily store objects.
  • Buffers for input/output streams.
  • Lookup tables using indexing properties.
  • Dynamic programming for tabulation.

Linked Lists

• Definition: Sequential list of nodes holding data pointing to other nodes containing data.
• Types:
  • Singly Linked List: Each node points to the next node.
  • Doubly Linked List: Each node points to both next and previous nodes.
• Use Cases: Lists, stacks, queues, modeling real-world objects (train carts, polygons).

Stacks

• Definition: One-ended linear data structure (LIFO: last in, first out).
• Operations:
  • Push: Adding an element.
  • Pop: Removing the top element.
  • Peek: Viewing the top element without removing it.
• Use Cases: Text editors, compilers for matching braces, recursion support, etc.

Queues

• Definition: Linear data structure (FIFO: first in, first out).
• Operations: Enqueue, dequeue, check if empty, peek at the front.
• Use Cases: Real-world queues (e.g., movie theaters), server management, BFS in graphs.

Priority Queues & Heaps

• Priority Queue: Data structure where each element has priority; elements with higher priority served first.
• Heap: Tree-based data structure satisfying the heap property (parent node ordered with respect to children).
• Types: Min-heaps and max-heaps.
• Implementations: Binary heap, Fibonacci heap, etc.
• Usefulness: In algorithms like Dijkstra's shortest path, Huffman encoding, graph traversals (BFS, DFS, minimum spanning tree).

Fenwick Tree (Binary Indexed Tree)

• Definition: Data structure that supports point updates and range queries in logarithmic time.
• Construction: Linear time construction using prefix sums and propagation techniques.

Suffix Arrays

• Definition: Array of indices storing sorted suffixes of a string.
• Use Cases: String processing, finding unique substrings, repeated substrings, longest common prefixes.

AVL Trees

• Definition: Self-balancing binary search tree with a balance factor ( -1, 0, 1).
• Operations: Insertion, deletion, tree rotations to maintain balance, complexity O(log n).

Index Priority Queues

• Definition: Priority Queue which supports quick updates and deletions of key-value pairs.
• Operations: Key insertions, deletions, updates efficiently managed using heaps.

Conclusion

• Importance of Data Structures: Critical for efficient algorithm design, clean code, managing data naturally.
• Variety of Structures: Static/Dynamic Arrays, Linked Lists, Stacks, Queues, Heaps, Trees (AVL, Fenwick), Suffix Arrays, and Index Priority Queues.
• Focus on Efficiency: Using the right data structure can drastically improve performance and readability of your code.