Chapter 26 - Implementing Lists, Stacks, Queues, and Priority Queues

Question 1

Describe the list (list as a general data structure).

Answer 1

A list is a popular data structure for storing data in sequential order. You can perform the following operations on most lists:

• Retrieve an element from the list
• Insert a new element into the list
• Delete an element from the list
• Find out how many elements are in the list
• Determine whether an element is in the list
• Check whether the list is empty

Question 2

What is a singly linked list?

Answer 2

A singly linked list contains a pointer to the list’s first node, and each node contains a pointer to the next node sequentially.

Question 3

What is a circular, singly linked list?

Answer 3

A circular, singly linked list is like a singly linked list, except that the pointer of the last node points back to the first node. Note that tail is not needed for circular linked lists. head points to the current node in the list.

Question 4

What is a doubly linked list?

Answer 4

A doubly linked list contains nodes with two pointers. One points to the next node and the other to the previous node. These two pointers are conveniently called a foreward pointer and a backward pointer. Thus, a doubly linked list can be traversed forward and backward. The java.util.LinkedList class is implemented using a doubly linked list.

Question 5

What is a stack?

Answer 5

A stack can be viewed as a special type of list whose elements are accessed, inserted, and deleted only from the end (top).

Question 6

What data structure can you use to implement a stack?

Answer 6

Since the insertion and deletion operations on a stack are made only at the end of the stack, it is more efficient to implement a stack with an array list than with a linked list.

Question 7

What data structure can you use to implement a queue?

Answer 7

Since deletions are made at the beginning of the list, it is more efficient to implement a queue using a linked list than an array list.

Question 8

There are two ways to design the stack and queue classes:

• – Using inheritance: you can define a stack class by extending ArrayList, and a queue class by extending LinkedList
• – Using composition: You can define an array list as a data field in the stack class, and a linked list as a data field in the queue class.

Which method is best, and why?

Answer 8

Both designs are fine, but using composition is better because it enables you to define a completely new stack class and queue class without inheriting the unnecessary and inappropriate methods from the array list and linked list.

Question 9

What data structure can you use to implement a priority queue?

Answer 9

In a priority queue, elements are assigned with priorities. When accessing elements, the element with the highest priority is removed first.
A priority queue can be implemented using a heap, in which the root is the object with the highest priority in the queue.

Question 10

Which of the following operations are supported by a list?

A. Retrieve an element from this list.
B. Insert a new element to this list.
C. Delete an element from this list.
D. Find how many elements are in this list.
E. Find whether an element is in this list.

Answer 10

All are true

Question 11

Which of the following statements are true?

A. MyArrayList and MyLinkedList are two concrete implementations of MyList.
B. MyArrayList is implemented using an array. The array is dynamically created. If the capacity of the array is exceeded, create a new larger array and copy all the elements from the current array to the new array.
C. MyLinkedList is implemented using a linked structure.
D. A linked structure consists of nodes. Each node is dynamically created to hold an element. All the nodes are linked together to form a list.
E. MyAbstractList partially implements MyList.

Answer 11

All are true

Question 12

In the implementation of MyArrayList, which of the following are true?

A. size indicates the number of elements in the list.
B. capacity is the length of the array used to store the elements in the list.
C. capacity is always greater than size.
D. size is reduced by 1 if an element is deleted from the list.
E. capacity is reduced by 1 if an element is deleted from the list.

Answer 12

The correct answer is ABD

Explanation: (C) is not correct because capacity may equal to size.

Question 13

In the implementation of MyArrayList, which of the following are true?

A. size never reduces.
B. capacity never reduces.
C. Inside MyArrayList, a regular array is used to store elements.
D. size is not declared in MyArrayList, but declared in MyAbstractList as protected.
E. If the current capacity equals to size, capacity is doubled when a new element is added to MyArrayList

Answer 13

All but A are true

Question 14

In the implementation of MyLinkedList, which of the following are true?

A. MyLinkedList contains all the methods defined in MyList. Additionally, MyLinkedList defines several new methods that are appropriate for processing a linked list.
B. MyArrayList does not introduce new methods. All the methods in MyArrayList are defined in MyList.
C. You can use a linked list to improve efficiency for adding and remove an element anywhere in a list.
D. You should use an array list if your application does not require adding and remove an element anywhere in a list.

Answer 14

All are true

Question 15

If a linked list is empty, which of following statements are true?
A. head is null.
B. tail is null.
C. head == tail.
D. head < tail.

Answer 15

All but D are true

Question 16

In the implementation of MyLinkedList, which of the following are true?

A. Node is defined as an inner class inside MyLinkedList.
B. Node is defined as a static inner class inside MyLinkedList because it does not reference any instance data fields in MyLinkedList.
C. Node has a property named next that links to the node after this node.
D. Node has a property named element that stores an element.

Answer 16

All are true

Question 17

In the implementation of MyLinkedList, which of the following are true?

A. MyLinkedList has a capacity property.
B. MyLinkedList has the properties named first and last to point to the nodes in a linked list.
C. If a linked list is empty, first is null and last is null.
D. If a linked list contains one element, first points to the node and last is null.
E. last.next is always null.

