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

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?

• Computer science is not an "Exact Science", and terms are often used by different people in slightly different ways -- yet we still manage to communicate successfully. I suspect that if you start from the expectation that every phrase and concept should have a single precise definition that's used the same way by everyone, then you might be disappointed a lot...
– D.W.
Oct 8 '20 at 17:49
• @D.W. a bit late answer on your comment. :) (sorry for that): I don't start, per se, it's been more than decade of my CS professional education and career.. :) I just started to dig deeper into DS/Algorithms, lately, and there I meet a lot of formal definitions (which I love, cause I'm a big lover and advocate of the theoretical CS). One thing which I really didn't know is, that CS is not an Exact Science.. and yes, me, being a type of perfectionist, will probably get annoyed several times with these distinctions. Mar 8 at 10:10

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".

• Thanks for your effort. I mean what I say. Things that you write are particular implementations of the Dynamic Array concept.. and I write, that "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.". Actually, that's all about my question - what precisely is the Dynamic Array. Mar 8 at 10:14

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.

• That means, that in Perl, array (not sure how exactly you declare/define it - array?, it doesn't matter) is an implementation of Dynamic Array concept, rather than ordinary and classical Array Abstract Data Type. Interesting.. I have 0 knowledge of Perl, but I see, that it provides OOP facilities. Is that array a reference type of construct? like Class or something alike? or is that a primitive? Thanks for this input; however, this doesn't answer my question.. Apr 8 '20 at 5:43

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.

• I think your answer doesn't respond to my question.. it rather talks about a very specific implementation of the array.. pay attention, that my question is more conceptual, it imples to have a clear formal and official definition for the Dynamic data manipulation structure/type. Array, as such, even before Objective C or any other programming language could've been defined as an ADT, implementations of which in different programming languages today, give quite similar functionalities, yet they are different. I'm looking for formal/official/scientific/exact definition of the Dynamic Array. Apr 11 '20 at 6:33
• Well, you say you like everything crystal clear and the real world isn’t like that. What the answer says clearly: Asking about an abstract data type “dynamic array” is pointless, and so is asking about the implementation when there are many different ones. Oct 8 '20 at 15:42