QUESTION 1 Briefly compare a doubly linked list to a single linked list, discuss

Question

QUESTION 1

Briefly compare a doubly linked list to a single linked list, discussing issues of memory conservation and node removal.

QUESTION 2

Here is a function that uses a for loop. Write a recursive function that does the same thing. Be sure you write the correct number of copies of the cheer, “Hip, Hip, Hurray!”.

QUESTION 3

Explain why a LinkedList object might make a good data member in the linked list implementation of a stack

QUESTION 4

Compare function templates to class templates, noting similarities and differences

Explanation / Answer

Q1.

A singly linked list maintains a single node to keep track of the next node, where as a double linked list maintains 2 nodes , one for next node and one for previous node.

Interms of memory, doubly linked list takes more memory since it has to keep track of previous node as well.

Interms of node removal, when we remove a node in singly linked list, we will link previous node of the node to next node of the current node
In doubly linked list, inaddition to linking previous node with next node, we should also link next node with previous node. Both singly linked list and doubly linked list has same complexity in node removal

Q2.

void rec_cheers(int n){
if(n==0){
cout << "Hurray!" << endl;
return;
}
cout<<"Hip, ";
rec_cheers(n-1);
}

Q3.

LinkedList object makes a really good data member in linked list implementatoin of stack. Because, in stack, we perform push and pop operations, which involve inserting and deleting a node at only one end. Since LinkedList can insert and delete a node in constant time, it is a very good choice.

Q4.

Function templates lets us create generic functions that are parameterized on types and constant values. A function in a class template also is considered a function template. These are useful to implement generic functions like add , substract, which can take generic parameters

Similar to function templates, class templates are useful when a class has data members which are independent of data type. It is very useful to implement classes like LinkedList, Stack, whose node datatypes are not known in advance.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.