template

class LinkedList : public ListInterface

$\{$

private:

Node$*$ headPtr; $//$ Pointer to first node in the chain;

$//($contains the first entry in the list$)$

int itemCount; $//$ Current count of list items

$//$ Locates a specified node in this linked list.

$//$ @pre position is the number of the desired node;

$//$ position $>=1$ and position $<=$ itemCount.

$//$ @post The node is found and a pointer to it is returned.

$//$ @param position The number of the node to locate.

$//$ @return A pointer to the node at the given position.

Node$*$ getNodeAt$($int position$)$ const;

public:

LinkedList$()$;

LinkedList$($const LinkedList& aList$)$;

virtual ~LinkedList$()$;

bool isEmpty$()$ const;

int getLength$()$ const;

bool insert$($int newPosition, const ItemType& newEntry$)$;

bool remove$($int position$)$;

void clear$()$;

$/**$ @throw PrecondViolatedExcep if position $<1$ or

position $>$ getLength$().*/$

ItemType getEntry$($int position$)$ const throw$($PrecondViolatedExcep$)$;

$/**$ @throw PrecondViolatedExcep if position $<1$ or

position $>$ getLength$().*/$

ItemType replace$($int position, const ItemType& newEntry$)$

throw$($PrecondViolatedExcep$)$;

$\}$; $//$ end LinkedList

Question $4(10$ points$)$

Consider a non member function that searches for the position of a given item in a ADT List. Which is the correct implementation among the following answers?

Question $4$ options:

a$)$

template

int find$($const LinkedList & aList, const ItemType& anItem$)$

$\{$

for $($int i $=1$; i $<=$ aList.getLength$()$; i$++)$

$\{$

if $($ anItem $==$ aList$[$i$])$

$\{$

return i;

$\}//$ end if

$\}//$ end for

return $-1$;

$\}$

b$)$

template

int find$($const LinkedList & aList, const ItemType& anItem$)$

$\{$

node$*$ curPtr $=$ headPtr;

int i$=1$;

while $($curPtr$!=$NULL && i$<=$aList.getLength$())$

$\{$

if$($curPtr$->$getItem$()==$anItem$)$

return i;

$++$i;

curPtr$=$curPtr$->$getNext$()$;

$\}$

return $-1$;

$\}$

c$)$

template

int find$($const LinkedList & aList, const ItemType& anItem$)$

$\{$

node$*$ curPtr $=$ aList.headPtr;

int i$=1$;

while $($curPtr$!=$NULL && i$<=$itermCount$)$

$\{$

if$($curPtr$->$getItem$()==$anItem$)$

return i;

$++$i;

curPtr$=$curPtr$->$getNext$()$;

$\}$

return $-1$;

$\}$

d$)$

template

int find$($const LinkedList & aList, const ItemType& anItem$)$

$\{$

for $($int i $=1$; i $<=$ aList.getLength$()$; i$++)$

$\{$

if $($ anItem $==$ aList.getEntry$($i$))$

return i;

$\}//$ end for

return $-1$;

$\}$