Are Arrays Sequential AND Indexed?

[Tim Holloway]

Tim Holloway wrote:Here's a definition that sounds suitably pompous (corrected):

A Sequence is a linear Directed Acyclic Graph of elements in a collection (little-c!) such that all elements of the collection appear in the graph exactly once.

A sub-sequence, of course is simply a snippet extracted from a sequence.

A tree can also be a DAG, but it's not a sequence.

[Tim Holloway]

Paul Anilprem wrote:tly.
Even if you try to access multiple elements of a data structure in parallel, for each element that you access, if you have to go through the exact same sequence of elements to reach that element, then that data structure is sequential. Otherwise, it is not. This is what I am trying to convey.

You're still hung up on a limited set of mechanisms and conflating random access with enumeration/iteration. Random access means that "get(n)" returns the n'th element according to some sequence (and for Collections, that is the primary sequence) regardless of how it was located internally. The get() method is a black box. As mentioned, other hardware, other rules. And for that matter, other mechanisms (e.g., Streams) other rules.

an iterator is a decanter of successive elements of the Collection according to the iterator's sequencer. For the getIterator() method, that would be the primary sequence defined for the Collection and getDescendingIterator would be the inverse of the primary sequence. But we can, of course, construct other iterators on a collection by applying a sort to the collection.

Regarding direct access versus enumeraton:

As a degenerate case, an array is accessible by going through the index of the desired object so the sequence is exact, just that the target is also the first and only element you have to step through.

A hash with overflows is also a case where you'd have to go through the same set of elements to get to the goal. A hash is very definitely NOT sequential.

[Paul Anilprem]

Tim Holloway wrote:

wikipedia wrote:In data structures, a data structure is said to have sequential access if one can only visit the values it contains in one particular order.

Said by whom? I'm surprised that this sloppy assertion hasn't been called out by the Wikipedia's editors. They don't generally admit that sort of thing. In fact, I've just called it out myself.

Tim Holloway wrote:
I think that the generally-accepted definition of sequential is that you can access members of a collection by enumerating them and always get them in the same, um, sequence. That is, the order of access is repeatable.

I tend go to wikipedia if I need to find out a generally-accepted meaning of a term because it is eyeballed by a huge number of people and it takes only a few "stickler to detail" types to get the meaning to its generally-accepted state.

But, in this case, as you pointed out, it is surprising that this definition has stayed for so long. May your edit be vetted and be the generally-accepted definition soon.

Your definition, though, does not help us determine whether an array is sequential or not because arrays do not have any intrinsic way to enumerate its items unlike other higher level data structures such as a Java Collection.


The pictorial representation of sequential and random access given on wikipedia along with that article, shows that with random access, one can traverse from any element to any element in any sequence. Since that is exactly what happens with arrays, they are clearly not sequential. That is my understanding as of now and that is what I said in my first post. But if they change the definition, I have no problem in changing my understanding.

So far, in this thread, no one has provided any reference to any authentic material that refutes this.

[Stephan van Hulst]

Paul Anilprem wrote:Your definition, though, does not help us determine whether an array is sequential or not because arrays do not have any intrinsic way to enumerate its items unlike other higher level data structures such as a Java Collection.

I'd say that applying the enhanced for-loop is the intrinsic way to enumerate the elements of an array.

Until now, in this thread, no one has provided any reference to any authentic material that refutes this.

Well, what would you consider an authentic material? In the end, it's all just an appeal to authority. What authority? The first person to use the term? The first person to adopt the term in a lexicon of computer science terms? The first person to bastardize a term borrowed from a field of mathematics?

[Paul Anilprem]

Stephan van Hulst wrote:

Paul Anilprem wrote:Your definition, though, does not help us determine whether an array is sequential or not because arrays do not have any intrinsic way to enumerate its items unlike other higher level data structures such as a Java Collection.

I'd say that applying the enhanced for-loop is the intrinsic way to enumerate the elements of an array.

