I think that arrays and especially sheets (dynamic arrays) are useless, but if they are used, then no?

So I think the type is this: if the array is sorted, then it is sorted for binary search, but for binary search there is a binary search tree (balanced), the insertion / deletion in which will be O (log n), when in the array O (n), there is a sorted array <balanced binary search tree, and if the array is not sorted, then why do we need it, if we can then use a linked list?

For then the search is the same, and the insert / delete is O (1). And the dynamic array is bad, because every time you insert, the service that participates in memory allocation will look for new places in memory, where there will be n + 1 (+1 is a new element) of free cells in a row. That is, a dynamic array spends a lot of effort on searching for cells when a coherent list simply indicates a link to the next. element. Well, if the dynamic array is sorted, then we use a balanced binary search tree, where, too, when inserting / deleting, there will be no messing with cells, just change the links and balance.

So what is the profit of arrays? Why do I see arrays and sheets in each first code (dynamic arrays or lists)?

  • 3
    Garbage ..., shit ..., these of your arrays ... What do you expect with this style of communication? If you do not understand something, this does not mean that it sucks, and you need to be able to properly convey your question. If you are given arguments in favor of arrays and write in your style: Mark Pavlovich is a perfect layman - will it be a shame? (note: by no means think so (about a layman), just an example for understanding) - vikttur
  • You should not swear in questions, it provokes, quite reasonably, other participants to put minuses, although the question itself is quite interesting. I edited, but try to continue to write without the use of dubious vocabulary. In essence, the question is that getting an item by index in arrays will be faster than in any other data structure. - Yuriy SPb ♦
  • Sorry, it was not swearing, it was like a "friendly" style of communication. I thought it was on the "own" stackerflow. - Mark Pavlovich

2 answers 2

The array is the fastest connection model (number <-> number). The speed will be O (1). In the C language, this model is used to implement switch for example. In assembly language or in any language, a number can represent itself as a letter, memory address, difference of memory addresses, etc. Lists and trees, for example, use heap memory, since the size of the list is not fixed, but dynamic. The speed of the operating system is not infinite, it should track the dynamic memory. If to use the fixed array on length int m[10]; , it will be stored on the stack, which does not load the OSes, and the speed gives the maximum. Each data implementation has its own chips and you need to know what you need.

    Convenient storage. You will not push 100 numbers in 100 variables?