Collection Classes – LINKED LIST
The Java 2 platform contains a Collections API
This group of classes represent various data structures that store and manage objects
It includes classes such as ArrayList and LinkedList
Abstract Data Types – A Review
An abstract data type (ADT) is :
an organized collection of information containing
a set of operations used to manage that information
The set of operations includes methods such as add, delete , find etc..
The set of operations/methods define the interface to the ADT
A List ADT, for instance would define the operations that be used with the list, such as add, delete.
We have looked an array implementation of a list, now we will look at a Linked List.
DRAWBACKS OF ARRAYS
Static vs. Dynamic Structures
A static data structure has a fixed size
Arrays are static; once you define the number of elements it can hold, it doesn’t change.
The array implementation of our collection has one serious drawback:
you must know the maximum number of items in your collection when you create it.
WHAT IF YOU DON’T KNOW THE NUMBER OF ITEMS BEFOREHAND?????
WHAT IF THE NUMBER OF ITEMS WILL VARY OVER TIME?
We need a dynamic data structure that grows and shrinks as necessary
Must specify size at construction time
WHICH GIVES RISE TO “Murphy’s law”
Construct an array with space for n
n = twice your estimate of largest collection
Tomorrow you’ll need n+1