It is not intrinsic to arrays. It is an external mechanism that can be used to enumerate arrays in one (out of many) ways.

Stephan van Hulst wrote:

Until now, in this thread, no one has provided any reference to any authentic material that refutes this.

Well, what would you consider an authentic material? In the end, it's all just an appeal to authority. What authority? The first person to use the term? The first person to adopt the term in a lexicon of computer science terms? The first person to bastardize a term borrowed from a field of mathematics?

Anything that is viewed and agreed by a large number of people and is democratic enough to incorporate a change if a mistake is spotted. So, wikipedia, a well known book/expert, or something similar would be my top resource. Stackoverflow...and to certain extent coderanch as well in absence of any other material.

Also, for a beginner, it is important to know what is the current generally accepted meaning of a term because they may be required to explain their understanding in an interview. There can always be disagreements based on experience and breadth of knowledge or due to difference in perspectives and that is fine if there is an opportunity to explain/defend a contrarian opinion. No one would second guess your ability if you are an industry expert and have a contrarian view. But for a beginner, taking a contrarian view because "I think so", is not a good idea, imho. The burden of proof is a lot heavier for them. So, if someone on a forum says arrays are sequential, I think it is fair to ask for references for their claim.

[Tim Holloway]

Mike Simmons wrote:Regarding Paul A's "I have 10 strings"  question:

I would usually describe the two linked lists as sequential.  I don't really care that there's more than one way to access it - both ways are sequential.  The array, I wouldn't usually describe as sequential, but I would say you certainly can access it sequentially.  On the other hand, I have no problem with someone describing it as sequential.  Not exclusively sequential, of course.

I was going to let the topic rest, but you've highlighted a good point. An array isn't so much sequential as it is a random data collection which can be accessed by a sequential enumeration of its element indexes. I think that the fact that the indexes are simple ordinal numbers probably gives a false sense of "sequentialness".

The term "sequential" as used as a simple adjective is questionable. What it actually means here is "can be accessed sequentially". Java Collections distort the concept because they demand at a minimum the ability to emit a sequential iterator of consistent characteristics.  I could overload a HashMap to define a getIterator(), but that wouldn't make the Map itself inherently "sequential".

But in the end, the reason for all this nitpicking is to generate awareness of how abstract collections work and how Java Collections work and the differenes between them so that we can use them intelligently and not get bitten.

[Paul Anilprem]

Just to summarize:

Q1: Is the following interpretation of the wiki definition correct?

–---- start -----
Every data structure *can* be accessed sequentially. That sequence can be: 0 to N numbers in increasing order. Or in some other sequence. A tree can also be accessed sequentially but that sequence is not the same as numbers 0 to N in increasing order.

So, it is not the actual sequence in which you access the elements of a ds that makes the ds sequential. It is the number of sequences in which you can access its elements that determines if it is sequential. If it is exactly 1, the ds is sequential. Otherwise not.

----- end ----

Q2: If the above interpretation is correct, I gather that the wiki definition of sequential is deemed incorrect by all of the participants except myself. Right?

[Tim Holloway]

It fails from the get-go.

A data structure is not always a collection. It would be absurd to talk about sequentially accessing, say the jakarta.apache.org.Catalina (tomcat) root javabean, but JavaBeans are very definitely data structures.

A collection may or may not be sequentially accessible. As I noted, an array isn't acually sequential in Java, because it's not a Collection class, and has no getIterator() method. One would have to be externally defined.

A Bag is even more problematic, because a Bag is like a Set except that the same object can be stored in it more than once. Java has no native Bag class, but Smalltalk does.

Trees are an especially interesting case, because they can be iterated by traversing either horizontally or vertically and left-to-right or right-to-level. And that's just for binary trees.

So yeah, the Wikipedia article is more on the "many people are saying" than on established Computer Science definitions. Pity I let my ACM susbscription lapse or I could try chasing references. Doing a google search on "sequence" and "collection" comes up pretty sparse.

