Are Arrays Sequential AND Indexed?

[Dylan Kwon]

They have a set order and can be sorted, so they are sequential, and they have indices that allow you to access their elements in random order, so are they also indexed?

[Mike Simmons]

Yes.

[Dylan Kwon]

Mike Simmons wrote:Yes.

Thank you!

[Paul Anilprem]

Dylan Kwon wrote: They have a set order and can be sorted, so they are sequential,

This is a loose statement and the reasoning part is entirely incorrect. What exactly do you understand by "sequential"? As per wikipedia,

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.

This is not the case with any indexed data structure.

Dylan Kwon wrote:and they have indices that allow you to access their elements in random order, so are they also indexed?

Yes.

So, you see, these two things are contradictory. If a data structure is indexed, it cannot be sequential.

Yes, single dimensional arrays do store values in sequence in memory (at least that is what it looks like in Java and other languages) but that is not a necessity.

Further, multi-dimensional arrays in Java are definitely not sequential (unlike in C) from even a memory perspective.

[Stephan van Hulst]

Paul Anilprem wrote:So, you see, these two things are contradictory. If a data structure is indexed, it cannot be sequential.

This is not true.

"Indexed" means that every element has a well defined index. Whether the element can be accessed by the index in constant time (random access) or in linear time (sequential access) does not matter.

A linked list is both indexed and supports sequential access.

I think what Dylan is trying to say is correct, but they're not using the correct word. Arrays are not "sequential and indexed", they are "ordered and indexed".

[Paul Anilprem]

Did you notice this part of the quote from the wiki?

... if one can only visit the values it contains in one particular order.

My reply is according to that definition.

Of course, that page also notes, "There is no consistent definition in computer science of sequential access or sequentiality".

[Stephan van Hulst]

I'm not arguing the definition you used for the word "sequential".

I'm arguing that this definition does not preclude a "sequential collection" from being "indexed".

[Paul Anilprem]

Stephan van Hulst wrote:I'm not arguing the definition you used for the word "sequential".

I'm arguing that this definition does not preclude a "sequential collection" from being "indexed".

I never said anything about "sequential collection".

I said, "if a data structure is indexed, it cannot be sequential." and that is correct. By definition quoted above.

(Fixed typo)

[Stephan van Hulst]

Then allow me to quote from the same Wikipedia page as well:

Indexing into a list that has sequential access requires O(n) time, where n is the index.

[Paul Anilprem]

Providing "sequential access" and being "sequential" are two different things. It is possible to have more than one type of ways to access elements and one of those ways could be sequential - but in that case, the data structure is not sequential.  Arrays are not sequential. They are indexed.

[Stephan van Hulst]

Linked lists are sequential. Linked lists are indexed.

If "sequential" contradicts "indexed", then please tell me which of these two properties doesn't hold for linked list and why.

[Paul Anilprem]

A linked list is indeed sequential because it provides only one way (sequential) access. The java.util.LinkedList class provides indexed as well as sequential access, hence, it is not a sequential data structure.

This seems quite clear from the definition that we are talking about. If you have another definition for a sequential data structure, please quote.

[Paul Anilprem]

Can you access elements of a data structure in more than one way? Yes? Then it is not a sequential data structure.

[Tim Holloway]

Paul Anilprem wrote:A linked list is indeed sequential because it provides only one way (sequential) access.

That depends on the implementation. The Amiga OS was built from the ground up using doubly-linked lists, traversable in either direction. Virtually every kernel object was an element of a doubly-linked list.

I noted that the Java LinkedList class defines a descendingIterator for running the List backwards, although for a singly-linked list, it's probably not going to be very efficient.

[Campbell Ritchie]

Tim Holloway wrote:. . . the Java LinkedList class defines a descendingIterator . . .

That is an implementation detail, but I think it is a subtype of Iterator called ListIterator. Another implementation detail: that linked list is doubly linked.

[Paul Anilprem]

Well, a doubly-linked list is not a sequential data structure because it provides more than one way of accessing its element, as per the above referred definition .

I do understand why one may intuitively feel that it is a sequential data structure, and they are not wrong. It is just that they are not clear on what their definition of a sequential data structure is.

