What is actually the array?

14

Initially, it seems like a silly question. But my goal here is to come up with a more concrete concept about array .

In languages such as JavaScript, array is an object that allows you to add and remove members to a sort of list. This list always has the numbered indexes starting from 0.

In Python, we have something similar to the array of JavaScript, which would be the list and the tuple , except the latter which is a unchanging list but similar.

However, in PHP, array seems to be a mixture of hash (or like Object in JavaScript) with a list.

As my first programming language was PHP, I got used to Array being what it is in PHP, but when comparing it with the array of Java, JavaScript and other languages, I see that even though they have the same nomenclature, they seem to be different things, creating a confusion of technical terms.

  • But after all, what is an array ? Is a list indexed sequentially? Or is it a container of manually indexed items (as in PHP)?

  • Would it be correct to say that the PHP array array concept is wrong ? If it is "wrong", what would be the most appropriate name for the array of this language?

  • List and array is the same thing? If not, what's the difference?

Related questions:

asked by anonymous 21.04.2017 / 16:49

5 answers

17
  

But after all, what is an array ? Is a list indexed sequentially? Or is it a container of manually indexed items (as in PHP)?

Formally anything other than a single, continuous sequence of values is not an array .

Keep using the term that everyone in the technology community uses.

Each technology can name whatever you want for each element of it. This is not to say that it is formally correct in computing, or even in mathematics since computing is a specific application of mathematics.

  

Would it be correct to say that the array concept of the PHP language is wrong? If it is "wrong", what would be the most appropriate name for the "array" of that language?

It's hard to say that concretely.

PHP has a structure with sparse elements and its access is made by a key that is not the position of the element in the sequence. At least it calls array and array is just a shortened form. Paying attention to the documentation is said to be an associative array even though it uses the term Array in syntax.

Roughly it is the same as a hash table. You do not need to call hash table , because this can only be implementation detail. Some people call it a map or dictionary.

It is far from ideal in performance, but as it is to run scripts nothing too troublesome. Both array and hash table have complexity O (1), but array does a simple pointer arithmetic, / em> needs a more complex arithmetic and in some cases the complexity of the formula can be O (N) in relation to the size of the object that serves as a key.

In the same way that hash is spoken when actually speaking hash table . Or when you use list for linked list. So depending on where to see something may seem wrong, there is place to sort it in the right way, without simplification.

  

List and array is the same thing? If not, what's the difference?

List is a set of values that have a certain sequence, but the exact form of organization in memory and access to it is not defined. A list must accept new elements. An array does not usually accept.

Although the array name can be used, there are more specific names for more specific data structures, except for the purest vector. List can be used thus freely, but depending on how it is implemented it may have a more specific name.

See What is the function of array (vector)? .

    
21.04.2017 / 17:21
6

"Array" is a word that already existed long before programming. This is what it means, according to Dictionary.com :

  

verb (used with object)
  1.   to place in proper or desired order; marshal:   (...)
noun
  3.   order or arrangement,
of troops drawn up for battle
  (...)
  5.   a large and impressive grouping or organization of things:   I could not dismiss the array of facts.
  6.   regular order or arrangement; series:   an array of figures.   7.   a large group, number, or quantity of people or things:   an impressive array of scholars; an imposing array of books.   (...)
  9.   an arrangement of interrelated objects or items of equipment for accomplishing a particular task:   thousands of solar cells in one vast array.

All these meanings can be summed up in Portuguese as "a set of things."

When the first programming languages were created, it was necessary to create a data structure that could store a variable amount of information. The name given to this type of structure was "Array" . The only requirement he had to meet was to store several items in an orderly fashion. Over time, new needs arose, and for every need a new data structure emerged: stack, queue, tree, etc.

Here's an interesting thing happening. The other structures are either not "embedded" in most languages / platforms, or there are libraries with implementations for them. But the array is something so simple that it is part of the standard implementation of most of the more common languages (including it is used internally to implement several other structures like the stack).

We know that arrays are something conceptual, simple and almost every language has. The way each language implements this concept, however, varies.

In Javascript, for example, the Array resembles a simple linked list (emphasis in "resembles" ... Each Javascript engine and interpreter implements in a different way). In C and C ++, an array is a pointer. That's right, a pointer! The array in these languages is a "syntactic sugar" to facilitate memory navigation.

To characterize the array at the implementation level, we would have to characterize each language - and there are many of them. More useful is to understand the array by its concept. For simplicity, think of it only as a framework where you store data in an orderly fashion. If you can add items beyond the declared size initially, you can mix different types and other behaviors will vary according to the language you use - so it's best to choose some languages that you like best, understand how array behaves in them, and learn the most common techniques of use. Good study!

    
21.04.2017 / 17:22
6

Array is a primitive data structure on which you cited ( Listas , Tuplas ) and other Objetos storing data can be constructed.

Independent language , array , is nothing more than a continuous space in the memory reserved for saving data . This way they can be accessed quickly and directly only using the index of the desired position.

Unlike other complex structures, such as lists, which must necessarily have access to the previous or later elements (depending on the type of list).

Below you can see the representation of this structure in memory as well as the accesses to elements from the point of view of the programmer and the operating system.

Note that the index value in most languages starts from 0 .

    
21.04.2017 / 17:29
3

Interesting the subject. First, let's think about array in its essence.
We know that a variable is a name, a label that points to a location in memory that stores a value. Studying the language C , from which most of the languages most used today, whether by syntax or because it is based on it, we will see that array is a pointer that points to a continuous region of memory , with fixed size, where we store several data / objects of the same type, and to facilitate their identification, we use the same variable name. The definition that @Wilker put in explains this well:

  

continuous space in the reserved memory to save data

Well, if we take this as an initial concept, a variable that points to a group of objects of the same type can be understood as a array .

Here is a very important feature: continuous and fixed storage. You declare an array, for example like this: int[2] x , which would be an array of two values of type int , identified by the name of "x". Here we can differentiate a list, which is dynamic, that is, allows to add / remove objects, which characterizes an object that is not fixed, and can not be kept in a continuous region of memory, obviously due to being dynamic. p>

So we can say, in a very brief way, that a list would be a array dynamic. Therefore, in my humble opinion, based on these concepts I quote, I could say that:

  • array : object that points to a sequence of objects of the same type, with fixed size, continuously stored;
  • list : object that stores a dynamic sequence of objects, of the same type, stored in a non-continuous way.

We also know that in many languages (such as Java and C# ) list objects have a number of operations that make the job easier, such as searching and sorting, which in the case of array would have to be implemented manually , this also highlights the difference between the two.

    
21.04.2017 / 17:57
0
  

But after all, what is an Array? Is a list indexed sequentially? Or is it a container of manually indexed items (like in PHP)?

Array has its origin in algebra as an array:

Matrix: "Arrangement of m.n mathematical elements arranged in a rectangular or square frame containing m rows and n columns."

List of Matrix Types

  

Would it be correct to say that the PHP Array concept is wrong? If you are "wrong", what would be the most appropriate name for the "Array" of this language?

I think the array in PHP fits the definition of matriz .

  

List and Array is the same thing? If not, what's the difference?

Lista without an index is just a list a Array List is an array.

    
21.04.2017 / 18:13