Solve problems that are commonly asked in C++ coding interviews related to common data structures.

Ace the C++ Coding Interview

Data structures are among the fundamentals of computer science and are often a core decision in developing efficient programs. They are categorized as a vital benchmark of computer science knowledge when it comes to industry interviews. This module contains a detailed review of common data structures in C++. We'll also become well-equipped with different data structures by implementing them.
By the end of this module, we'll have expertise in solving problems in data structures.

Data Structures

The main difference between *arrays* and *linked lists* is memory allocation. An *array* instantiates a fixed block of memory based on the size we define in its declaration.

On the other hand, *linked lists* can access or release memory based on the addition and deletion elements. Its size is not fixed.

Other differences can be observed in the way elements are inserted and deleted. As for *linked list*, insertion, and deletion at head happens in a constant amount of time while in case of *arrays* it takes *O(n)* time to insert or delete a value because you have to shift the array elements left or right after that operation. But in case of searching an element, for an array it takes constant time to access an index while in case of a linked list you will have to iterate the list from start till you find the node with the correct value.

Apart from memory allocation, there are some differences in performance between linked lists and arrays. Let's take a look at them now:

| **Operation**  | **Linked List** | **Array** |
| -----  | ------| ---- |
| <center>Access | <center>O(n)| <center>O(1) |
| <center>Insert (at head) | <center>O(1) | <center>O(n) |
| <center>Delete (at head) | <center>O(1) | <center>O(n) |
|Insert (at tail)|O(n)|O(n)|
|Delete (at tail)|O(n)|O(n)|

In a *linked list*, insertion and deletion happen in a constant amount of time. You can simply add or delete a Node between two Nodes. 

In an array, the two operations would take O(n) time since addition or deletion would mean shifting the whole array left or right.

The access operation in *arrays* is much faster as you can simply use the index of an array to access the value you need. In *linked lists*, there is no concept of indexing. To reach a certain element in the list, we must traverse it from the beginning.

As you can see, there is a trade-off between the facilities provided by both structures. You will understand more about the working of *linked lists* in the lessons that follow.

___




Let's put the two data structures against each other to find out which is more efficient.

Linked Lists vs. Arrays