Lists

Strongly typed ordered collections of items that as a minimum support two operations:

• Push - places an item onto the "head" of the list
• Pop - removes and returns an item from the head of the list (lists follow the LIFO protocol)

Implementation	Performance	Std. lib equivalent
LinkedList	Constant time operations	LinkedList (actually a doubly linked list)
ArrayList	Constant amortised time operations	List

The elements of an ArrayList are held within a backing array whereas the elements of a LinkedList are represented as a chain of nodes that reference each other. An ArrayList cannot offer guaranteed performance or memory utilisation for a given operation because the backing array may need to be resized.

In practice however following the references of and creating the nodes of a LinkedList is resource intensive, and resizing operations become rarer and rarer as an ArrayList grows in size.