3

Sedgewick's Algorithm 4ed says

Several fundamental data types involve collections of objects. Specifically, the set of values is a collection of objects, and the operations revolve around adding, removing, or examining objects in the collection. In this section, we consider three such data types, known as the bag, the queue, and the stack. They differ in the specification of which object is to be removed or examined next.

...

A linked list is a recursive data structure that is either empty (null) or a reference to a node having a generic item and a reference to a linked list.

  • Is the concept of "collection" well defined in general programming language theory, or just in Java's language or library?

  • Is a linked list a collection?

    The book doesn't say a linked list is a collection, but says that the three collections, namely a bag, queue and stack, can be implemented in terms of linked lists.

    But it seems that a linked list possesses some features of a collection, but I am not sure if it possesses all the characteristics of a collection to be qualified as a collection.

Thanks.

  • 2
    A linked list is as much a collection as an array, bag, queue, stack, hash table, or tree. – Erik Eidt Oct 7 '16 at 4:39
  • I assume that book is pointing out to the differences between implementations. Queue, bags, stacks, arrays, lists, etc. All are a set of objects (a collection). But the implementation beneath each of them is different (stack implements LIFO, queue implements FIFO and I guess bag implements ¿indexation?). – Laiv Oct 7 '16 at 5:29
5

As far as I am aware, there is no formal definition of "collection" in computing. It's an imprecise term for any construct in a programming language or library that groups (usually) arbitrary items that (usually) share a common type. By this definition, a linked list is absolutely a collection.

In some languages (Java particularly, and the textbook you link to), programmers think of collections as being defined by their API, or in Java, their Interface. In this world, the data structure behind the interface is an implementation detail, and some collections may have multiple implementations using different data structures.

In this world a queue is a queue, and all implementations of a queue obey the contracts of that API, but based on the performance characteristics you are looking for, you might want to use the queue that's backed by a linked list, or by an array.

On other languages (for example, C) this distinction is not commonly made, and developers are far more likely to program directly to their chosen data structure. In this world a linked list is a linked list, and whether it is being used as a bag, a stack or a queue is entirely up to the code that calls it.

So in summary, yes a linked list is a collection, but in some languages you are encouraged not to use it directly, but to hide it behind a layer of abstraction.

2

Bag, queue and stack are conceptual descriptions of collections. This defines how they work. For example, if you use a queue, you can put things in, and get them out in the same order (FIFO - first in, first out).

Linked list however is not so much about usage, it's about implementation. How are the elements wired up? Each element points to the next.

If you want to be very picky, you could say: linked lists can be used as collections, but they might also be used differently. (Although it's hard to make up some example here.)

  • I would disagree with your last statement. A linked list, is by definition a collection. It is a group of independent objects (of some description), loosely collected by pointers. You could argue that it is a looser collection because they do not lump all the pieces together like an array does, but I don't think you can have a linked list that is not a collection. – EvSunWoodard Oct 7 '16 at 19:46
  • I should phrase it like this: The objects of a linked list might not always be regarded as a collection in the first place. Of course you can always say its elements build a collection. As a half-baked example a possible implementation of the responder chain comes into my mind: to process an input event, a list of possible handlers is walked down until one of them handles the event. While they naturally form a collection of handlers, the dominating purpose of the list would be to model the relationship between neighboured/hierarchical elements. It wouldn't collect things in the first place. – Eiko Oct 7 '16 at 20:20

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.