Difference between indexed and sequential data structure

What exactly is the difference between indexed and sequential data structures? For example, HashSet is an indexed data structure but TreeSet is sequential.

When using an index you can read or write data directly to any position in the data structure. If the access is sequential, you have to go through all the elements until you reach the wanted one (like iterating a next method).

This also means access time is constant for an indexed structure, no matter its size, while it increases with the size for a sequential structure.

This applies supposing that the internal implementation of access for indexes (that are actually just an access operation that can be implemented in many ways) is based on some kind of mapping, and that the sequential structure uses some kind of linked lists. This should be aligned with the spirit of the formulated question.

For an example on how this can be different depending on the implementation, lists in Python implement direct access internally, for obvious performance reasons, besides being accessed by the user with an index, not with next methods.

Within java, those terms don't have set meanings. The meanings will be obtained from everyday English usage, and from an examination of the types which you listed.

'Indexed' would mean that there is an index associated with a data structure and which can be used to reference elements of the data structure, with the most basic example being an array, which is indexed by integer offset, or Map, which is indexed by key values. Note that this omits a sense of the data structure having a natural order. We can see that arrays have a natural order but Map does not.

'Sequential' would mean that the data structure has an order which may be used to order operations on the elements of the data structure. There is a sense that this should be a natural order, but the term could also mean that there is an order imposed on the data structure which enables iterative operations.

In neither case should the meanings include a reference to particular operations. A data structure may support reading, or writing, or iteration, but won't necessarily support any or all of these. For example, a sequential data structure could support a findFirst operation without allowing iteration as an external operation.

For the two referenced types, HashSet and TreeMap, since these are implementation types, the terms can be used to describe the general properties of the data structure, or can be used to describe properties of the implementation. I'm not sure that is very useful, since the implementation can change.

Note that 'indexed' doesn't imply 'sequential', unless the index values are themselves sequential.

Let us answer this question in a broader, Data Structures domain, rather than concentrating on Java, or any other implementation, as such.

Indexed data structures

are based on a more general - Random/Direct Access Data Structures concept.

Main benefit of using these data structures is, that they have O(1) time complexity, for both - read and write operations.

For instance, when you define the array, a continuous chain of the same-sized, little memory slices (blocks) are allocated in a physical RAM and each of those slices has, unique, but continuously chained memory address. That means, if, for example, array[0] is stored at 0100X001, array[1] will be allocated at 0100X010 if the slot occupies 1 bit (if more, correspondingly you will have to add that number of bits to each slot);

Sequential Data Structure

on the other hand, are not clearly defined in the Computer Science domain, they, depending on the implementation, have different time complexities for read and write operations, but mostly - it's never O(1).

In the most cases, Sequential Data Structures are implemented in a way, that:

• Each element, except the first, has a reference to its immediate predecessor;
• Each element, except the last, has a reference to its immediate successor.