Lists

Lists are ordered data, it is implemented as List Interface in Java, The List Interface contains an Array Lists and Linked Lists

Array List

A class that supports dynamic arrays, the size of the array grows as elements are inserted, it can store any Java object

List Instantiation

Define as a List Reference instead of a ArrayList

List<String> list = new ArrayList<>();

So that the type of List can be changed easily in testing

Growth of Array List

The Array List grows by every time the size of the array reaches its allotted size
Array Lists do not resize when elements are removed

Iterator: A built-in object to loop elements in order
Amortized: The expected run time over a

Pre vs Post incrementer

Different incrementers can be used based on necessity
x++ is a post incrementer that returns the current value before modifying it
++x is a pre incrementer that modifies the value before returning it

Time Complexity of Array List

The Time Complexity of common Array List methods are as follows

add(element):

: When array does not need to be expanded
: When the array needs to be expanded
: Amortized Time
add(index, element):
get(index):
remove(index):
indexOf(element):

Linked Lists

Linked Lists are dynamic lists made out of nodes

Nodes

All objects in a Linked List must be encapsulated by a node, which contains the value and a pointer to the next node in the list
They can be added and removed as needed, in any order from the List

Heads & Tails

All Linked Lists must have a head, otherwise the linked list will be headless
A headless list will not be referred and will be collected by the garbage collector

The head refers to the starting node in the List

Linked Lists can have a tail which refers to the end of the List

Java Method Arguments

When a method is called, all passed-in arguments are copies of a pointer of that value, meaning the argument is completely local

	int a = 8;
	boolean isNextEven(int number) {
		number++; // number will be 9; a will still be 8
		return (number%2==0);
	}

Time Complexity of Array List

The Time Complexity of common Array List methods are as follows

add(element):

: With tail pointer
: Without tail pointer
add(index, element):
get(index):
remove(index):
indexOf(element):