[Stephan van Hulst]

Given the following class:

final class SimpleLinkedList<E> implements Iterable<E> {

  private static final class Node<E> {

    E element;

    Node<E> next;

    Node(E element) {
      this.element = element;
    }
  }

  private Node<E> firstNode;

  @Override
  public Iterator<E> iterator() {
    return new Iterator<>() {
      private Node<E> next = firstNode;

      @Override
      public boolean hasNext() {
        return next != null;
      }

      @Override
      public E next() {
        if (next == null) {
          throw new NoSuchElementException();
        }

        var result = next.element;

        next = next.next;

        return result;
      }
    };
  }

  void add(E element) {
    var newNode = new Node<>(element);

    findLastNode().ifPresentOrElse(
      node -> node.next = newNode,
      () -> firstNode = newNode
    );
  }

  private Optional<Node<E>> findLastNode() {
    return findNode(node -> node.next == null);
  }

  private Optional<Node<E>> findNode(Predicate<? super Node<E>> predicate) {
    for (
      var node = firstNode;
      node != null;
      node = node.next
    ) {
      if (predicate.test(node)) {
        return Optional.of(node);
      }
    }

    return Optional.empty();
  }
}

I think you'd agree that the above is a sequential data structure.

But as soon as I add the following method:

  Optional<E> get(int index) {
    var i = 0;

    for (var element: this) {
      if (index == i++) {
        return Optional.of(element);
      }
    }

    return Optional.empty();
  }

According to your interpretation of the definition given in the cited Wikipedia article, it just stops being a sequential data structure, even though nothing in the inner workings of the class has changed?

I don't think such a definition would be useful, and I don't think your interpretation is correct.

[Paul Anilprem]

According to your interpretation of the definition given in the cited Wikipedia article, it just stops being a sequential data structure, even though nothing in the inner workings of the class has changed?

The part that you are referring to as "inner workings" is unchanged and is indeed sequential. But you are not calling the "inner workings" part as the "data structure". The data structure that the world see is SimpleLinkedList (not the "inner workings" part) and adding the method to provide indexed access does change SimpleLinkedList. It is no more a sequential data structure and shouldn't be treated as such. You changed its interface. Do you expect the users to look at the implementation instead of what it promises through its API?

I don't think such a definition would be useful, and I don't think your interpretation is correct.

May be my interpretation is incorrect, but I am not sure what is your interpretation of "one can only visit the values it contains in one particular order".

[Paul Anilprem]

Just to add, I would call it a bad implementation of a non-sequential data structure.

[Tim Holloway]

wikipedia wrote:There is no consistent definition in computer science of sequential access or sequentiality.

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.

I note also the lack of substantial sourcing for this definition. Anything that's that fundamental that hasn't been addressed at least once in early-era ACM or IEEE publications would surprise me. Almost everything of that nature was dealt with in the late 1950s and early 1960s by people like Djikstra, Hoare, and others. To say nothing of Knuth's sourcing from those papers.

As a practical note, in JavaServer Faces, there are certain model collections that absolutely must be enumerable sequentially and idempotently. JSF may make up to 5 queries on that collection in order to manage a View, so it is critical that nothing changes either in content or in order on any of those queries. But it doesn't give a   whether there is one and only one type of iterator available or not so long as there is one primary (getIterator or index incrementor) for that collection (which includes arrays).

[Paul Anilprem]

Tim Holloway wrote:

wikipedia wrote:There is no consistent definition in computer science of sequential access or sequentiality.

Yes, I already acknowledged that in an earlier post and I too am curious to know a better definition of sequential  

[Mike Simmons]

I think several of us here will remember ISAM structures, which of course stands for Indexed Sequential Access Method.  There's a long tradition that "sequential" doesn't necessarily mean that's the only way to access something.

[Stephan van Hulst]

Paul Anilprem wrote:The data structure that the world see is SimpleLinkedList (not the "inner workings" part) and adding the method to provide indexed access does change SimpleLinkedList. It is no more a sequential data structure and shouldn't be treated as such.

