Linked List vs Array When to Choose Which in DSA C++ - Build Both Approaches

Linked List vs Array: When to Choose Which

📖 Scenario: Imagine you are organizing a music playlist app. You want to store songs so users can add, remove, or browse songs easily. You need to decide whether to use an array or a linked list to store the songs.

🎯 Goal: You will create a simple list of songs using an array and a linked list. Then, you will add a new song and remove a song from each structure. This will help you see when arrays or linked lists are better choices.

📋 What You'll Learn

Create an array of 3 songs with exact titles

Create a linked list of 3 songs with exact titles

Add a new song to the array and linked list

Remove the second song from the array and linked list

Print the final state of both data structures

💡 Why This Matters

🌍 Real World

Music apps, contact lists, and many programs store data in arrays or linked lists depending on how users add or remove items.

💼 Career

Understanding when to use arrays or linked lists is key for software developers to write efficient and maintainable code.

1

Create an array of songs

Create a C++ array called songsArray with these exact 3 song titles: "SongA", "SongB", "SongC".

DSA C++

// Create the array songsArray with 3 songs
// Your code here

Hint

Use string songsArray[3] = {"SongA", "SongB", "SongC"}; to create the array.

2

Create a linked list of songs

Add a linked list node struct called Node with a string called song and a Node* called next. Then create 3 nodes with songs "SongA", "SongB", and "SongC" linked in order, and a pointer head to the first node.

DSA C++

#include 
#include 

using namespace std;

// Define Node struct here
// Your code here

int main() {
    string songsArray[3] = {"SongA", "SongB", "SongC"};

    // Create linked list nodes and link them
    // Your code here

    return 0;
}

Hint

Define struct Node with string song and Node* next. Create nodes with new Node{"SongA", nullptr} and link them with next.

3

Add and remove songs in array and linked list

Add a new song "SongD" to the end of songsArray by creating a new array newSongsArray of size 4 and copying old songs plus "SongD". Then remove the second song from newSongsArray by creating finalSongsArray of size 3 without the second song. For the linked list, add a new node with "SongD" at the end, then remove the second node from the list.

DSA C++

#include 
#include 

using namespace std;

struct Node {
    string song;
    Node* next;
};

int main() {
    string songsArray[3] = {"SongA", "SongB", "SongC"};

    Node* head = new Node{"SongA", nullptr};
    Node* second = new Node{"SongB", nullptr};
    Node* third = new Node{"SongC", nullptr};

    head->next = second;
    second->next = third;

    // Add "SongD" to songsArray by creating newSongsArray
    // Remove second song from newSongsArray to create finalSongsArray
    // Add "SongD" node at end of linked list
    // Remove second node from linked list
    // Your code here

    return 0;
}

Hint

Use loops to copy arrays. Create new nodes with new Node{"SongD", nullptr}. To remove a node, change next pointers and delete the node.

4

Print final songs in array and linked list

Print the songs in finalSongsArray separated by spaces on one line. Then print the songs in the linked list starting from head, separated by spaces on one line.

DSA C++

#include 
#include 

using namespace std;

struct Node {
    string song;
    Node* next;
};

