# PrintLots

## Problem

Today, I finished the problem 3.2. The question is following:

You are given a linked list, L, and another linked list, P, containing integers sorted in ascending order. The operation PrintLots(L,P) will print the elements in L that are in positions specified by P. For instance, if P = 1,3,4,6, the first, third, fourth, and sixth elements in L are printed. Write the procedure PrintLots(L,P). You should use the basic list operations. What is the running time of your procedure?

## Solution

 ``` 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50``` ``` void printLots(List L, List P) { Pos dummyP, dummyL; // creates dummy nodes to traverse the list int i = 0, idx, outofelement; dummyP = P->Next; dummyL = L->Next; while (dummyP != NULL) { idx = dummyP->Element; if (idx >= 0) { // if the idx is larger or equal to where the dummyL currently is // we don't want to reset the dummyL to the very beginning of // the list L again to redo the traverse. if (idx < i) { dummyL = L->Next; i = 0; } for(; i < idx; i++) { if (dummyL->Next != NULL) { dummyL = dummyL->Next; } else { outofelement = 1; break; } } if (outofelement == 1) { printf("No element in position %d, ", idx); } else{ printf("%d, ", dummyL->Element); } } else { exit(EXIT_FAILURE); } outofelement = 0; dummyP = dummyP->Next; } } ```

The problem isn't hard to solve. However, to get things right, I need to develop several test cases. Let's develop a solution that can handle more general situation. In other words, linked list, P, doesn't necessarily contain integers sorted in ascending order. Here are test cases I developed:

```L: 23, 44, 45, 57, 89, -1

P:  1, 3, 4, 5          <--- normal case
1, 3, 4, 6          <--- there is no sixth element in L
1, 3, 4, 6, 7       <--- there is no sixth, seventh element in L
6, 7, 3, 1          <--- there is no sixth, seventh element in L, but have third, first element
6, 2, 7, 1          <--- a no element (6th) followed by a existing element (2nd)
-9, 1, 3, 4          <--- negative integer from P appears at the beginning
1, 2, 4, -10        <--- negative integer from P appears at the end
```

The code presented above handles all these different situations. In addition, if the integers presented in P are actually in ascending order, we want to take advantage of this piece of information. That's why we check if (idx < i). We don't want to reset the traverse ptr (i.e. dummyL) every single time. In other words, if the number in P is actually ascending, we want to move the traver ptr from its current pos instead of reset.