Chapter 17, Problem 1TF

a.

Every node in a linked list has two components: one to store the relevant information and one to store the address. Hence, the given statement is “True”.

Program Plan Intro

A linked list is a collection of components called nodes. Every node except the last node contains the address of the next node and it has two components: one to store the relevant information or data and one to store the address, called the link, of the next node in the list. The address of the first node in the list is stored in a separate location called the head or first.

Program Description Answer

Every node in a linked list has two components: one to store the relevant information and one to store the address. Hence, the given statement is “True”.

Explanation of Solution

Every node in a linked list has two components: one to store the relevant information and one to store the address.

b.

In a linked list, the order of the elements is not determined by the order in which the nodes were created to store the elements. Hence, the given statement is “False”.

Program Plan Intro

A linked list is a collection of components called nodes. Every node except the last node contains the address of the next node and it has two components: one to store the relevant information or data and one to store the address, called the link, of the next node in the list. The address of the first node in the list is stored in a separate location called the head or first.

Program Description Answer

In a linked list, the order of the elements is not determined by the order in which the nodes were created to store the elements. Hence, the given statement is “False”.

Explanation of Solution

In a linked list, the order of the elements is not determined by the order in which the nodes were created to store the elements but by the order of the pointers or links in the list.

c.

In a linked list, memory allocated for the nodes may not necessarily be sequential. Hence, the given statement is “False”.

Program Plan Intro

A linked list is a collection of components called nodes. Every node except the last node contains the address of the next node and it has two components: one to store the relevant information or data and one to store the address, called the link, of the next node in the list. The address of the first node in the list is stored in a separate location called the head or first.

Program Description Answer

In a linked list, memory allocated for the nodes may not necessarily be sequential. Hence, the given statement is “False”.

Explanation of Solution

In a linked list, memory allocated for the nodes may not necessarily be sequential, as memory is dynamically allocated during the node creation using pointer mechanism. A linked list is a dynamic data structure.

d.

In a linked list, the link field of the last node does not point to itself. Hence, the given statement is “False”.

Program Plan Intro

A linked list is a collection of components called nodes. Every node except the last node contains the address of the next node and it has two components: one to store the relevant information or data and one to store the address, called the link, of the next node in the list. The address of the first node in the list is stored in a separate location called the head or first.

Program Description Answer

In a linked list, the link field of the last node does not point to itself. Hence, the given statement is “False”.

Explanation of Solution

In a linked list, the link field of the last node does not point to itself but to a null pointer (nullptr).

e.

Suppose the nodes of a linked list are in the usual info-link form and current points to a node of the linked list. Then current = current.link; does not advance current to the next node in the linked list. Hence, the given statement is “False”.

Program Plan Intro

A linked list is a collection of components called nodes. Every node except the last node contains the address of the next node and it has two components: one to store the relevant information or data and one to store the address, called the link, of the next node in the list. The address of the first node in the list is stored in a separate location called the head or first.

Program Description Answer

Suppose the nodes of a linked list are in the usual info-link form and current points to a node of the linked list. Then current = current.link; does not advance current to the next node in the linked list. Hence, the given statement is “False”.

Explanation of Solution

Suppose the nodes of a linked list are in the usual info-link form and current points to a node of the linked list. Then current = current->link; advances current to the next node in the linked list. Since link and current both are pointers the member of the structure pointed to by the pointer variable current is accessed using the arrow notation -> and not the dot operator.

f.

To insert a new item in a linked list, create a node, store the new item in the node, and insert the node in the linked list..Hence, the given statement is “True”.

Program Plan Intro

While building a linked list initially the list is empty, and the pointerfirst must be initialized to nullptr. The steps of insertion are -firstly, initialize first to nullptr. Then for each item in the list - create the new node, newNode, store the item in newNode, insert newNode before first and update the value of the pointer first.

Program Description Answer

To insert a new item in a linked list, create a node, store the new item in the node, and insert the node in the linked list..Hence, the given statement is “True”.

Explanation of Solution

To insert a new item in a linked list, create a node, store the new item in the node, and insert the node in the linked list.

g.

To build a linked list forward, the new node is inserted at the end of the list. Hence, the given statement is “True”.

Program Plan Intro

When building a linked list forward, a new node is always inserted at the end of the linked list, while building backwards, new node is always inserted at the beginning of the list.

Program Description Answer

To build a linked list forward, the new node is inserted at the end of the list. Hence, the given statement is “True”.

Explanation of Solution

When building a linked list forward, a new node is always inserted at the end of the linked list, while building backwards, new node is always inserted at the beginning of the list.