int main() {
    string songsArray[3] = {"SongA", "SongB", "SongC"};

    Node* head = new Node{"SongA", nullptr};
    Node* second = new Node{"SongB", nullptr};
    Node* third = new Node{"SongC", nullptr};

    head->next = second;
    second->next = third;

    string newSongsArray[4];
    for (int i = 0; i next = newNode;

    head->next = second->next;
    delete second;

    // Print finalSongsArray
    // Print linked list songs
    // Your code here

    return 0;
}

Hint

Use a for loop to print the array songs separated by spaces. Use a while loop to traverse the linked list and print each song.

Practice

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

easy

A. Queue

B. Array

C. Stack

D. Linked List

Solution

1. Step 1: Understand random access requirement

   Random access means accessing any element directly by its position quickly.

2. Step 2: Compare array and linked list access times

   Arrays allow direct access by index in constant time, while linked lists require traversal.

3. Final Answer:

   Array -> Option B

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 traversal cost in linked lists

2. Which of the following is the correct way to declare a dynamic array in C++?

easy

A. int arr[] = new int(10);

B. int arr[10];

C. int arr = new int[10];

D. int* arr = new int[10];

Solution

1. Step 1: Identify dynamic array syntax in C++

   Dynamic arrays use pointers with 'new' keyword and size in brackets.

2. Step 2: Check each option

   int* arr = new int[10]; correctly uses 'int* arr = new int[10];'. Others are either static arrays or incorrect syntax.

3. Final Answer:

   int* arr = new int[10]; -> Option D

4. Quick Check:

   Dynamic array = new int[size] [OK]

Hint: Use 'new' with pointer for dynamic arrays in C++ [OK]

Common Mistakes:

• Using static array syntax for dynamic arrays
• Missing pointer (*) in declaration
• Incorrect use of parentheses instead of brackets

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

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

Node* head = new Node{1, nullptr};
head->next = new Node{2, nullptr};
head->next->next = new Node{3, nullptr};

Node* temp = head;
while(temp != nullptr) {
  std::cout << temp->data << " ";
  temp = temp->next;
}

medium

A. 1 2 3

B. 3 2 1

C. 1 3 2

D. Compilation error

Solution

1. Step 1: Understand linked list creation

   Nodes are created with values 1, 2, 3 linked in order: head -> 1 -> 2 -> 3 -> nullptr.

2. Step 2: Trace the while loop output

   Loop prints data of each node from head to end: 1, then 2, then 3, each followed by space.

3. Final Answer:

   1 2 3 -> Option A

4. Quick Check:

   Traverse linked list prints 1 2 3 [OK]

Hint: Traverse linked list from head to print data [OK]

Common Mistakes:

• Confusing order of nodes
• Forgetting to update temp pointer
• Assuming array-like indexing

4. Identify the error in the following code that tries to insert a new node at the beginning of a linked list:

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

void insertAtHead(Node* head, int val) {
  Node* newNode = new Node{val, nullptr};
  newNode->next = head;
  head = newNode;
}

medium

A. head pointer is passed by value, so original list is not updated

B. Missing return type in function

C. newNode->next should be nullptr

D. Memory leak due to not deleting old head

Solution

1. Step 1: Analyze function parameter passing

   head is passed by value, so changes inside function do not affect original head pointer.

2. Step 2: Understand effect on linked list

   Assigning head = newNode only changes local copy; original list head remains unchanged.

3. Final Answer:

   head pointer is passed by value, so original list is not updated -> Option A

4. Quick Check:

   Pass pointer by reference to update list head [OK]

Hint: Pass head by reference to modify original list [OK]

Common Mistakes:

• Assuming pointer changes affect caller without reference
• Incorrect next pointer assignment
• Ignoring memory management

5. You need to store a large collection of elements where insertions and deletions happen frequently at random positions. Which data structure is more suitable and why?

hard

A. Array, because it provides fast random access

B. Array, because it uses less memory than linked list

C. Linked List, because it allows efficient insertions and deletions without shifting elements

D. Linked List, because it supports binary search efficiently

Solution

1. Step 1: Understand operation requirements

   Frequent insertions and deletions at random positions require efficient element rearrangement.

2. Step 2: Compare array and linked list for these operations

   Arrays require shifting elements on insert/delete, which is costly. Linked lists adjust pointers, making these operations efficient.

3. Final Answer:

   Linked List, because it allows efficient insertions and deletions without shifting elements -> Option C

4. Quick Check:

   Frequent insert/delete = Linked List [OK]

Hint: Use linked list for frequent insertions/deletions [OK]

Common Mistakes:

• Choosing array for frequent insert/delete ignoring shift cost
• Thinking linked list supports fast random access
• Confusing binary search applicability