Question 1

Suppose we maintain a linked list of length n in sorted order. What would be the big-Oh notation for the add operation?

Accepted Answer

To add an element to a sorted linked list, you need to find the correct position to maintain the order, which requires traversing the list. This takes O(n) time in the worst case.

Question 2

Suppose we maintain a linked list of length n in sorted order. What would be the big-Oh notation for printing out those elements that occur exactly once in the list?

Accepted Answer

To print elements that occur exactly once, we need to traverse the entire list, which takes O(n) time.

Question 3

If we want a create a doubly-linked list data structure so that we can move from a node to the next node as well as to a previous node, we need to add a previous reference to the Node class. Each such DNode (doubly-linked Node) will have a data portion and two DNode references, next and previous. How many references need to be updated when we remove a node from the middle of such a list? Consider the neighboring nodes.

Accepted Answer

When we remove a node from the middle of a doubly-linked list, we need to update the previous and next references of the neighboring nodes. Therefore, we need to update two references.

Question 4

Suppose we maintain two linked lists of length n in random element order. What would be the big-Oh notation for the creating a third list that includes only elements common to both lists, without sorting the first two lists?

Accepted Answer

To find common elements between two unsorted linked lists, you need to compare each element of the first list with each element of the second list, resulting in a time complexity of O(n^2).

Question 5

What type of access does the use of an iterator with a LinkedList provide for its elements?

Accepted Answer

An iterator provides sequential access to the elements of a LinkedList, allowing traversal from one element to the next in order.

Question 6

A doubly-linked list requires that each node maintain two references, one to the next node and one to the previous node. Which of the following statements about a doubly-linked list is NOT correct?

Accepted Answer

A doubly-linked list requires that each node maintain a reference to the previous node and a reference to the next node. To remove a node in the middle of the list, the node's previous node's next reference must be updated to point to the node following the one being removed. To add a node in the middle of the list, you must update the next reference of the node after which the new node will be added. If a node's next reference is null, it is at the end of the list. However, to remove a node in the middle of the list, the previous node's previous reference does not need to be updated.

Question 7

Suppose we maintain a linked list of length n in random element order. What would be the big-Oh notation for an algorithm that prints each list element and the number of times it occurs in the list (without sorting the list)?

Accepted Answer

To print each element and count its occurrences without sorting, you would need to traverse the list for each element to count its occurrences, leading to a time complexity of O(n^2).

Question 8

Suppose we maintain a linked list of length n in random element order. What would be the big-Oh notation for printing out those elements which occur exactly once in the list (without sorting the list)?

Accepted Answer

To find elements that occur exactly once, we need to check each element against all others, leading to a time complexity of O(n^2).

Question 9

Adding or removing an element at an arbitrary iterator position in a singly linked list of length n takes ____ time.

Accepted Answer

Adding or removing an element at an arbitrary iterator position in a singly linked list of length n takes O(1) time because it only requires updating the pointers of the nodes around the insertion or deletion point.

Question 10

Which of the following algorithms would be efficiently executed on a LinkedList?

Accepted Answer

The answer of Which of the following algorithms would be...

Question 11

Suppose we maintain two linked lists of length n in sorted order. What would be the big-Oh notation for the creating a third list, which included only elements common to both lists?

Accepted Answer

To find common elements in two sorted linked lists, you can traverse both lists simultaneously, which takes linear time, O(n).

Question 12

If we want a create a doubly-linked list data structure so that we can move from a node to the next node as well as to a previous node we need to add a previous reference to the Node class. Each such DNode (doubly-linked Node) will have a data portion and two DNode references, next and previous. How many references need to be updated when we remove a node from the beginning of a list with many nodes? Consider the first reference and neighboring node(s).

Accepted Answer

When we remove a node from the beginning of a doubly-linked list, we need to update two references: the "next" reference of the previous node (which will now be the new head of the list) and the "previous" reference of the new head (which will be null because it has no previous node). We do not need to update the reference of the removed node itself since it is no longer in the list. Therefore, the correct choice is B.

Question 13

Which of the following actions must be taken to remove a node X from the middle of a doubly-linked list?
I Update the next reference in the node before X
II Update the previous reference in the node after X
III Update the list's first reference

Accepted Answer

When removing a node X from the middle of a doubly-linked list, we need to update the next reference in the node before X to point to the node after X (which becomes the new next node), and update the previous reference in the node after X to point to the node before X (which becomes the new previous node). Therefore, both actions I and II are necessary. Updating the list's first reference (action III) is only necessary if X happens to be the first node of the list, but it is not necessary in the general case. Therefore, the correct choice is C.

Question 14

Which of the following operations is least efficient in a LinkedList?

Accepted Answer

LinkedLists do not support efficient random access because they require traversal from the head to the desired position, making it an O(n) operation.

Question 15

Which of the following actions must be taken to add a node X at the end of a doubly-linked list?
I Update the next reference in the node before the position where X will be placed
II Update the previous reference in the node before the position where X will be placed
III Update the list's last reference

Accepted Answer

To add a node X at the end of a doubly-linked list, we need to update the next reference in the last node of the list to point to the new node X and update the previous reference in the new node X to point to the previous last node. Additionally, we need to update the list's last reference to point to the new node X. Therefore, options I and III are correct. Option II is not required for adding a node at the end of the list.

Question 16

Using the textbook's implementation of a linked list, what is the purpose of declaring the Node class to be a static inner class?

Accepted Answer

Declaring the Node class as a static inner class prevents storage of an outer-class reference that is not needed. Since each Node object only needs to know about the next Node in the list, there is no need to store a reference to the LinkedList object that contains it. This can save memory and reduce complexity in the code. Option A and D suggest the creation of an outer-class reference, which is not necessary, and Option B does not accurately describe the purpose of declaring the Node class as a static inner class.

Question 17

Which of the following actions must be taken to add a node X at the beginning of a doubly-linked list?
I Update the next reference in the node before the position where X will be placed
II Update the previous reference in the node after the position where X will be placed
III Update the list's first reference

Accepted Answer

To add a node at the beginning of a doubly-linked list, you must update the previous reference in the current first node (II) and update the list's first reference to point to the new node (III).

Question 18

Which of the following actions must be taken to add a node X into the middle of a doubly-linked list?
I Update the next reference in the node before the position where X will be placed
II Update the previous reference in the node after the position where X will be placed
III Update the list's first reference

Accepted Answer

To insert a node in the middle of a doubly-linked list, you must update the next reference of the node before the insertion point and the previous reference of the node after the insertion point.

Question 19

Using the textbook's implementation of a linked list, why is the LinkedListIterator inner class NOT declared as an inner static class?

Accepted Answer

The LinkedListIterator class needs to access the instance variables of the LinkedList class, such as the head of the list, to iterate through the list. Making it a non-static inner class allows it direct access to the LinkedList's instance variables. Static inner classes, on the other hand, do not have access to the instance variables of the outer class.

Question 20

In a linked list data structure, when does the reference to the first node need to be updated?
I inserting into an empty list
II deleting from a list with one node
III deleting an inner node

Accepted Answer

The reference to the first node needs to be updated in scenarios I and II. In scenario I, when inserting into an empty list, the first node reference needs to be updated to the newly inserted node. In scenario II, when deleting from a list with one node, the first node reference needs to be updated to null as there are no nodes left in the list. However, in scenario III where an inner node is being deleted, the first node reference does not need to be updated as only the reference of the previous node needs to be updated to the next node.

Quiz 16: Basic Data Structures