Talk:Dynamic array

Language of example

What language is the example in. Fresheneesz 02:30, 10 June 2006 (UTC)

Pseudocode. Deco 04:51, 10 June 2006 (UTC)

Ok, but its not very clear what the difference between the = operator and the  := operator is - at least for me. Fresheneesz 10:33, 10 June 2006 (UTC)

:= is a conventional operator for assignment. = refers to equality. In this case I think the context makes it obvious. I'd considered using ← for assignment but that's somewhat harder to edit. Deco 21:08, 10 June 2006 (UTC)

I don't know how the use of = as equality is obvious here - especially to programmers who never learned any pseudo code. And in that case, is this line wrong then?:

a.capacity = a.capacity × 2

May I suggest we switch to a *real* language, pseudo code always makes the syntax seems unreliable (not always the same), and real code is easier to look up. Fresheneesz 23:59, 10 June 2006 (UTC)

You might be interested in Wikipedia:Algorithms on Wikipedia. I would be amused if you attempt to change the guidelines to use the One True Programming Language rather than pseudocode. --68.0.120.35 09:12, 5 March 2007 (UTC)

Ha. I'm not gonna pull that kinda stunt. Maybe I would if my programming language ever gets on wikipedia. : ) Fresheneesz 07:12, 8 March 2007 (UTC)

Overview

I thought that the overview section should be kept. Dynamic array is obviously an array data structure. I am not clear about the edit that states "dynamic array is not strictly an array data structure". MegaHasher 06:56, 28 July 2007 (UTC)

I suppose this depends on how you define "array." It's certainly not "obvious" that it is, since an array is frequently defined as a fixed-size data structure. Dcoetzee 03:55, 1 August 2007 (UTC)

The cost of expanding to a larger sized array is not n², but 2n. The amortized cost per insertion is O(1). MegaHasher 07:06, 28 July 2007 (UTC)

The cost is n² with naive expansion for every insertion. This is the point. Dcoetzee 03:56, 1 August 2007 (UTC)

A constant sized array could have elements removed by using a size field, but this fact is probably not notable. MegaHasher 07:06, 28 July 2007 (UTC)

We

This topic has many instances of the 'we' pronoun. Who's 'we'? Is this a recommended style for encyclopedic article? MegaHasher 07:10, 28 July 2007 (UTC)

My fault. Feel free to fix. I'll fix eventually if you don't. Dcoetzee 10:33, 28 July 2007 (UTC)

'the "inclusive we" widely used in professional mathematics writing is sometimes used to present and explain examples in articles, although discouraged on Wikipedia' -- WP:PRONOUNS, via MOS:WE. --DavidCary (talk) 19:56, 12 February 2022 (UTC)

Redirect into Array

Should this page be merged into Array? Is dynamic array a sufficiently broad topic that it can stand as a separate topic? MegaHasher 03:11, 31 July 2007 (UTC)

I'm not sure. It just seemed like there was a lot of redundancy, and we were explaining the same things in two places. MisterSheik 08:48, 31 July 2007 (UTC)

No, no, no. Dynamic arrays aren't even arrays. They're just a data structure built on top of them. It's only briefly summarized in the array article. Dcoetzee 10:30, 31 July 2007 (UTC)

In C++ that's true. In many other languages, static arrays are a special case of dynamic arrays. It's just a matter of perspective. MisterSheik 15:33, 31 July 2007 (UTC)

No, it's totally language-independent. Just because some languages (e.g. Perl) use dynamic arrays to implement the same functions normally performed by fixed-size arrays doesn't mean fixed-sized arrays have ceased to exist conceptually in those languages - they just have to be implemented differently. Besides the whole fixed-size versus dynamic size thing, they support different set of operations, are frequently given different names, and depending on the implementation can have drastically differently indexing operations such as the one described by Brodnik et al.

Besides, some languages (e.g. Lua) implement almost everything, including arrays, using associative arrays, and I don't think you're about to propose merging that into array. Dcoetzee 03:52, 1 August 2007 (UTC)

What does it mean to say that a data structure is a special case of another? I think there should be only two things to check: if the interface of A is a subset of the interface of B, and if the speed (including complexity guarantees) of the operations that data structure A supports is the same as those that B supports, then A is a special case of B. In that case, I'm glad you brought the Brodnik paper up. They suggest that resizable arrays have four operations: read, write, grow, and shrink. It's clear that static arrays have simply omitted grow and shrink, and offer the same complexity guarantees for read and write. MisterSheik 05:08, 1 August 2007 (UTC)

