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 $2 𝑛 + 1$ 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 $𝑛 \to \infty$

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):

$Θ (1)$ : When array does not need to be expanded
$Θ (𝑛)$ : When the array needs to be expanded
$Θ (1)$ : Amortized Time
add(index, element):
$𝑂 (𝑛)$
get(index):
$Θ (1)$
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):

$Θ (1)$ : With tail pointer
$Θ (𝑛)$ : Without tail pointer
add(index, element):
$𝑂 (𝑛)$
get(index):
$𝑂 (𝑛)$
remove(index):
$𝑂 (𝑛)$
indexOf(element):
$𝑂 (𝑛)$