h.

A single linked list cannot be traversed in either direction. Hence, the given statement is “False”.

Program Plan Intro

A single linked list cannot be traversed in either direction but only in forward direction.

Program Description Answer

A single linked list cannot be traversed in either direction. Hence, the given statement is “False”.

Explanation of Solution

A single linked list cannot be traversed in either direction but only in forward direction. A doubly linked list can be traversed in either direction as it has links pointing in either direction stored at each node.

i.

In a linked list, nodes are not always inserted either at the beginning or at the end because a linked list is a random-access data structure. Hence, the given statement is “False”.

Program Plan Intro

A linked list is a collection of components called nodes. Every node except the last node contains the address of the next node and it has two components: one to store the relevant information or data and one to store the address, called the link, of the next node in the list. The address of the first node in the list is stored in a separate location called the head or first.

Program Description Answer

In a linked list, nodes are not always inserted either at the beginning or at the end because a linked list is a random-access data structure. Hence, the given statement is “False”.

Explanation of Solution

In a linked list, nodes are not always inserted either at the beginning or at the end because a linked list is a random-access data structure. Hence nodes can be inserted anywhere in the linked list.

j.

The head pointer of a linked list should not be used to traverse the list. Hence, the given statement is “True”.

Program Plan Intro

A linked list is a collection of components called nodes. Every node except the last node contains the address of the next node and it has two components: one to store the relevant information or data and one to store the address, called the link, of the next node in the list. The address of the first node in the list is stored in a separate location called the head or first.

Program Description Answer

The head pointer of a linked list should not be used to traverse the list. Hence, the given statement is “True”.

Explanation of Solution

The head pointer of a linked list should not be used to traverse the list. Because if that is done we will lose the rest of the linked list which has already been traversed. Linked list is a dynamic data structure and the nodes are not stored in contiguous memory locations.

k.

The two most common operations on iterators are ++ and * (the dereferencing operator). Hence, the given statement is “True”.

Program Plan Intro

The two most common operations on iterators are ++ (the increment operator) and * (the dereferencing operator). The increment operator advances the iterator to the next node in the list, and the dereferencing operator returns the info of the current node.

Program Description Answer

The two most common operations on iterators are ++ and * (the dereferencing operator). Hence, the given statement is “True”.

Explanation of Solution

The two most common operations on iterators are ++ (the increment operator) and * (the dereferencing operator). The increment operator advances the iterator to the next node in the list, and the dereferencing operator returns the info of the current node.

l.

The function initializeList of the class linkedListType initializes the list not only by setting the pointers first and last to nullptr, but also the count variable to 0. Hence, the given statement is “False”.

Program Plan Intro

The function initializeList of the class linkedListType initializes the list not only by setting the pointers first and last to nullptr, but also the count variable to 0.

Program Description Answer

The function initializeList of the class linkedListType initializes the list not only by setting the pointers first and last to nullptr, but also the count variable to 0. Hence, the given statement is “False”.

Explanation of Solution

The function initializeList of the class linkedListType initializes the list not only by setting the pointers first and last to nullptr, but also the count variable to 0.

m.

The function search of the class unorderedLinkedList searches the entire linked list sequentially until the item is found, while the function search of the class ordered-LinkedList searches the list using a mechanism which is not exactly binary search algorithm. Hence, the given statement is“False”.

Program Plan Intro

In case of ordered-LinkedList because the list is sorted, we start the search at the first node in the list and stop the search as soon as we find a node in the list with info greater than or equal to the search item or when we have searched the entire list.

Program Description Answer

The function search of the class unorderedLinkedList searches the entire linked list sequentially until the item is found, while the function search of the class ordered-LinkedList searches the list using a mechanism which is not exactly binary search algorithm. Hence, the given statement is“False”.

Explanation of Solution

In case of ordered-LinkedList because the list is sorted, we start the search at the first node in the list and stop the search as soon as we find a node in the list with info greater than or equal to the search item or when we have searched the entire list. This is not the binary search algorithm.

n.

A doubly linked list can be traversed in either direction. Hence, the given statement is “True”.

Program Plan Intro

A single linked list cannot be traversed in either direction but only in forward direction. A doubly linked list can be traversed in either direction as it has links pointing in either direction stored at each node.

Program Description Answer

A doubly linked list can be traversed in either direction. Hence, the given statement is “True”.

Explanation of Solution

A single linked list cannot be traversed in either direction but only in forward direction. A doubly linked list can be traversed in either direction as it has links pointing in either direction stored at each node.