Formal definition of the Dynamic Array - what is the Dynamic Array

Question

I've researched quite a bit about this topic. Since I'm kind of a fan of Exact Sciences, I love everything to have a crystal-clear and determined definition, without any ambiguous or dubious points.

Dynamic Array, according to the Wikipedia's article, is a Data Structure. Article states, that:

Dynamic array (also called as growable array, resizable array, dynamic table, or array list) is a random access, variable-size list data structure that allows elements to be added or removed.

This/above definition, surprisingly coincides with the definition of the Dynamic Array provided in the Data Structures and Algorithms Made Easy book (Chapter 3.5), by Narasimha Karumanchi.

However!,

We know, that the Data Structure, by its formal definition, is a specialized implementation of the Abstract Data Type (ADT), but I have never seen, in any programming language ever, any specialized Data Structure called Dynamic Array, nor can I find any ADT which is implemented by Dynamic Array.

For instance, we have several Data Structures, in Java, which implement List interface (and interface constitutes an ADT, in this case, as similarly to the concept of ADT, it declares the abstract behavioural characteristic of What must be done, and - says nothing about How), and Dynamic Array is defined (as shown above) as a Data Structure implementing a concept of the Array with the functionality of adding and removing elements in/from it. Many resources (including books provided) define the model of the Dynamic Array as implementations of List - namely ArrayList and LinkedList in the case of Java.

So,

1. if the Dynamic Array is a Data Structure, then what is the ADT implemented by that Data Structure?
2. Maybe Dynamic Array suits more the concept of ADT where the implementations of it are provided in a different ways (example in Java is classes implementing List)?
3. What is the formal definition of Dynamic Array? is it ADT? is it Data Structure? as I find the definitions in the books/articles, quite contradictory and they oppose each other.

I, personally, think of defining it as a special type of Array Abstract Data Type, in which, structure is not a fixed-sized. I'd call it a special type of Array ADT, which makes it also ADT. Because, it's obvious, that if the Data Structures implementing the Dynamic Array (as said in the provided resources) are very concrete classes like LinkedList and ArrayList then the Dynamic Array itself is no longer a Data Structure, but rather it's some special kind of Array ADT.

What is the Dynamic Array? how it should be correctly and formally defined? Maybe it's just a concept of non-fixed-sized array, which is a conceptual model and has nothing to do with any ADT or DS?

Answer 1

I'm not sure what you mean by this:

I have never seen, in any programming language ever, any specialized Data Structure called Dynamic Array, nor can I find any ADT which is implemented by Dynamic Array.

There are many examples of dynamic arrays in mainstream programming languages:

• Python: list
• C++: std::vector
• Java: ArrayList
• Rust: Vec
• OCaml (Batteries included): BatDynArray
• Javascript: array (when dense)
• and many others...

To answer your question about whether or not dynamic arrays are data structures or ADTs: why not both? Clearly, there is a well-known implementation technique known as a "dynamic array" which is characterized by random-access arrays and exponential resizing. So in this sense, there is an agreed upon notion of a "dynamic array data structure". But also, in many of the examples I gave above, the library interface exposes functionality for explicit resizing (e.g. trimming to size). This suggests that dynamic arrays could be considered as an ADT, because the library interface includes details of performance semantics. And presumably, the "dynamic array data structure" is not the only possible implementation of the "dynamic array ADT".

Answer 2

Never looked at e.g. Perl, or C++, or a lot of other languages...

In Perl (and Raku, it's successor), an array is (at least) just as big as needed for it's last element. If I say in Raku:

my @a = 1, 2, 3;

I've got a 3-element array called @a, and @a[10] = 42; extends it to 11 elements (zero based). You can also apply push, pop, shift, unshift (add/remove at the top or the start of the array).

C++'s vector is also an extensible array.

C's standard library offers the realloc(3) routine, that enlarges (or reduces) a heap based memory area, copying data if needed.

Answer 3

As an example, in Objective-C and Swift the fact that an array is dynamic is never mentioned at all. An array is either immutable (you can't change it's elements, so no reasonable person would expect to be able to add or remove elements if you can't even change them), or it is mutable (and if it is mutable, then you can change any aspects of it, including the values of its elements, and the number of elements).

We don't even mention that a mutable array is dynamic because the fact seems so obvious. (And mutable arrays are really nice to build things like stacks, FiFo lists, priority queues and probably many other things, which are all just mutable lists with a few functions added. Other things like dictionaries and sets use mutable arrays internally).

As an exercise, design a mutable array where adding and removing items both at the beginning and the end of the array can be done in constant time. As a second exercise design an array where the amortized time to insert and remove items or sequences of items at index $i_1$, $i_2$, $i_3$ etc. is proportional to the sum of the distances $|i_1 - i_2|$, $|i_3 - i_2|$, etc. plus the number of items added or removed. In other words, applying many sequential changes in the array is fast.