Linked List vs Array When to Choose Which in DSA C - Compare & Choose

Challenge - 5 Problems

🧠 Conceptual

intermediate

When is a linked list better than an array?

Which scenario best shows when you should choose a linked list over an array?

A When you want to sort elements quickly using index-based algorithms.

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

C When you want to use less memory overall.

D When you frequently insert or delete elements in the middle of the collection.

💡 Hint

Think about which data structure handles insertions and deletions efficiently.

Linked lists allow quick insertions and deletions anywhere because they just change pointers. Arrays require shifting elements, which is slower.

🧠 Conceptual

intermediate

Why might arrays be preferred over linked lists?

Which reason best explains why arrays are often preferred over linked lists?

A Arrays use pointers to connect elements, making traversal slower.

B Arrays can easily grow and shrink without reallocating memory.

C Arrays allow fast access to elements by index, improving speed for lookups.

D Arrays use more memory per element due to storing extra pointers.

💡 Hint

Think about how you access elements in an array versus a linked list.

Arrays store elements contiguously, so accessing by index is very fast. Linked lists require walking through nodes one by one.

❓ Predict Output

advanced

Output after inserting in a linked list

What is the printed state of the linked list after inserting 99 at position 2?

DSA C

struct Node {
    int data;
    struct Node* next;
};

void insertAtPosition(struct Node** head, int data, int pos) {
    struct Node* newNode = malloc(sizeof(struct Node));
    newNode->data = data;
    if (pos == 1) {
        newNode->next = *head;
        *head = newNode;
        return;
    }
    struct Node* temp = *head;
    for (int i = 1; i < pos - 1 && temp != NULL; i++) {
        temp = temp->next;
    }
    if (temp == NULL) return;
    newNode->next = temp->next;
    temp->next = newNode;
}

void printList(struct Node* head) {
    while (head != NULL) {
        printf("%d -> ", head->data);
        head = head->next;
    }
    printf("null\n");
}

int main() {
    struct Node* head = malloc(sizeof(struct Node));
    head->data = 10;
    head->next = malloc(sizeof(struct Node));
    head->next->data = 20;
    head->next->next = malloc(sizeof(struct Node));
    head->next->next->data = 30;
    head->next->next->next = NULL;

    insertAtPosition(&head, 99, 2);
    printList(head);
    return 0;
}

A 10 -> 20 -> 30 -> 99 -> null

B 10 -> 99 -> 20 -> 30 -> null

C 99 -> 10 -> 20 -> 30 -> null

D 10 -> 20 -> 99 -> 30 -> null

💡 Hint

Remember position 2 means after the first element.

Inserting 99 at position 2 places it after the first node (10), so the list becomes 10 -> 99 -> 20 -> 30 -> null.

❓ Predict Output

advanced

Array resizing behavior

What is the content of the array after doubling its size and copying elements?

DSA C

int* resizeArray(int* arr, int oldSize, int newSize) {
    int* newArr = malloc(newSize * sizeof(int));
    for (int i = 0; i < oldSize; i++) {
        newArr[i] = arr[i];
    }
    for (int i = oldSize; i < newSize; i++) {
        newArr[i] = 0;
    }
    free(arr);
    return newArr;
}

int main() {
    int oldSize = 3;
    int* arr = malloc(oldSize * sizeof(int));
    arr[0] = 5;
    arr[1] = 10;
    arr[2] = 15;

    int newSize = 6;
    arr = resizeArray(arr, oldSize, newSize);

    for (int i = 0; i < newSize; i++) {
        printf("%d ", arr[i]);
    }
    free(arr);
    return 0;
}

A 5 10 15 0 0 0

B 5 10 15 15 15 15

C 0 0 0 0 0 0

D 5 10 15 garbage garbage garbage

💡 Hint

New elements after oldSize are set to zero.

The function copies old elements and sets new slots to zero, so the output is 5 10 15 0 0 0.

🧠 Conceptual

expert

Choosing data structure for mixed operations

You need a data structure for a program that requires frequent insertions and deletions anywhere, but also fast access by index sometimes. Which is the best choice?

A Use a balanced tree or a specialized data structure like a skip list to balance both needs.

B Use an array because it provides fast access by index, and insertions/deletions are rare.

C Use a stack because it supports fast insertions and deletions at one end.

D Use a linked list because it handles insertions and deletions efficiently, and access speed is not important.

💡 Hint

Think about a data structure that balances both fast access and efficient insertions/deletions.

Neither arrays nor linked lists alone handle both requirements well. Balanced trees or skip lists provide a good compromise.

Practice

1. Which data structure is better when you need fast random access to elements by index?

easy

A. Array

B. Linked List

C. Stack

D. Queue

