Linked List vs List Big O Flashcards
Append - Linked List
O(1) - same
Append - List
0(1) - same
Pop - Linked List
O(n) - worst
Pop - List
O(1) - better
Prepend - Linked List
O(1) - better
Prepend - List
O(n) = worst
Pop First - Linked List
O(1) - better
Pop First - List
O(n) - worst
Insert - Linked List
O(n) - same
Insert - List
O(n) - same
Remove - Linked List
O(n) - same
Remove - List
O(n) - same
Lookup by Index - Linked List
O(n) - worst
Lookup by Index - List
O(1) - better
Lookup by Value - Linked List
O(n) - same
Lookup by Value - List
O(n) - same
Append Order
1) Create new node
2) Check if there is already a node
3) IF NOT, set head & tail to new node
4) ELSE, set tail.next = new & tail = new
5) Add length += 1
6) return True
Pop Order
1) Check if there is a node
2) self temp & pre variable to head
3) Loop until temp.next is not None
4) In loop set pre to temp (moves pre over)
5) In loop set temp = temp.next to move temp
6) Move tail back to pre
7) Set tail.next = None
8) Decrease length by 1
9) Re-check length
10) set head & tail to None
11) return temp
Prepend Order
1) Create new Node
2) Check if there is a node
3) IF NOT set head & tail to new node
4) ELSE set the new node’s next to head
5) Set head to the new node
6) Increase the length by 1
7) Return True
Pop-First Order
1) Check if there is a node
2) Create temp variable and set to Head
3) Set head to head.next
4) Set the new temp.next to None
5) Decrease by 1
6) Check length again & set tail to none
7) Return temp
Get Order
1) Make sure index is in the range
2) Create temp variable & set to head
3) Create for loop for range of index
4) Set temp to temp.next to move to next node
5) Return Temp
Set order
1) Set temp to get(index)
2) Loop temp through
3) Set temp.value to value
4) Return True in the Loop
5) Return False out the Loop
