4.1 Given the following list of integers. 3, 9, 2, 15, -5, 18, 7, 5, 8 EA.6. Sup

Question

4.1 Given the following list of integers.

3, 9, 2, 15, -5, 18, 7, 5, 8

EA.6. Suppose you are given a list that supports only the operations append, remove, and enumerate, as described in the first three rows of Table 4.1. Give an algorithm describing how you would perform each of the following operations in terms of the given operations (a) Empty a list (i.e., remove all the entries) (b) Remove all occurrences of a given item from a list (c) Obtain the size (i.e., the number of entries) of a list d) Search for a given item in the list, returning true or false depending on whether the item is found or not

Explanation / Answer

a) Empty List:
en = List.enumerate();
while (en.hasNext()) {
     list.remove(0); //always remove the first item
     en.next();
}
Complexity: O(n)

b) remove particular item(x)
en = List.enumerate();
count = 0;
while (en.hasNext()) {
     k = en.next();
     if (k == x)
         list.remove(count);
    else
        count ++;
}
Complexity: O(n)

c) size of list:
en = List.enumerate();
count = 0;
while (en.hasNext()) {
     en.next();
     count ++;
}
Complexity: O(n)

d) search a particular item (x):
en = List.enumerate();
while (en.hasNext()) {
     k = en.next();
     if (k == x)
         return true;
}
return false;
Complexity: O(n)

Related Questions

Navigate

• Browse (All)
• Browse 4
• Subjects

---

---

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