Arrays vs Other Data Structures When to Choose Arrays in DSA C - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

When is an array the best choice over a linked list?

Choose the scenario where using an array is better than using a linked list.

A When you need to frequently insert or delete elements in the middle.

B When the size of the data changes frequently and unpredictably.

C When memory usage must be minimal and flexible.

D When you need fast random access to elements by index.

💡 Hint

Think about how arrays store elements contiguously and how that affects access speed.

Arrays store elements in continuous memory locations, allowing fast access by index. Linked lists require traversal to access elements, making arrays better for random access.

❓ Predict Output

intermediate

Output of array vs linked list access time simulation

What is the output of the following C code simulating access times for array and linked list?

DSA C

int main() {
    int arr[5] = {10, 20, 30, 40, 50};
    struct Node {
        int val;
        struct Node* next;
    };
    struct Node n1 = {10, NULL}, n2 = {20, NULL}, n3 = {30, NULL}, n4 = {40, NULL}, n5 = {50, NULL};
    n1.next = &n2; n2.next = &n3; n3.next = &n4; n4.next = &n5;

    // Access 3rd element in array
    int arr_val = arr[2];

    // Access 3rd element in linked list
    struct Node* temp = &n1;
    for(int i = 0; i < 2; i++) {
        temp = temp->next;
    }
    int list_val = temp->val;

    printf("Array value: %d\nLinked list value: %d\n", arr_val, list_val);
    return 0;
}

A

Array value: 20
Linked list value: 30

B

Array value: 30
Linked list value: 30

C

Array value: 30
Linked list value: 20

D

Array value: 40
Linked list value: 40

💡 Hint

Remember array indexing starts at 0 and linked list traversal moves node by node.

Accessing the 3rd element (index 2) in the array gives 30. Traversing two nodes from the head in the linked list also reaches the node with value 30.

🔧 Debug

advanced

Why does this array resizing code cause errors?

Consider this C code snippet that tries to resize an array using malloc and memcpy. Identify the error causing a runtime crash.

DSA C

int* resize_array(int* arr, int old_size, int new_size) {
    int* new_arr = malloc(new_size * sizeof(int));
    memcpy(new_arr, arr, new_size * sizeof(int));
    free(arr);
    return new_arr;
}

A free is called before memcpy causing memory corruption.

B malloc is not called correctly and returns NULL.

C memcpy copies more bytes than the original array size, causing undefined behavior.

D The function returns a pointer to freed memory.

💡 Hint

Check the number of bytes copied compared to the original array size.

memcpy copies new_size elements, but the original array only has old_size elements. Copying beyond old_size causes undefined behavior and possible crash.

🚀 Application

advanced

Choosing data structure for frequent insertions and random access

You need to store a collection of items where you must insert new items frequently at random positions and also access items by index quickly. Which data structure is best?

A Balanced binary search tree

B Dynamic array (resizable array)

C Doubly linked list

D Singly linked list

💡 Hint

Think about which structure supports both fast insertion and fast indexed access.

Dynamic arrays have fast indexed access but slow insertions in the middle. Linked lists have fast insertions but slow indexed access. Balanced binary search trees can provide balanced performance for both operations.

🧠 Conceptual

expert

Why are arrays preferred for CPU cache performance?

Explain why arrays often provide better CPU cache performance compared to linked lists.

A Arrays store elements contiguously in memory, improving spatial locality and cache hits.

B Arrays use pointers which help CPU prefetch data better than linked lists.

C Arrays have smaller memory overhead per element than linked lists, so CPU caches more elements.

D Arrays allocate memory dynamically which reduces cache misses.

💡 Hint

Consider how memory layout affects CPU cache behavior.

Arrays store elements next to each other in memory, so when CPU loads one element, nearby elements are also loaded into cache, improving access speed. Linked lists store elements scattered in memory, causing more cache misses.

Practice

1. Which of the following is the best reason to choose an array over other data structures like linked lists or trees?

easy

A. When you need fast access to elements by index

B. When you want to easily insert or delete elements anywhere