Your argument appears to be saying that fixed-size arrays are in fact a special case of dynamic arrays; but only abstract data structures are defined strictly in terms of their interfaces. This is about as strange as claiming that a "red-black tree" is a special kind of "hash table", because it supports the same operations and also range queries. It isn't typical to implement fixed-size arrays using dynamic arrays (due partly to problems such as linear wasted space), although some scripting languages do it. Nevertheless I'm happy with the current wording, provided the two articles remain separate. Dcoetzee 05:31, 1 August 2007 (UTC)

Isn't this article about an abstract data structure? Hash tables don't support range queries. And there is no wasted space if the constructor for the dynamic array is called with the initial size, just as the constructor for the fixed-size array would be. However, I am also happy with the current wording :) MisterSheik 09:25, 1 August 2007 (UTC)

Hash tables not supporting range queries was my point - and I don't think this article is about an abstract data structure but rather, like hash table and red-black tree, a concrete data structure with a particular implementation, based on geometric expansion of an underlying array. Some of the variants implement the ADT in other ways, but this is the implementation of interest because of its wide use. But anyway, if you're happy I am. :-) Dcoetzee 11:48, 1 August 2007 (UTC)

Okay, I understand your point. But the example isn't a very good one: Hash tables have O(1) expected access time, and Θ(n) worst case time for element find, while red-black trees are always &Theta(log(n)). What you're saying is that this article is about a concrete data types rather than abstract ones. MisterSheik 20:45, 1 August 2007 (UTC)

Recent changes

Okay, here's a list of some things that were modified by recent changes that I changed:

• Dynamic arrays are not supplied with "most standard libraries"; they are not supplied with C, or ML, or Fortran, or Pascal, or countless other standard libraries. The qualifier modern mainstream programming languages is necessary and should not have been removed.
• I don't like use of the ambiguous term static array, which variously means either compile-time allocated array or fixed-size array, so I've eliminated it.
• The text no longer makes a clear distinction between the underlying fixed-size storage and the variable-size storage used for the contents of the dynamic array and no longer clearly explains the concept of capacity. I added a section to more clearly explain this before launching into the discussion of geometric expansion, which is another matter entirely.
• Restored the slightly pedantic explanation that n insertions take O(n) time, under the assumption that people viewing this will not be already familiar with amortized analysis.
• Recent discussion at Talk:Array established that material related to insertion and deletion of elements in fixed-size arrays, and comparison to linked lists, was more appropriate for this article. All this material was subsequently removed. It has to go somewhere - it is referenced here in two places from array. Restored this.
• Text was removed noting that wasted cells were a disadvantage over fixed-size arrays. Restored.
• Discussion of variants was removed, such as the deque variant - it appears that at least some of it was moved to Deque#Dynamic_array_implementation. Linking it properly and expanding it with removed material in the new location. Deques are not strictly speaking "built on top of" dynamic arrays, since this variant changes how the basic data structure is implemented (either the elements are placed in the middle or a circular buffer is used).
• Brief summary of gap buffer doesn't hurt.
• realloc() does not implement dynamic arrays. Where are the insertion and deletion operations? Where are the amortized cost guarantees? realloc() can be used to implement dynamic arrays, but isn't even needed for that (malloc, free, and memcpy are enough). realloc() need not be mentioned here at all.

Changes you guys made that I liked:

• Merging the time-space tradeoff stuff into the discussion. Didn't need its own section.
• Moving deque-related stuff out to deque.
• Removal of the pronoun "we" - bad habit.
• General briefening of some verbose explanation.

Please discuss if you disagree. Dcoetzee 05:23, 1 August 2007 (UTC)

Merger proposal

This page should be merged with Vector (STL). Vector (STL) talks about an implementation of a dynamic array, and most of the content on that page applies to all dynamic arrays. 71.51.124.230 (talk) 19:29, 5 January 2008 (UTC)

• Agreed, this page documents the specific implementation of a dynamic array 16:37, 5 April 2008 (UTC) —Preceding unsigned comment added by Cerf (talk • contribs)

• No, I disagree. Vector STL is just one specific C++ construct. At best you could call it an implementation of dynamic arrays. Boost also released a similar implemenation with vectors. Beyond that, dynamic arrays are available in many other languages than C++. Vector STL is C++ specific. Dlother (talk) 18:14, 21 February 2008 (UTC)

