Data Structures Computer Science

List ADT:

3. Write down detailed pseudo-code implementing the procedure of deleting every third position of an input list, i.e. positions 1, 4, 7, 10, 13, 16, ... . Make sure your implementation properly treats lists of any length and the empty list as well. In your implementation you are only allowed to use the basic operations of the List ADT, i.e. FIRST(L), END(L), RETRIEVE(p, L), LOCATE(x, L), NEXT(p, L), PREVIOUS(p, L), INSERT(x, p, L), DELETE(p, L), MAKENULL(L). 1. INSERT(x,p, L). Insert x at position p in list L, moving elements at p and following positions to the next higher position. That is, if L is 21, 22, . . . ,an, then L becomes aj, A2,. .. ,ap-1,X, ap, . . . ,Qn. If p is END(L), then L becomes 21, 22, ..., an, x. If list L has no position p, the result is undefined. 2. LOCATE(x, L). This function returns the position of x on list L. If x appears more than once, then the position of the first occurrence is returned. If x does not appear at all, then END(L) is returned. 3. RETRIEVE(p, L). This function returns the element at position p on list L. The result is undefined if p = END(L) or if L has no position p. Note that the elements must be of a type that can be returned by a function if RETRIEVE is used. In practice, however, we can always modify RETRIEVE to return a pointer to an object of type elementtype. 4. DELETE(p, L). Delete the element at position p of list L. If L is aj, a2,... an, then L becomes a1, A2, ... Ap- 1, 2p+1, ... An. The result is undefined if L has no position p or if p = END(L). 5. NEXT(p, L) and PREVIOUS(p, L) return the positions following and preceding position p on list L. If p is the last position on L, then NEXT(p, L) = END(L). NEXT is undefined if p is END(L). PREVIOUS is undefined if p is 1. Both functions are undefined if L has no position p. 6. MAKENULL(L). This function causes L to become an empty list and returns position END(L). 7. FIRST(L). This function returns the first position on list L. If L is empty, the position returned is END(L). 8. PRINTLIST(L). Print the elements of L in the order of occurrence