CS101 EXAM 2 QUESTIONS AND ANSWERS

Singly Linked List runtimes for:
insertFront, insertBack, removeFront, removeBack - ANSWER insertFront: 1
insertBack: N
removeFront: 1
removeBack: N

Types of Linked Lists: - ANSWER 1. Singly-linked list
2. Doubly-linked list
3. Circular linked list

Describe a singly-linked list. - ANSWER Each node has a next pointer, but no
previous pointer.

Describe a doubly-linked list. - ANSWER Each node has a next pointer and a
previous pointer.

What is a circularly-linked list? - ANSWER A list that wraps around to the
front. The tail pointer points to the head.

Singly Linked List WITH TAIL runtimes for:
insertFront, insertBack, removeFront, removeBack - ANSWER insertFront: 1
insertBack: 1
removeFront: 1
removeBack: N

Doubly Linked List WITH TAIL runtimes for:
insertFront, insertBack, removeFront, removeBack - ANSWER insertFront: 1
insertBack: 1
removeFront: 1
removeBack: 1
same as DLL circular

, Doubly Linked List CIRCULAR runtimes for:
insertFront, insertBack, removeFront, removeBack - ANSWER insertFront: 1
insertBack: 1
removeFront: 1
removeBack: 1
same as DLL with tail

Even though the worst case in this Amortized Analysis is log(n), the average is -
ANSWER O(1).

Dynamic Array Runtimes B/W/A for: insertFront, insertBack, removeFront,
removeBack - ANSWER insertFront: N/N/N
insertBack: N/1/1
removeFront: N/N/N
removeBack: N/1/1

In a pop-push stack, what is the rule? - ANSWER Last-in, first-out.

Cons of a stack (or queue) for a linked list - ANSWER POP takes longer for a
linked list.

Cons of a stack (or queue) for an array - ANSWER Size limit and chance for
wasted space.

Pros of a stack (or queue) for an array (as apposed to a linked list) - ANSWER
Arrays allocate all at once, so they are faster. Arrays also take up less memory
(linked list has to track data AND pointer).

In a queue, what is the rule? - ANSWER First-in, first-out

What does enqueue(x) do? - ANSWER insert back

What does dequeue() do? - ANSWER removes front

What does peek() do? - ANSWER views front

What are the two options for making a queue? - ANSWER Circular array or
singly-linked list.