Contiguous cells
A static list keeps its data in an array: back-to-back cells in contiguous memory. That is why get(1) is a single calculation: it jumps straight to cell 1 without walking. Reading is O(1).
A static list keeps its data in an array: back-to-back cells in contiguous memory.
That is why get(1) is a single calculation: it jumps straight to cell 1 without walking. Reading is O(1).
A static list keeps its data in an array: back-to-back cells in contiguous memory. That is why get(1) is a single calculation: it jumps straight to cell 1 without walking. Reading is O(1).
addFirst(10) needs cell 0 free: first it must shift every element one position to the right.
The for loop moves 30 and then 20; with n elements that is n moves. Inserting at the front costs O(n).
addFirst(10) needs cell 0 free: first it must shift every element one position to the right. The for loop moves 30 and then 20; with n elements that is n moves. Inserting at the front costs O(n).
The linked list uses another piece: the Node, an object with data and a next reference.
Nodes sit scattered across the Heap. Only head knows where it starts; the last one points to null.
The linked list uses another piece: the Node, an object with data and a next reference. Nodes sit scattered across the Heap. Only head knows where it starts; the last one points to null.
addFirst(10) creates fresh with new Node(10): it is born isolated, with next set to null.
If head = fresh goes first, 20 is lost: it compiles, but the garbage collector takes the rest of the list.
addFirst(10) creates fresh with new Node(10): it is born isolated, with next set to null. If head = fresh goes first, 20 is lost: it compiles, but the garbage collector takes the rest of the list.
The right order: fresh.next = head first hooks up node 20, which the list already had.
Only then does head = fresh adopt 10 as the first. No node moved: insertion in O(1).
The right order: fresh.next = head first hooks up node 20, which the list already had. Only then does head = fresh adopt 10 as the first. No node moved: insertion in O(1).
print() walks with an auxiliary variable: current starts at head, which never moves.
Each pass prints current.data and advances with current = current.next until it reaches null.
print() walks with an auxiliary variable: current starts at head, which never moves. Each pass prints current.data and advances with current = current.next until it reaches null.
To remove 20 you have to stand on the previous node: from 20 there is no way back.
previous.next = previous.next.next skips 20; with no references left, the garbage collector takes it.
To remove 20 you have to stand on the previous node: from 20 there is no way back. previous.next = previous.next.next skips 20; with no references left, the garbage collector takes it.
The array pays for insertion so reading is free: reading is O(1), inserting at the front, O(n).
The linked list pays for reading so insertion is free: walking is O(n), hooking up is O(1).
The array pays for insertion so reading is free: reading is O(1), inserting at the front, O(n). The linked list pays for reading so insertion is free: walking is O(n), hooking up is O(1).