Linked List vs List Big O

Question 1

Append - Linked List

Answer 1

O(1) - same

Question 2

Append - List

Answer 2

0(1) - same

Question 3

Pop - Linked List

Answer 3

O(n) - worst

Question 4

Pop - List

Answer 4

O(1) - better

Question 5

Prepend - Linked List

Answer 5

O(1) - better

Question 6

Prepend - List

Answer 6

O(n) = worst

Question 7

Pop First - Linked List

Answer 7

O(1) - better

Question 8

Pop First - List

Answer 8

O(n) - worst

Question 9

Insert - Linked List

Answer 9

O(n) - same

Question 10

Insert - List

Answer 10

O(n) - same

Question 11

Remove - Linked List

Answer 11

O(n) - same

Question 12

Remove - List

Answer 12

O(n) - same

Question 13

Lookup by Index - Linked List

Answer 13

O(n) - worst

Question 14

Lookup by Index - List

Answer 14

O(1) - better

Question 15

Lookup by Value - Linked List

Answer 15

O(n) - same

Question 16

Lookup by Value - List

Answer 16

O(n) - same

Question 17

Append Order

Answer 17

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

Question 18

Pop Order

Answer 18

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

Question 19

Prepend Order

Answer 19

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

Question 20

Pop-First Order

Answer 20

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

Question 21

Get Order

Answer 21

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

Question 22

Set order

Answer 22

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