What is actually the array?

Question

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

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

In Python, we have something similar to array of Javascript, which would be the list and the tuple, except the latter which is an immutable but similar list.

However, in PHP, the array seems to be a mixture of hash (or as 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 with array of Java, Javascript and other languages, I see that even having the same nomenclature, they seem to be different things, generating a confusion of technical terms.

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

• It would be correct to state that the PHP language 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 is the difference?

Related questions:

• Is there any way to know if an array is associative or sequential? (PHP)

Answer 1

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

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

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

Each technology can name every element of it after itself. This is not to say that formally it is correct in computation, or even in mathematics since computation is a specific application of mathematics.

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

It is difficult to say this concretely.

PHP has a structure with sparse elements and its access made by a key that is not the position of the element in the sequence. At least it calls array associative and probably array is only a shortened form. If you pay attention to the documentation it is said that it is a array associative despite using the term Array in syntax.

Roughly it’s the same as a table hash. You don’t have to call it hash table, including because this may be just implementation detail. Some people call this a map or dictionary.

It is far from ideal in performance, but as it is to perform scripts nothing too problematic. So much array how much hash table have complexity O(1), but the array makes a simple pointer arithmetic, a table hash needs a more complex arithmetic and in some cases the complexity of the formula can be O(n) relative to the size of the key object.

The same way you talk about hash when you’re actually talking hash table. Or when you use list for list on. So depending on where you look something might look wrong, there’s a place that classifies it the right way, without simplification.

List and array is the same thing? If not, what is 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. A array does not usually accept.

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

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

Answer 2

"Array" is a word that existed long before programming. This is its meaning, according to the Dictionary.:

Verb (used with Object)
1. to place in Proper or desired order; marshal: (...)
Noun
3. order or arrangement, as of Troops Drawn up for Battle.
(...)
5. a large and impressive grouping or Organization of Things: He couldn’t 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 summarized, in Portuguese, as "an ordering or positioning of things". Or 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 should meet was to store several items in an orderly manner. Over time, new needs were emerging, and for every need a new data structure emerged: stack, queue, tree etc.

Something interesting happens here. 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 common languages (it is even used internally to implement several other structures like the stack).

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

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

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. To simplify, just think of it as a structure where you store data in an orderly fashion. If you can add items beyond the stated size initially, if you can mix different types and other behaviors will vary according to the language you use - then it’s best to choose some languages you like best, understand how the array behaves in them, and learn the most common techniques of use. Good study!

Answer 3

Array is a primitive data structure about which you quoted (Listas, Tuplas) and others Objetos which store data can be built.

Language-independent, array, is nothing more than a continuous space in the reserved memory to store data. This way they can be accessed quickly and directly only using the desired position index.

Unlike other complex structures, such as lists, which need to be accessed the previous or later elements (depending on the type of list).

---

Below can be seen the representation of this structure in memory as well as the access to the elements from the point of view of the programmer and the operating system.

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

Answer 4

Interesting thing about it. First, let’s think about array in its essence.
We know that a variable is a name, a tag that points to a memory location that stores a value.
Studying the language C, from which derive most of the most widely used languages today, either by syntax or by having AIDS based on it, we will see that a array is a pointer pointing 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 @Wilker put forth explains this well:

continuous space in the reserved memory to store 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 with a array.

Here is a very important feature: continuous and fixed storage. You declare an array, for example like this: int[2] x, what would be an array of two values of the type int, identified by the name of "x".
Here we can already differentiate a list, which is dynamic, ie, 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 because of being dynamic.

So we can say, in a very concise 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 pointing to a sequence of objects of the same type, with fixed size, stored continuously;
• list: object that stores a dynamic sequence of objects of the same type, stored in a noncontinuous manner.

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

Answer 5

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

Array has its origin in algebra as matrix:

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

List of matrix types

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

I believe the array in PHP falls within the definition of matriz.

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

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