On the other hand, I did find 2 articles that may prove food for thought. One is for Python:

https://data-flair.training/blogs/python-sequence/

I don't know if this is official Python, but the author here considers "sequences" and "collections" as defined by Python to be 2 separate types of entities, where a "collection" includes things like dictionaries. In effect, the exact opposite of java.util.Collection.

Another interesting discussion seems to be going on here:

https://stackoverflow.com/questions/19850730/whats-the-difference-between-a-sequence-and-a-collection-in-clojure

I'm not familiar with clojure, but some other stuff I saw seems to indicate that it's another language where collections and their properties are important.

And finally, Java 23 is slated to make non-Collection collections sequentially accessible, or so I read it:

https://dev.to/msmittalas/sequenced-collections-an-upcoming-feature-of-java-21-to-handle-a-sequence-of-elements-in-a-better-way-1452

[Mike Simmons]

Tim Holloway wrote:And finally, Java 23 is slated to make non-Collection collections sequentially accessible, or so I read it:

https://dev.to/msmittalas/sequenced-collections-an-upcoming-feature-of-java-21-to-handle-a-sequence-of-elements-in-a-better-way-1452

That's available now in Java 21, final release, not a preview version. (It's nice when a feature just gets released, without going through multiple iterations of preview versions.)  The SequencedCollection API that I previously referenced is part of that.  I would say that it's both for non-Collection collections (Maps, really), and non-List Collections, if it's something that has some well defined order.  So, LinkedHashSet implements SequencedSet, and LinkedHashMap implements SequencedMap.  But HashSet does not implement SequencedSet or SequencedCollection, and HashMap does not implement SequencedMap.

[Paul Clapham]

Paul Anilprem wrote:Q2: If the above interpretation is correct, I gather that the wiki definition of sequential is deemed incorrect by all of the participants except myself. Right?

I haven't been following this thread but... you linked to a Wikipedia article named "Sequential access". And I believe there was some talk earlier that "being sequential" and "sequential access" were different concepts. So it isn't clear to me that we're looking at a Wikipedia definition of sequential. (And if we are, it's "citation needed".)

However I don't think that describing a thing as "sequential" is a helpful concept -- what does it even to mean to say that a Java array is "sequential"? Presumably people somewhere learn about that concept but I've never heard of it in that form. Sequential access to Java collections and its pros and cons, sure, that's helpful. But naming of things which lead to arguments about what the names mean, not so much.

[Paul Anilprem]

Tim Holloway wrote:
A collection may or may not be sequentially accessible.

Could you please give an example for a collection that is not sequentially accessible and why?

[Paul Anilprem]

Paul Clapham wrote:
However I don't think that describing a thing as "sequential" is a helpful concept -- what does it even to mean to say that a Java array is "sequential"?

Actually, it has been a very helpful and well known concept since the early days of computers in the matter of accessing external storage. Tapes drives were sequential, weren't they? If you know that something is sequential, you know about it properties and behavior.
It does get fuzzy with higher level abstractions such as arrays but the concept applies. It is not inconsequential to say that arrays are not sequential or that streams are sequential (unless they are parallel ). It has a well understood meaning.

[Paul Clapham]

I understand that (now). But I still think it's inconsequential.

It's not that I don't care for abstractions; it's just that I don't care for this particular abstraction. I know perfectly well what can be done with a Java array, and whether it's "sequential" has no relevance to me.

But if there are other people who need to understand "sequential" then I don't want to stand in their way.

[Paul Anilprem]

Well, at least that is what the OP wanted to understand, as evident from the topic of this thread.
I claimed, with reference, that something that is indexed cannot be sequential. Stephen countered and this whole discussion ensued

I think the OP, if they read the thread (I didn't notice it was asked 2 months ago, when I replied), has enough to make up their mind.

[Jeanne Boyarsky]

Interestingly, Java 21 introduces "sequenced collections".So the next version of the exam (Java 21) will have a very specific definition for the word "sequenced" (and therefore "sequential"!