Exit Ticket: Day 26 - Data Structures

day26-exit-ticket.md

Exit Ticket: Day 26 - Data Structures

Choose whether a given object is a Data Structure (DS) or an Abstract Data Type (ADT):

	DS	ADT	Can be implemented using...	Features include...
Contiguous Array	✔️		n/a	Uninterrupted space in memory (RAM)
Stack		✔️	arrays, linked lists	Linear, LIFO, top reference, push, pop, peek, isEmpty, size
Queue		✔️	arrays, linked lists	Linear, FIFO, head/front and tail/back references, enqueue/add/enter, dequeue/remove/leave, peek, isEmpty, size
List		✔️	arrays, linked lists	Linear, "flexible" arrays, get/find, insert/add, remove/delete, isEmpty, size
Tree		✔️	arrays, linked trees	Non-linear, level, depth, height, root, leaf, parent, left-child, right-child, subtree, traversals (see final two exit ticket question below)
Linked List	✔️		n/a	Placed wherever there is space in memory (RAM) and connected by references

• Data Structure (DS)
  • actual implementation of how information is stored in memory
  • a concrete implementation of a data type
  • it’s possible to analyze the time and memory complexity of a Data Structure but not from a data type
  • the Data Structure can be implemented in several ways and its implementation may vary from language to language
  • (📖 ) GeeksforGeeks: Key Differences Between Array and Linked List
    • The reference above is super useful in building a foundation before going into ADTs
• Abstract Data Type (ADT)
  • a blueprint of expected operations and how information is related
  • a way of classifying data structures based on how they are used and the behaviors they provide
  • they do not specify how the data structure must be implemented but simply provide a minimal expected interface and set of behaviors
  • (📖 ) GeeksforGeeks: Abstract Data Types
    • Covers lists, stacks and queues
• References:
  • (📖 ) Cornell: Abstract Data Types and Data Structures
  • (📖 ) Cornell: Abstract Data Types; Lists & Trees
  • (📖 ) Univ of Wisconsin: Lists
  • (📖 ) Medium: #SideNotes — Stack — Abstract Data Type and Data Structure

Match the method with the appropriate ADT

	Stack	Queue
Enqueue		✔️
Dequeue		✔️
Push	✔️
Pop	✔️

Choose which type of tree traversal is better for the given task.

	Breadth-First Search (BFS)	Depth-First Search (DFS)
Traverses a tree level by level	✔️
Traverses a tree branch by branch		✔️
Good for copying a BST		✔️ (Specifically, pre-order)
Extra: Implemented using...	Queue ADT	Stack ADT / Recursive call stack

• Reference:
  • (📺 ) Back to Back SWE: Depth First & Breadth First Graph Search

Match each use case with the appropriate depth first traversal methods.

	Pre-order (root, left, right)	Post-order (left, right, root)	In-order (left, root, right)
Produce a sorted list of items from a BST			✔️
Remove all tree nodes from memory		✔️
Clone a binary search tree	✔️