0
$\begingroup$

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?

$\endgroup$
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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.. $\endgroup$ – Giorgi Tsiklauri Apr 8 at 5:43
0
$\begingroup$

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.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Giorgi Tsiklauri Apr 11 at 6:33
0
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.