C. When you need a flexible size that changes often

D. When you want to store key-value pairs

Solution

1. Step 1: Understand array access

   Arrays store elements in contiguous memory, so accessing by index is very fast (constant time).

2. Step 2: Compare with other structures

   Linked lists and trees have slower access by index because they require traversal. Arrays are best for fast index access.

3. Final Answer:

   When you need fast access to elements by index -> Option A

4. Quick Check:

   Fast index access = B [OK]

Hint: Arrays give fast index access, unlike linked lists [OK]

Common Mistakes:

• Thinking arrays are best for frequent insertions/deletions
• Confusing arrays with key-value stores
• Assuming arrays resize automatically

2. Which of the following is the correct way to declare an integer array of size 5 in C?

easy

A. int arr = new int[5];

B. int arr[5];

C. int arr();

D. array<int> arr(5);

Solution

1. Step 1: Recall C array syntax

   In C, arrays are declared with the type, name, and size in square brackets, like int arr[5];.

2. Step 2: Check other options

   int arr(); uses parentheses which is a function declaration. int arr = new int[5]; is C++ style with new. array<int> arr(5); is not valid C syntax.

3. Final Answer:

   int arr[5]; -> Option B

4. Quick Check:

   C arrays use square brackets for size = C [OK]

Hint: C arrays use square brackets for size declaration [OK]

Common Mistakes:

• Using parentheses instead of square brackets
• Using C++ style new keyword in C
• Confusing array declaration with function declaration

3. What will be the output of the following C code?

int arr[3] = {10, 20, 30};
printf("%d", arr[1]);

medium

A. 10

B. Compilation error

C. 20

D. 30

Solution

1. Step 1: Understand array initialization

   The array arr has elements 10 at index 0, 20 at index 1, and 30 at index 2.

2. Step 2: Identify printed element

   The code prints arr[1], which is the second element, value 20.

3. Final Answer:

   20 -> Option C

4. Quick Check:

   arr[1] = 20 [OK]

Hint: Array indexing starts at 0, so arr[1] is second element [OK]

Common Mistakes:

• Confusing index 1 with first element
• Expecting compilation error due to syntax
• Mixing up array initialization order

4. Identify the error in the following C code snippet that uses an array:

int arr[3];
arr[3] = 100;
printf("%d", arr[3]);

medium

A. Array index out of bounds error

B. Syntax error in array declaration

C. Missing semicolon after declaration

D. No error, code runs fine

Solution

1. Step 1: Check array size and indexing

   The array arr has size 3, so valid indices are 0, 1, and 2.

2. Step 2: Analyze the assignment and print

   The code assigns and prints arr[3], which is outside the valid range, causing out of bounds access.

3. Final Answer:

   Array index out of bounds error -> Option A

4. Quick Check:

   Index 3 invalid for size 3 array = A [OK]

Hint: Array indices go from 0 to size-1 only [OK]

Common Mistakes:

• Assuming index 3 is valid for size 3 array
• Thinking syntax error due to semicolon
• Believing code runs without error

5. You need to store a fixed number of sensor readings that will not change in size and require fast access by position. Which data structure is the best choice and why?

hard

A. Binary tree, because it keeps data sorted automatically

B. Linked list, because it allows easy insertion and deletion

C. Hash table, because it stores key-value pairs efficiently

D. Array, because it provides fast indexed access and fixed size

Solution

1. Step 1: Analyze requirements

   The sensor readings count is fixed and will not change, and fast access by position is needed.

2. Step 2: Match data structure features

   Arrays have fixed size and allow fast access by index. Linked lists are slower for access. Hash tables and trees serve different purposes.

3. Final Answer:

   Array, because it provides fast indexed access and fixed size -> Option D

4. Quick Check:

   Fixed size + fast access = Array = A [OK]

Hint: Fixed size and fast access? Choose array [OK]

Common Mistakes:

• Choosing linked list for fixed size data
• Confusing hash table use case
• Thinking binary tree is best for fixed size arrays