CS50 Week 5 Notes

Introduction to Data Structures

• Focus on data structures and their applications in problem-solving using C.
• Important terms:
  • Abstraction: High-level descriptions of data structures.
  • Implementation: Low-level details of how data structures are realized in code.

Abstract Data Types (ADTs)

• An abstract data type defines certain properties and characteristics but allows for different implementations.
  • Example: Queue
    • Defined by the FIFO (First In, First Out) principle.
    • Operations: Enqueue (adding to the queue) and Dequeue (removing from the queue).

Queue Demonstration

• Example with volunteers forming a queue to receive cookies.
• Volunteers receive cookies in the order they queued up.

Implementing a Queue in C

• Can be implemented using arrays with the following components:
  • An array to hold elements.
  • Integer to track the size of the queue.

Stack Data Structure

• Defined by the LIFO (Last In, First Out) principle.
  • Operations: Push (adding to the stack) and Pop (removing from the stack).
• Stack demonstration with volunteers, showing that the last person to enter will be the first to leave with cookies.

Practical Considerations for Data Structures

• Limitations of static arrays:
  • Fixed capacity can result in wasted space or overflows.
• Issues with resizing arrays:
  • Requires copying elements when reallocating memory.

Linked Lists

• Introduced to solve fixed size array limitations.
• Consists of nodes that hold data and pointers to other nodes.

Implementing a Linked List

• Each node contains:
  • Data (value).
  • Pointer to the next node.
• Advantages:
  • Dynamic size.
  • Efficient insertion and deletion.

Searching and Inserting in Linked Lists

• Big O notation for inserting:
  • Prepend: O(1) (constant time).
  • Append or insert in sorted order: O(n) (linear time).

Trees and Binary Search Trees (BSTs)

• Trees store hierarchical relationships, with nodes containing data and pointers to child nodes.
• Binary Search Tree:
  • Each node has up to two children.
  • Left child < Parent < Right child (ensures sorted order).

Operations on BSTs

• Searching in BSTs:
  • Average: O(log n) (due to halving the search space).
  • Worst case: O(n) if unbalanced (degenerated into a linked list).

Hash Tables

• Implements dictionaries using hashing techniques.
• Maps keys (e.g., names) to values (e.g., phone numbers).
• Avoids collisions by using arrays of linked lists.
• Ideal hash function aims for O(1) access time but can degrade to O(n) in case of collisions.

Implementing Hash Tables

• Use an array of linked lists to accommodate potential collisions.
• Hash function converts names to indices based on their first letters.

Tries

• A tree-based data structure where each node represents a character.
• Efficient for prefix searches.
• Complex to implement but offers O(k) search times for words (where k is the length).

Conclusion

• Data structures are fundamental to computer science, supporting efficient algorithms for data management and retrieval techniques.
• Balance between time complexity and space complexity is essential.