The Abstact data type Wikipedia article has a lot to say.
In computer science, an abstract data type (ADT) is a mathematical model for a certain class of data structures that have similar behavior; or for certain data types of one or more programming languages that have similar semantics. An abstract data type is defined indirectly, only by the operations that may be performed on it and by mathematical constraints on the effects (and possibly cost) of those operations.
In slightly more concrete terms, you can take Java’s List
interface as an example. The interface doesn’t explicitly define any behavior at all because there is no concrete List
class. The interface only defines a set of methods that other classes (e.g. ArrayList
and LinkedList
) must implement in order to be considered a List
.
A collection is another abstract data type. In the case of Java’s Collection
interface, it’s even more abstract than List
, since
The
List
interface places additional stipulations, beyond those specified in theCollection
interface, on the contracts of theiterator
,add
,remove
,equals
, andhashCode
methods.
A bag is also known as a multiset.
In mathematics, the notion of multiset (or bag) is a generalization of the notion of set in which members are allowed to appear more than once. For example, there is a unique set that contains the elements a and b and no others, but there are many multisets with this property, such as the multiset that contains two copies of a and one of b or the multiset that contains three copies of both a and b.
In Java, a Bag would be a collection that implements a very simple interface. You only need to be able to add items to a bag, check its size, and iterate over the items it contains. See Bag.java for an example implementation (from Sedgewick & Wayne’s Algorithms 4th edition).