Choosing the right data structure in Intro to Computing - Draw & Build Visually

Draw This - beginner

Draw a flowchart to help decide which data structure to use for storing a collection of items based on these questions: 1. Do you need to keep the items in order? 2. Do you need to access items by position quickly? 3. Do you need to add or remove items often? 4. Do you need to find items by a key or name? Use the answers to guide to one of these data structures: Array, Linked List, Hash Table, or Tree.

10 minutes

Hint 1

Hint 2

Hint 3

Hint 4

Grading Criteria

Start and End symbols present

Decision diamonds used for yes/no questions

Flow follows logical order of questions

Each decision leads to a correct data structure

Data structures named correctly in terminal boxes

Solution

  +-----------------------------+
  |          Start              |
  +-----------------------------+
                |
                v
  +-----------------------------+
  | Need to keep items in order?|
  +-----------------------------+
              Yes      No
               |        |
               v        v
  +-----------------------+  +-----------------------------+
  | Need fast access by   |  | Need to find items by key?  |
  | position?             |  +-----------------------------+
  +-----------------------+           Yes     No
              Yes      No                 |       |
               |        |                 v       v
               v        v        +---------------+  +----------+
         +----------+  +----------+  | Hash Table  |  | Tree    |
         +----------+  +----------+  +---------------+  +----------+
         |  Array   |  |Linked List|

This flowchart helps decide the best data structure based on your needs.

1. Start by asking if you need to keep items in order. If yes, go to step 2; if no, go to step 4.
2. If you need order, ask if you need fast access by position. If yes, use an Array because it stores items in order and allows quick access by index.
3. If you don't need fast access by position but still want order and frequent adding/removing, a Linked List is better.
4. If you don't need order, ask if you need to find items by a key or name. If yes, use a Hash Table for fast key-based lookup.
5. If no key-based lookup is needed but you want sorted data and fast search, use a Tree.

This step-by-step decision helps pick the right data structure for your problem.

Variations - 2 Challenges

[intermediate] Draw a flowchart to choose between Array, Linked List, Stack, and Queue based on whether you need order, fast access, or last-in-first-out behavior.

[advanced] Draw a detailed flowchart to select the best data structure among Array, Linked List, Hash Table, Tree, Stack, and Queue considering order, access speed, insertion/deletion frequency, and search by key.

Practice

1. Which data structure should you use if you want to store a list of items where order matters and duplicates are allowed?

easy

A. List or array

B. Set

C. Dictionary

D. Tuple

Solution

1. Step 1: Understand the need for order and duplicates

   Lists and arrays keep the order of items and allow duplicates, which matches the requirement.

2. Step 2: Compare with other structures

   Sets do not allow duplicates, dictionaries store key-value pairs, and tuples are immutable but also keep order.

3. Final Answer:

   List or array -> Option A

4. Quick Check:

   Order + duplicates = List/array [OK]

Hint: Use lists for ordered data with duplicates [OK]

Common Mistakes:

• Choosing set which removes duplicates
• Choosing dictionary which stores key-value pairs
• Confusing tuple immutability with order

2. Which of the following is the correct way to create an empty set in Python?

easy

A. empty_set = {}

B. empty_set = set()

C. empty_set = []

D. empty_set = ()

Solution

1. Step 1: Recall syntax for empty set

   In Python, {} creates an empty dictionary, not a set.

2. Step 2: Identify correct set creation

   Using set() creates an empty set correctly.

3. Final Answer:

   empty_set = set() -> Option B

4. Quick Check:

   Empty set = set() [OK]

Hint: Use set() to create empty sets, {} is a dict [OK]

Common Mistakes:

• Using {} which creates an empty dictionary
• Using [] which creates a list
• Using () which creates a tuple

3. What will be the output of this Python code?

data = {'apple': 3, 'banana': 5, 'orange': 2}
print(data['banana'])

medium

A. 5

B. 3

C. 'banana'

D. KeyError

Solution

1. Step 1: Understand dictionary key-value access

   In the dictionary, 'banana' is a key with value 5.

2. Step 2: Access the value for 'banana'

   Using data['banana'] returns the value 5.

3. Final Answer:

   5 -> Option A

4. Quick Check:

   Dictionary key 'banana' = 5 [OK]

Hint: Dictionary[key] returns the value for that key [OK]

Common Mistakes:

• Confusing key with value
• Expecting the key name as output
• Mistyping key causing KeyError

4. You want to store unique user IDs and quickly check if a user ID exists. Which data structure is best? The code below has an error. Find and fix it.

user_ids = []
user_ids.add(101)
user_ids.add(102)

medium

A. Use dictionary instead of list

B. Use append instead of add: user_ids.append(101)

C. Change list to set: user_ids = set()

D. No error, code is correct

Solution

1. Step 1: Identify the error in method usage

   Lists do not have an add() method; add() is for sets.

2. Step 2: Choose correct data structure for unique items

   Sets store unique items and support add() method, so change list to set.

3. Final Answer:

   Change list to set: user_ids = set() -> Option C

4. Quick Check:

   Unique items + add() = set [OK]

Hint: Use set() for unique items and add() method [OK]

Common Mistakes:

• Using add() on list causing AttributeError
• Using append() but duplicates allowed
• Choosing dictionary unnecessarily

5. You have a list of student names with possible duplicates. You want to count how many times each name appears. Which data structure is best and why?

hard

A. Use a tuple to store names immutably

B. Use a set to store unique names only

C. Use a list to store all names again

D. Use a dictionary to map names to counts

Solution

1. Step 1: Understand the need to count occurrences

   Counting requires storing each name with its count, which is a key-value pair.

2. Step 2: Choose data structure for key-value pairs

   Dictionaries store keys (names) with values (counts), perfect for this task.

3. Final Answer:

   Use a dictionary to map names to counts -> Option D

4. Quick Check:

   Counting items = dictionary [OK]

Hint: Use dictionary for counting items with keys and values [OK]

Common Mistakes:

• Using set which removes duplicates and loses counts
• Using list which doesn't map names to counts
• Using tuple which is immutable and not for counting