Linked lists

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
ac
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.

LINKED LIST

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

ARRAYS LIMITATIONS

Arrays
Simple, Fast
but
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