Answer 17

The correct answer is BCE

Explanation: (D) is partially wrong, last and first points to the same node if a linked list contains one node.

Question 18

ArrayList is more efficient than LinkedList for the following operations:

A. Insert/delete an element in the middle of the list.
B. Insert/delete an element in the beginning of the list.
C. Insert/delete an element at the end of the list.
D. Retrieve an element given the index.

Answer 18

D. Retrieve an element given the index.

Question 19

LinkedList is more efficient than ArrayList for the following operations:

A. Insert/delete an element in the middle of the list.
B. Insert/delete an element in the beginning of the list.
C. Insert/delete an element at the end of the list.
D. Retrieve an element given the index.

Answer 19

A and B

Question 20

Suppose list1 is a MyArrayList and list2 is a MyLinkedList. Both contains 1 million double values. Analyze the following code:

A:
while (list1.size() > 0)
list1.remove(0);

B:
while (list2.size() > 0)
list2.remove(0);

A. Code fragment A runs faster than code fragment B.
B. Code fragment B runs faster than code fragment A.
C. Code fragment A runs as fast as code fragment B.

Answer 20

B. Code fragment B runs faster than code fragment A.

Question 21

Suppose list1 is a MyArrayList and list2 is a MyLinkedList. Both contains 1 million double values. Analyze the following code:

A:
while (list1.size() > 0)
list1.remove(size() - 1);

B:
while (list2.size() > 0)
list2.removeLast();

A. Code fragment A runs faster than code fragment B beacuse the time complexity for code fragment A is O(n) and for B is O(n^2).
B. Code fragment B runs faster than code fragment A.
C. Code fragment A runs as fast as code fragment B beacuse both code fragment A and B have the same time complexity O(n).
D. Both code fragment A and B have the same time complexity O(n), but A runs slightly faster beacuse LinkedList has more overhaed on creating object for each node in the linked list.

Answer 21

D. Both code fragment A and B have the same time complexity O(n), but A runs slightly faster beacuse LinkedList has more overhaed on creating object for each node in the linked list.

Question 22

Suppose list1 is a MyArrayList and list2 is a MyLinkedList. Both contains 1 million double values. Analyze the following code:

A:
for (int i = 0; i

Answer 22

B. Code fragment B runs faster than code fragment A.

Question 23

Suppose list1 is a MyArrayList and list2 is a MyLinkedList. Both contains 1 million double values. Analyze the following code:

A:
for (int i = 0; i

Answer 23

A. Code fragment A is more efficient that code fragment B.

Question 24

Suppose list2 is a MyLinkedList. Analyze the following code:

A:
while (list2.size() > 0)
list2.remove(list2.get(list2.size() - 1));

B:
while (list2.size() > 0)
list2.removeLast();

A. Code fragment A runs faster than code fragment B.
B. Code fragment B runs faster than code fragment A.
C. Code fragment A runs as fast as code fragment B.

Answer 24

The correct answer is B

Explanation: It takes O(n) time to retrieve list2.get(llist2.size() - 1)

Question 25

Which of the following are true?

A. A stack can be viewed as a special type of list, where the elements are accessed, inserted, and deleted only from the end, called the top, of the stack.
B. A queue represents a waiting list. A queue can be viewed as a special type of list, where the elements are inserted into the end (tail) of the queue, and are accessed and deleted from the beginning (head) of the queue.
C. Since the insertion and deletion operations on a stack are made only at the end of the stack, using an array list to implement a stack is more efficient than a linked list.
D. Since deletions are made at the beginning of the list, it is more efficient to implement a queue using a linked list than an array list.

Answer 25

All are true

Question 26

Which data structure is appropriate to store patients in an emergency room?

A. Stack
B. Queue
C. Priority Queue
D. Linked List

Answer 26

C. Priority Queue

Question 27

Which data structure is appropriate to store customers in a clinic for taking flu shots?

A. Stack
B. Queue
C. Priority Queue
D. Array List
E. Linked List

Answer 27

B. Queue

Question 28

Suppose the rule of the party is that the participants who arrive later will leave earlier. Which data structure is appropriate to store the participants?

A. Stack
B. Queue
C. Priority Queue
D. Array List
E. Linked List

Answer 28

A. Stack

Question 29

What are the limitations of the array data type?

Answer 29

Two limitations:

1. once an array is created, its size cannot be altered.
2. it does not support adequate support for insertion and deletion operations.

Question 30

Both MyArrayList and MyLinkedList are used to store a list of objects. Why do we need both types of lists?

Answer 30

MyLinkedList is more efficient for deletion and insertion at the beginning/middle of the list. MyArrayList is more efficient for all other operations.

Question 31

What is the time complexity of the addFirst(e) and removeFirst() methods in MyLinkedList?

Answer 31

O(1);

Question 32

Suppose you need to store a list of elements. If the number of elements in the program is fixed, what data structure should you use? If the number of elements in the program changes, what data structure should you use?

Answer 32

If the number of elements is fixed in the program, using a regular array is more efficient. If the number of elements changes, use ArrayList or LinkedList.