List Summary

List Performance Summary

Static versus Dynamic data structures

Static means memory is allocated at compile time.
E.g., int[] numbers = new int[99];

Dynamic means memory is allocated at run time.
E.g., Node number = new Node(42);

TRADEOFFS

	Static	Dynamic
PRO	Fast Access ("Random access") `get()` is O(1).	Allocate only memory that will be used. Allocate as much memory as needed.
CON	Fixed amount of space.	Slower access, `get()` is O(n).
Example	Calendar - has twelve months Can directly access any month	Customer transactions - unknown amount Must access them sequentially, but don't need to know how many in advance.

Compromises:
1. Just declare a big array and don't worry about "wasted" space.
2. Use an ArrayList, which is a hybrid, and will auto-allocate more space if needed (at considerable cost).