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

answer 1->

answer 2->

iter_cheers(n-1);

return ;

}

answer 3->

The major problem with the stack implemented using array is, it works only for fixed number of data values. That means the amount of data must be specified at the beginning of the implementation itself. Stack implemented using array is not suitable, when we don't know the size of data which we are going to use. A stack data structure can be implemented by using linked list data structure. The stack implemented using linked list can work for unlimited number of values. That means, stack implemented using linked list works for variable size of data. So, there is no need to fix the size at the beginning of the implementation. The Stack implemented using linked list can organize as many data values as we want.

In linked list implementation of a stack, every new element is inserted as top element. That means every newly inserted element is pointed by top. Whenever we want to remove an element from the stack, simply remove the node which is pointed by top by moving top to its next node in the list. The next field of the first element must be always null.

answer 4->

A function template works in a similar to a normal function, with one key difference.

A single function template can work with different data types at once but, a single normal function can only work with one set of data types.

Normally, if you need to perform identical operations on two or more types of data, you use function overloading to create two functions with the required function declaration.

However, a better approach would be to use function templates because you can perform the same task writing less and maintainable code.

Like function templates, you can also create class templates for generic class operations.

Sometimes, you need a class implementation that is same for all classes, only the data types used are different.

Normally, you would need to create a different class for each data type OR create different member variables and functions within a single class.

This will unnecessarily bloat your code base and will be hard to maintain, as a change is one class/function should be performed on all classes/functions.

However, class templates make it easy to reuse the same code for all data types.

Singly linked list Doubly linked list A singly linked list is a linked list where the node contains some data and a pointer to the next node in the list A doubly linked list is complex type of linked list where the node contains some data and a pointer to the next as well as the previous node in the list It allows traversal only in one way It allows a two way traversal It uses less memory per node (single pointer) It uses more memory per node(two pointers) Complexity of insertion and deletion at a known position is O(n) Complexity of insertion and deletion at a known position is O(1) If we need to save memory and searching is not required, we use singly linked list If we need better performance while searching and memory is not a limitation, we go for doubly linked list If we know that an element is located towards the end section, eg. ‘zebra’ still we need to begin from start and traverse the whole list If we know that an element is located towards the end section e.g. ’zebra’ we can start searching from the Back. Singly linked list can mostly be used for stacks They can be used to implement stacks, heaps, binary trees.

Related Questions

Navigate

• Browse (All)
• Browse Q
• Subjects

---

---

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