That makes absolutely no sense. Adding a method called get(index) does not magically make its elements accessible in a random-access fashion. This would be clearly documented in the Javadoc for the method, which IS part of the class' public API.

May be my interpretation is incorrect, but I am not sure what is your interpretation of "one can only visit the values it contains in one particular order".

You'll notice that the get(index) method still has to traverse every element before the indexed element in order to access the indexed element. That's the meaning of sequential access, and this sequential access is what makes the linked list a sequential collection.

[Tim Holloway]

Stephan van Hulst wrote:
That makes absolutely no sense. Adding a method called get(index) does not magically make its elements accessible in a random-access fashion.

Well, actually, it does.

Doesn't mean that it will make them accessible in a performant fashion, but by definition it does provide random access. No matter how slow.

If a List truly wants to forbid random access, then it should overide and throw an UnimplementedMethodException.

[Paul Anilprem]

Whenever you access all the elements of a data structure, you access them in some sequence. That sequence could be 1 to N, or N to 1, or whatever. By that logic, every data structure can be called sequential because there is always going to be some sequence in which its elements will be accessed.  The word sequential has no meaning if you interpret it that way.

I think the definition given in wikipedia is correct. The whole reason something is deemed sequential is because there is exactly one sequence in which it can be accessed. If there are more than one sequences in which it can be accessed, why would we call it sequential? I am truly at a loss to express it in any other way.

ISAM is not sequential. It is indexed sequential. We are not talking OOP here. "Indexed sequential" is-not "sequential".

Edited: I give up!

Not yet

[Mike Simmons]

Tim Holloway wrote:If a List truly wants to forbid random access, then it should overide and throw an UnimplementedMethodException.

Well, get(int) is not marked as optional in the API.  From Collection:

Certain methods are specified to be optional. If a collection implementation doesn't implement a particular operation, it should define the corresponding method to throw UnsupportedOperationException. Such methods are marked "optional operation" in method specifications of the collections interfaces.

The API for List and its supertypes marks a number of methods as "optional operation" - but get(int) is not one of them.  Generally, it's only the mutators that are optional.

In practice, the compiler won't stop us from throwing UnsupportedOperationException from any method we want to.  But it's outside of the general contract, though not explicitly forbidden.

[Tim Holloway]

Paul Anilprem wrote:
Yes, I already acknowledged that in an earlier post and I too am curious to know a better definition of sequential  

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. That's a definition that I think few will argue with (aside from possibly being tautologous) both in abstract mathematics and practical computer science. How that sequence is realized is not important in the abstract, though it can definitely affect performance.

Also, it's important to be aware of the difference between a "collection" (an abstract term) and a Collection. Sets, Bags (not a Java class), and Maps are collections, but they are most definitely not Collections. That's because a Collection is required by its interface contract to implement an iterator and Java defines an iterator to be something that returns a repeatable sequence.

Just to confuse things, there are subclasses of Sets and Maps that are iterable and may be formally Java Collections, but the bases for Sets and Maps are out in the cold.

So in JSF, for example, a collection property can be an array or a List, but as more than one querant to the JSF forum has discovered to their sorrow, it cannot (safely) be a HashMap.

[Mike Simmons]

Speaking of supertypes, in the Java world we now have SequencedCollection, which does not exclude indexed access.  Of course this is a recent development and does not prevent other definitions of "sequential" - but I think it's a good indicator of how the term is often used nowadays, at least.

[Tim Holloway]

Paul Anilprem wrote:Whenever you access all the elements of a data structure, you access them in some sequence!

Untrue. I'd refer you to my copy of "Content-Addressable Parallel Processors", but it's probably long out of print. Von Neumann isn't the only way to compute, and in fact, the reason why accelerated graphics cards have become so popular is precisely because they can take a thousand processors and operate them in parallel.

And no, I don't always access elements of a collection using the same sequencer. There's a difference between having a sequence and accessing sequentially. You can access a collection sequentially any way that you like as long as there is at least one way to relate all the nodes in the collection in a consistent manner. It is the Collection that's madatimg a primary iteration sequence, not the concept of collections as a whole.

