Why do we use arrays instead of other data structures?

When we start learning C and C++ programming. Surely you've heard of data structures. So the following problem arises: "Why do we use arrays instead of other data structures?".

Currently, there are many different types of structures to store data such as: Linked List, Stack, Queue, Binary Tree, etc. These data structures gradually replace arrays in C/C++.

So, basically, what's the point of using arrays?

This is not so much why do we use arrays from a computer standpoint, but rather why would we use arrays from a programming standpoint (a subtle difference). What the computer does with the array was not the point of the question.

Why do we use arrays instead of other data structures?

Time to go back in time for a lesson. While we don't think about these things much in our fancy managed languages today, they are built on the same foundation, so let's look at how memory is managed in C / C++.

Before we dive in, a quick explanation of what the term "pointer" means. A pointer is simply a variable that "points" to a location in memory. It doesn't contain the actual value at this area of memory, it contains the memory address to it. Think of a block of memory as a mailbox. The pointer would be the address to that mailbox.

In C / C++, an array is simply a pointer with an offset, the offset specifies how far in memory to look.

faq 01 PNG

All other data structures either build upon this, or do not use adjacent memory for storage, resulting in poor random access look up time (Though there are other benefits to not using sequential memory).

For example: Let's say we have an array with 6 numbers {6, 4, 2, 3, 1, 5} in it, in memory it would look like this:

faq 02 PNG

In an array, we know that each element is next to each other in memory. C / C++ array (called MyArray here) is simply a pointer to the first element:

faq 03 PNG

If we wanted to look up MyArray[4], internally it would be accessed like this:

faq 04 PNG

Because we can directly access any element in the array by adding the offset to the pointer, we can look up any element in the same amount of time, regardless of the size of the array. This means that getting MyArray[1000] would take the same amount of time as getting MyArray[5].

An alternative data structure is a linked list. This is a linear list of pointers, each pointing to the next node.

faq 05 PNG

Note that we made each "node" into its own block. This is because they are not guaranteed to be (and most likely won't be) adjacent in memory.

If we want to access P3, we can't directly access it, because we don't know where it is in memory. All we know is where the root (P1) is, so instead we have to start at P1, and follow each pointer to the desired node.

Higher level data structures, such as hashtables, stacks and queues, all may use an array (or multiple arrays) internally, while Linked Lists and Binary Trees usually use nodes and pointers.

You might wonder why anyone would use a data structure that requires linear traversal to look up a value instead of just using an array, but they have their uses.

Take our array again. This time, I want to find the array element that holds the value '5'.

faq 06 PNG

In this situation, we don't know what offset to add to the pointer to find it, so we have to start at 0, and work our way up until we find it. This means we have to perform 6 checks.

Remember up above where we said that sometimes using a non sequential data structure can have advantages? Searching for data is one of these advantages and one of the best examples is the Binary Tree.

A Binary Tree is a data structure similar to a linked list, however instead of linking to a single node, each node can link to two children nodes.

faq 07 PNG

This is an incredibly high level overview on data structures in memory, skipping over a lot of details, but hopefully it illustrates an array's strength and weakness compared to other data structures.

In short, in some cases, we need to use arrays to store data. Accessing random elements helps us access any element much faster than other data structures. Some data structures such as Stack, Queue all use arrays for implementation.

Source link

Cùng chuyên mục:

What happens if no break statement in

What happens if no break statement in

Which is better while or do while loop?

Which is better while or do while loop?

How to stop while loop in C / C++?

How to stop while loop in C / C++?

Why for loop in C / C++ not stopping?

Why for loop in C / C++ not stopping?