LinkedLists

Question 1

What is the runtime of addFront(x) for an SLList?

Answer 1

O(1)

Question 2

What is the runtime of removeFront() for an SLList?

Answer 2

O(1)

Question 3

What is the runtime of addBack(x) for an SLList?

Answer 3

O(1)

Question 4

What is the runtime of removeBack() for an SLList?

Answer 4

O(n)

Question 5

What interfaces does an SLList implement?

Answer 5

Stack

Queue

Question 6

What is the runtime of addFront(x) for a DLList?

Answer 6

O(1)

Question 7

What is the runtime of removeFront() for a DLList?

Answer 7

O(1)

Question 8

What is the runtime of addBack(x) for a DLList?

Answer 8

O(1)

Question 9

What is the runtime of removeBack() for a DLList?

Answer 9

O(1)

Question 10

What interfaces does a DLList implement?

Answer 10

Deque
List
Stack
Queue

Question 11

What is the runtime of get(i) for a DLList?

Answer 11

O(1 + min{i, n-i})

Question 12

What is the runtime of set(i,x) for a DLList?

Answer 12

O(1 + min{i, n-i})

Question 13

What is the runtime of add(i,x) for a DLList?

Answer 13

O(1 + min{i, n-i})

Question 14

What is the runtime of remove(i) for a DLList?

Answer 14

O(1 + min{i, n-i})

Question 15

What is the extra space required by a DLList to store n elements?

Answer 15

O(n)

Each of the n nodes requires two pointers, which take up O(n) space.

Question 16

What is the backing storage of a DLList?

Answer 16

A dummy node

An integer size

Question 17

What is the backing storage of a SLList?

Answer 17

A head node
A tail node
An integer size

Question 18

Pros of a DLList

Answer 18

fairly simple implementation
not amortized time
If you have a fast way to get to the i’th node then the rest of add/remove/get/set is O(1).

Question 19

Cons of a DLList

Answer 19

Uses O(n) space
Random access (get(i), set(i,x)) is not as fast as an array.