• I agree, but in the reverse direction. The generic parts of Vector (STL) ought to be merged here (or discarded, if they're already here in some form) - and the language-specific parts left there. Dcoetzee 19:03, 21 February 2008 (UTC)

• It doesn't make sense to merge the two. I agree with the second comment. It is just one implementation of dynamic arrays, why should the Dynamic Arrays article focus on the C++ implementation? The C++ implementation is a complete and large subject in its own right. —Preceding unsigned comment added by 24.99.173.164 (talk) 14:59, 29 March 2008 (UTC)

• Definitely should not be merged. Yes, STL vector is an implementation of dynamic arrays, just as a Cadillac is a car, but the wiki page for Cadillac shouldn't be merged into automobile.

--Anniepoo (talk) 01:16, 22 May 2008 (UTC)

• Provided there is truly enough to say about vector - and keep in mind Wikipedia isn't a detailed API guide - it can have its own article. But I think when you boil it down there's really not much left, maybe a paragraph. That is why I suggest merging it into this article. Dcoetzee 07:58, 22 May 2008 (UTC)

• I disagree with the merger. The dynamic array's article should concentrate more on the reason for using a dynamic array and where it differs from a static array as opposed to how it is implemented. The vector class is part of the Standard Template library and as mentioned earlier is probably an "implementation" of dynamic arrays at best. In that case the STL vector could be mentioned in this article but it definitely warrants an article of its own. The present article for STL vector has various implementation specific functions which have absolutely no meaning in dynamic arrays.38.104.0.30 (talk) 18:32, 29 July 2008 (UTC)

• Do not merge, the STL is a special case of the dynamic array, for a specific language. Maybe the article has changed over time; but there is very little in the STL article that seems "generic"; its rather highly C++-specific. linas (talk) 16:46, 27 September 2008 (UTC)
• Do not merge, second the comments above. --Jorge Stolfi (talk) 10:39, 5 May 2009 (UTC)

Efficiency Chart

In the chart in the performance section it says that dynamic arrays have a wasted space of Θ(n). I believe that the vector only need a start and end pointer ( size or other ). This makes the required wasted space linear. There are of course optional things such as extra allocated space but those are not in the definition (and still linear). — Preceding unsigned comment added by Youarefunny (talk • contribs) 19:40, 16 June 2011 (UTC)

The linear wasted space is with reference to the most common dynamic array data structure in which geometric expansion of an underlying array is used. In this case wasted space is linear. For example, when the doubling factor is 2, the wasted space is 3.5n. I'll add a citation to clarify this. Dcoetzee 01:37, 20 June 2011 (UTC)

Sorry, I forgot to subscribe. I meant constant space when I said linear a lot. But I think that there should be some sort of note that there doesn't need to be any wasted space (except for small constant overhead) but that most implementations use geometric expansion. There is no reason to not use dynamic arrays because of space limitations. I think the chart should say O(1) and have a sidenote that many implementations use O(n) wasted space because of geometric doubling. Kevin Cox (talk) 16:00, 14 June 2012 (UTC)

I agree that this article should mention alternatives to geometric expansion, so I added a brief note about "Linearly growing arrays". --DavidCary (talk) 05:28, 18 February 2022 (UTC)

Language support

"Many scripting languages such as Perl and PHP offer dynamic arrays as a built-in primitive data type."

PHP's array type is not a dynamic array; it is an "ordered map" (PHP manual). It is implemented as a hash table with doubly linked buckets (source code). --Viktor Söderqvist (talk) 15:08, 19 June 2011 (UTC)

Terminology

This should not be called a "dynamic array", because it's not an array at all; it's a list data structure backed by an array.

"Dynamic array" has an actual meaning: an array whose size is not static. For example, .NET arrays are dynamic arrays, (resizeable via Array.Resize,) Java arrays are static only, and Delphi offers both static and dynamic arrays. All three also have List data structures as part of their standard libraries. In all three cases, the List data structure is something completely distinct from the array primitive type. Incorrectly conflating the two leads to confusion, and it should be changed. — Preceding unsigned comment added by 67.21.63.147 (talk) 20:58, 23 June 2017 (UTC)

Wikipedia is not the place for pushing your opinions on what terminology should or should not be used; rather, we reflect the terminology used in reliable sources (see WP:SOAPBOX). Since many sources call this a dynamic array, we should also. —David Eppstein (talk) 21:32, 23 June 2017 (UTC)

@David Eppstein: Wikipedia also has an article about variable-length arrays: is this a synonym of "dynamic array?" Jarble (talk) 00:23, 7 April 2021 (UTC)

I don't think so. A VLA appears to be an array that has a fixed size once it's created, but where that size is determined at runtime rather than compile-time. That's different from a dynamic array, where the array size can change after the array object is created. —David Eppstein (talk) 00:28, 7 April 2021 (UTC)

Performance(linked list, insert, middle) should be red

In section Performance, the table has yellow color (everywhere else used for O(log n)) for Linked List => mutate => Middle, and text "peek time + O(1)" but "peek time" is O(n) = red bg color, so "mutate/middle" should also be red. Or am I missing something? — MFH:Talk 22:28, 27 April 2023 (UTC)