What is the difference between an Array Data Structure and an Array Data-type in the context of a programming language like C?

Question

Wikipedia differentiates an Array Data Structure and an Array Data-type.

What is the difference between an Array Data Structure and an Array Data-type in the context of a programming language like C?

What is this : int array[]={1, 2, 3, 4, 5}; ?

Is it an Array Data Structure or an Array Data-type? Why?

Answer 1

Short answer: Do yourself a favor and just ignore both articles. I don't doubt the good intentions of the authors, but the articles are confusing at best.

What is this : int array[]={1, 2, 3, 4, 5}; ?

Is it an Array Data Structure or an Array Data-type? Why?

It's both. The array data structure discussed in the article by that name is supposed to relate specifically to arrays as implemented in C. The array data type concept is supposed to be more abstract, but C arrays certainly are one implementation of array data type.

Long answer: The difference those two articles consider is the difference between behavior and implementation. As used in the articles, array data structure refers to elements stored sequentially in memory, so that you can calculate the address of any element by:

address = (base address) + (element index * size of a single element)

where 'base address' is the address of the element at index 0.

Array data type, on the other hand, refers to any data type that provides a logical sequence of elements accessed by index. For example, C++ provides std::vector, and Objective-C provides NSArray and NSMutableArray, none of which are likely to be implemented as a contiguous sequence of elements in memory.

The terminology used in the articles isn't very helpful. The definition given at the top of the array data structure article is:

an array data structure or simply array is a data structure consisting of a collection of elements (values or variables), each identified by at least one index

while the definition given for array data type is:

an array type is a data type that is meant to describe a collection of elements (values or variables), each selected by one or more indices that can be computed at run time

It doesn't help that the array data structure article, which is apparently supposed to be about the C-style implementation of arrays, includes discussion of associative arrays and other material that would be far more appropriate in the array data type article. You can learn why this is by reading the discussion page, particularly Proposal to split the article and Array structure. The only thing that's clear about these articles is that the various authors can't make up their collective mind about how 'array' should be defined and explained.

Answer 2

A type is something that the programmer sees; a data structure is how something is implemented behind the scenes. It's conceivable that an array type is implemented behind the scenes with e.g. a hashtable (this is the case for PHP, I think).

In C, there is no distinction; an array type must be implemented with a contiguous block of memory.