Solution

1. Step 1: Understand random access in arrays

   Arrays store elements in contiguous memory, so accessing any element by index is fast and direct.

2. Step 2: Compare with linked list access

   Linked lists require traversal from the head to reach an element, making random access slower.

3. Final Answer:

   Array -> Option A

4. Quick Check:

   Random access = Array [OK]

Hint: For fast index access, choose arrays [OK]

Common Mistakes:

• Thinking linked lists provide fast random access
• Confusing stack or queue with random access
• Ignoring memory layout differences

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

easy

A. int arr{};

B. int arr();

C. int arr[5];

D. int arr = new int[5];

Solution

1. Step 1: Recall C array declaration syntax

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

2. Step 2: Check other options for errors

   int arr(); uses parentheses which is a function declaration, C uses braces which is invalid, D uses 'new' which is C++ syntax.

3. Final Answer:

   int arr[5]; -> Option C

4. Quick Check:

   C array declaration = int arr[5]; [OK]

Hint: Use square brackets for arrays in C [OK]

Common Mistakes:

• Using parentheses instead of brackets
• Using C++ 'new' keyword in C
• Using braces for array declaration

3. Consider the following C code snippet:

typedef struct Node {
  int data;
  struct Node* next;
} Node;

Node* head = NULL;

// Insert 3 nodes at the beginning
for (int i = 1; i <= 3; i++) {
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = i;
  newNode->next = head;
  head = newNode;
}

// Print list
Node* temp = head;
while (temp != NULL) {
  printf("%d -> ", temp->data);
  temp = temp->next;
}
printf("NULL\n");

What is the printed output?

medium

A. 1 -> 2 -> 3 -> NULL

B. 3 -> 2 -> 1 -> NULL

C. NULL

D. 3 -> 1 -> 2 -> NULL

Solution

1. Step 1: Understand insertion at beginning in linked list

   Each new node is added at the head, so the last inserted node becomes the first in the list.

2. Step 2: Trace the loop values and list order

   Insert 1: list is 1 -> NULL Insert 2: list is 2 -> 1 -> NULL Insert 3: list is 3 -> 2 -> 1 -> NULL

3. Final Answer:

   3 -> 2 -> 1 -> NULL -> Option B

4. Quick Check:

   Insertion at head reverses order [OK]

Hint: Insertion at head reverses order [OK]

Common Mistakes:

• Assuming insertion appends at end
• Confusing order of nodes after insertion
• Ignoring pointer updates

4. The following code tries to insert a node at the end of a singly linked list but causes a runtime error. What is the error?

void insertEnd(Node** head, int val) {
  Node* newNode = (Node*)malloc(sizeof(Node));
  newNode->data = val;
  newNode->next = NULL;

  Node* temp = *head;
  while (temp->next != NULL) {
    temp = temp->next;
  }
  temp->next = newNode;
}

medium

A. Dereferencing NULL pointer when list is empty

B. Memory leak due to missing free()

C. Incorrect data assignment to newNode

D. Missing return statement in void function

Solution

1. Step 1: Analyze behavior when list is empty

   If *head is NULL, then temp = NULL. Accessing temp->next causes a runtime error (segmentation fault).

2. Step 2: Identify fix for empty list case

   Need to check if *head is NULL before loop and assign newNode as head if true.

3. Final Answer:

   Dereferencing NULL pointer when list is empty -> Option A

4. Quick Check:

   Empty list causes NULL pointer error [OK]

Hint: Check for empty list before traversal [OK]

Common Mistakes:

• Ignoring empty list case
• Confusing memory leak with pointer error
• Thinking missing return causes runtime error

5. You need to store a large number of elements where insertions and deletions happen frequently at random positions. Which data structure is more suitable and why? A) Array because it uses less memory B) Linked List because it allows efficient insertions and deletions C) Array because it provides faster random access D) Linked List because it uses contiguous memory

hard

A. Array because it uses less memory

B. Linked List because it uses contiguous memory

C. Array because it provides faster random access

D. Linked List because it allows efficient insertions and deletions

Solution

1. Step 1: Understand insertion and deletion costs

   Arrays require shifting elements for insertions/deletions at random positions, which is costly.

2. Step 2: Compare with linked list behavior

   Linked lists allow insertions and deletions by changing pointers without shifting elements, making them efficient for frequent changes.

3. Final Answer:

   Linked List because it allows efficient insertions and deletions -> Option D

4. Quick Check:

   Frequent insert/delete = Linked List [OK]

Hint: Frequent insert/delete? Choose linked list [OK]

Common Mistakes:

• Choosing array for frequent insertions
• Thinking linked list uses contiguous memory
• Ignoring cost of shifting in arrays