Please help me answer these questions: 1, Why do the linked stack and queue impl

Question

Please help me answer these questions:

1, Why do the linked stack and queue implementations not include iterators, as in the linked list classes of Chapter 17? Are there cases when a stack or queue might need to be traversed privately, even if access cannot be provided publicly? If so, should an iterator be used for these cases?

2,Discuss any assumptions that have been made regarding sorting or searching with duplicate items in a list. How would the searching and sorting algorithms presented in this chapter handle duplicates?

3,Do some thinking about alternate searching methods to sequential and binary search. What other search techniques exist? How do they compare with sequential and binary search in terms of performance?

Explanation / Answer

1)

            For a linked list stack and queue, iterator is not needed because the implementation of stack requires the pointer of the last node for push or pop() operations, (last pointer is like top in normal stack)

Similarly for queue front and rear are stored in head and last node of the linked to operate the queue.

By declaring the subclass Node to be private we restrict access to methods within the enclosing class. One characteristic of a private nested class is that its instance variables can be directly accessed from within the enclosing class, but nowhere else, so there is no need to declare them public or private.

Note : A nested class that is not static is known as an inner class, so technically our Node classes are inner classes, though the ones that are not generic could be static.

2)

Here I consider Insertion sort for handling duplicates:

Insertion Sort:

To sort unordered list of elements, we remove its entries one at a time and then insert each of them into a sorted part (initially empty):

void insertionSort(int[] ar)

{

   for (int i=1; i ? ar.length; i++)

   {

      int index = ar[i]; int j = i;

      while (j > 0 && ar[j-1] > index)

      {

           ar[j] = ar[j-1];

           j--;

      }

      ar[j] = index;

} }

Example: We color a sorted part in green, and an unsorted part in black. Here is an insertion sort step by step. We take an element from unsorted part and compare it with elements in sorted part, moving form right to left.

29, 20, 73, 34, 64

29, 20, 73, 34, 64

20, 29, 73, 34, 64

20, 29, 73, 34, 64

20, 29, 34, 73, 64

20, 29, 34, 64, 73

Let us compute the worst-time complexity of the insertion sort. In sorting the most expensive part is a comparison of two elements. Surely that is a dominant factor in the running time. We will calculate the number of comparisons of an array of N elements:

we need 0 comparisons to insert the first element

we need 1 comparison to insert the second element

we need 2 comparisons to insert the third element

...

we need (N-1) comparisons (at most) to insert the last element

Totally,

1 + 2 + 3 + ... + (N-1) = O(n2)

The worst-case runtime complexity is O(n2).What is the best-case runtime complexity? O(n). The advantage of insertion sort comparing it to the previous two sorting algorithm is that insertion sort runs in linear time on nearly sorted data.

O(n log n) algorithms

3)

Sequential search takes O(n) comparisons in worst case but can be operated on any list (no need to be sorted)

Binary search takes O(log2 n) comparisons in worst case but can be operated only on sorted list.

We have another technique is hashing but that is not directly related to search. but a faster way to search.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

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