A Collection is not a data structure, by the way. At best, you may have an object ("data structure") that anchors (or at least taps into) a collection, but again, that's not an abstract requirement.

You can see access to all elements of a data structure in the "new" Java Streams facility. They define operations over a collection in a context-free way, making it possible for massively-parallel processors to do their work without ever sequencing anything. There is already logic in there to facilitate that.

[Mike Simmons]

Tim Holloway wrote:

Stephan van Hulst wrote:That makes absolutely no sense. Adding a method called get(index) does not magically make its elements accessible in a random-access fashion.

Well, actually, it does.

Doesn't mean that it will make them accessible in a performant fashion, but by definition it does provide random access. No matter how slow.

Which reminds me... this issue is why they introduced another interface, RandomAccess.  That definition does expect the access to be "fast" - though as they say, "It is recognized that the distinction between random and sequential access is often fuzzy."  And once again, that doesn't mean there aren't other definitions of "random access" out there - but it does seem to be a reasonable signpost for the Java programming world.

[Tim Holloway]

Mike Simmons wrote:
Well, get(int) is not marked as optional in the API.

I agree technically. In actual practice, I've coded a lot of UnimplementedMethod overrides. Either because I was too lazy to implement the entire contract and didn't need those methods or because the method wasn't really applicable to the implementation (especially for JDBC driver-type stuff). A UME not only satisfies the compiler, it's anti-bugging in the event that a method that "never gets called" - gets called.

[Mike Simmons]

Yeah, I do it too.  In fact, in the past I had IntelliJ set up so that the default implementation of "implement a method" was to make a method that simply threw UnsupportedOperationException, with a "// TODO: implement this!" comment.  Makes it easier to run and test with a partial implementation, especially if you're figuring out as you go, which methods do you really need.  I guess I lost that config last time I upgraded my machine.  Maybe I'll set it up again, now...

[Edit] Found it under Settings -> Editor -> File and Code Templates -> Implemented Method Body.  I replaced the default

#if ( $RETURN_TYPE != "void" )return $DEFAULT_RETURN_VALUE;#end

with

// TODO: implement!
throw new UnsupportedOperationException();

[Tim Holloway]

Here's a definition that sounds suitably pompous:

A Sequence is a 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.

[Paul Anilprem]

One more try:
I have 10 strings.  I create a linked list, a doubly linked list, and an array to store those 10 strings.

I want to access the 9th string.

1. In linked list, no matter which string I want to access, I will always have to go through the same sequence until I reach the desired string.
2. In a doubly linked list, I have a choice between two sequences.
3, In an array, I have multiple choices.

Which one is sequential? Of course, the one with exactly one sequence. The other two, imho, are not sequential.

[Paul Anilprem]

Tim Holloway wrote:

Paul Anilprem wrote:Whenever you access all the elements of a data structure, you access them in some sequence!

Untrue. I'd refer you to my copy of "Content-Addressable Parallel Processors", but it's probably long out of print. Von Neumann isn't the only way to compute, and in fact, the reason why accelerated graphics cards have become so popular is precisely because they can take a thousand processors and operate them in parallel.

And no, I don't always access elements of a collection using the same sequencer. There's a difference between having a sequence and accessing sequentially. You can access a collection sequentially any way that you like as long as there is at least one way to relate all the nodes in the collection in a consistent manner. It is the Collection that's madatimg a primary iteration sequence, not the concept of collections as a whole.

A Collection is not a data structure, by the way. At best, you may have an object ("data structure") that anchors (or at least taps into) a collection, but again, that's not an abstract requirement.

You can see access to all elements of a data structure in the "new" Java Streams facility. They define operations over a collection in a context-free way, making it possible for massively-parallel processors to do their work without ever sequencing anything. There is already logic in there to facilitate that.

May be I did not convey it correctly.

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.

[Mike Simmons]

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.

Now, if we were to agree on a particular set of definitions, I would be happy to change my answers accordingly - at least for purposes of that conversation.  I can adapt to other definitions as needed, if they are specified.  The world will always have multiple definitions of terms I want to use, and it's helpful to recognize that ambiguity can exist, and not be paralyzed by that.