Chapter 12

Section 12.1

a collection is an object that serves as a repository for other objects
used for objects whose specific role is to provide add, remove and collection management
some maintain some order, others don’t
some are homogeneous (all objects in collection are same type), others are heterogeneous (objects in collection can be of various types)
Vector class can hold any type of object
can be implemented in many ways – underlying data structure could be a variety of things, like an array, a list, etc.
abstract data type (ADT) is a collection of data and the operations allowed on that data
the operations you perform on it are separated from the underlying implementation – it doesn’t matter to us that a Vector object is implemented using an array. We just use the operations of a Vector and trust the class to make it work

arrays are limited with their fixed size
dynamic data structure is implemented using links – use references as links between objects
considered a dynamic structure because links are added as needed
all objects are created dynamically using “new”, and the variable keeping track of that object is a reference to that object
can create a linked list by setting references of each link
last node in the link would have a reference of null
listing 12.1, 12.2, 12.3, p. 500, 501, 503
uses add method, but could also use insert and delete
can also do doubly linked lists, or a list with a header that knows the front reference and the tail reference

a queue is a linked list where the first item put in the list is the first item off the list (FIFO)
uses enqueue to add items to rear of list
uses dequeue to remove items from the front of the list
uses empty to return true or false if queue is empty or not
a stack is a linked list where the last item put in the list is the first item off the list (LIFO)
uses push to push item on the top of the list
uses pop to pop items off the top of the list
uses peek to retrieve the top element without removing it (to peek at it for some information)
uses empty to return true or false if the stack is empty or not
Java has a Stack class, derived from Vector
listing 12.4, p. 508