Question

C++ ONLY!

Implement the find function for the List class. It takes a string as an argument and returns an iterator to a matching node. If no matching node, it returns a null iterator.

#include <iostream>
#include <cstddef>
#include <string>

using Item = std::string;

class List {
private:

class ListNode {
public:
Item item;
ListNode * next;
ListNode(Item i, ListNode *n=nullptr) {
item = i;
next = n;
}
};
  
ListNode * head;
ListNode * tail;
  
public:
class iterator {
ListNode *node;
public:
iterator(ListNode *n = nullptr) {
node = n;
}
Item& getItem() { return node->item; }
void next() { node = node->next; }
bool end() { return node==nullptr; }

friend class List;
};

public:
List() {
// list is empty
head = nullptr;
tail = nullptr;
}

bool empty() {
return head==nullptr;
}
  
// Only declared, here, implemented
// in List.cpp
void append(Item a);
bool remove (Item &copy);

void insertAfter(iterator, Item);
void removeAfter(iterator, Item&);

iterator begin() {
return iterator(head);
}

iterator find(Item);
};

void List::append(Item a) {
ListNode *node = new ListNode(a);
if ( head == nullptr ) {
// empty list
head = node;
tail = node;
} else {
tail->next = node;
tail = node;
}
}

bool List::remove(Item &copy)
{
if (!empty()) {
copy = head->item;
ListNode *tmp = head->next;
delete head;
head = tmp;
if (head==nullptr)
tail = nullptr;
return true;
}
return false;
}

void List::insertAfter(iterator it, Item item)
{
if (it.node == nullptr)
{
// insert at head
ListNode *tmp = new ListNode(item,head);
// if list is empty, set tail to new node
if (tail==nullptr) {
   tail = tmp;
}
// set head to new node
head = tmp;
}
else
{
ListNode *tmp = new ListNode(item,it.node->next);  
it.node->next = tmp;
// could be a new tail, if so update tail
if (tail==it.node) {
   tail = tmp;
}   
}
}

void List::removeAfter(iterator it, Item& item)
{
// emtpy list or at tail, just return
if (it.node == tail) return;
  
if (it.node == nullptr)
{
ListNode * tmp = head;
head = head->next;
delete tmp;
if (head==nullptr)
   tail = nullptr;
}
else
{
ListNode *tmp = it.node->next;
it.node->next = tmp->next;
delete tmp;
// could be that it.node is the new nullptr
if (it.node->next == nullptr)
   tail = it.node;
}
}

List::iterator List::find(Item item)
{
//YOUR CODE HERE

return iterator();
}

int main()
{
List l;
l.append("one");
l.append("two");
l.append("three");
l.append("four");

auto it = l.find("one");
if (!it.end())
std::cout << "Should be one: " << it.getItem() << std::endl;
else
std::cout << "Iterator should not have been null." << std::endl;
  
auto no_it = l.find("zero");
if (no_it.end())
std::cout << "As expected, zero not found." << std::endl;
else
std::cout << "Oops! should not have found zero." << std::endl;
  
return 0;
}

Answer 1

If you have any doubts, please give me comment...

#include <iostream>

#include <cstddef>

#include <string>

using Item = std::string;

class List

{

private:

    class ListNode

    {

    public:

        Item item;

        ListNode *next;

        ListNode(Item i, ListNode *n = nullptr)

        {

            item = i;

            next = n;

        }

    };

    ListNode *head;

    ListNode *tail;

public:

    class iterator

    {

        ListNode *node;

    public:

        iterator(ListNode *n = nullptr)

        {

            node = n;

        }

        Item &getItem() { return node->item; }

        void next() { node = node->next; }

        bool end() { return node == nullptr; }

        friend class List;

    };

public:

    List()

    {

        // list is empty

        head = nullptr;

        tail = nullptr;

    }

    bool empty()

    {

        return head == nullptr;

    }

    // Only declared, here, implemented

    // in List.cpp

    void append(Item a);

    bool remove(Item &copy);

    void insertAfter(iterator, Item);

    void removeAfter(iterator, Item &);

    iterator begin()

    {

        return iterator(head);

    }

    iterator find(Item);

};

void List::append(Item a)

{

    ListNode *node = new ListNode(a);

    if (head == nullptr)

    {

        // empty list

        head = node;

        tail = node;

    }

    else

    {

        tail->next = node;

        tail = node;

    }

}

bool List::remove(Item &copy)

{

    if (!empty())

    {

        copy = head->item;

        ListNode *tmp = head->next;

        delete head;

        head = tmp;

        if (head == nullptr)

            tail = nullptr;

        return true;

    }

    return false;

}

void List::insertAfter(iterator it, Item item)

{

    if (it.node == nullptr)

    {

        // insert at head

        ListNode *tmp = new ListNode(item, head);

        // if list is empty, set tail to new node

        if (tail == nullptr)

        {

            tail = tmp;

        }

        // set head to new node

        head = tmp;

    }

    else

    {

        ListNode *tmp = new ListNode(item, it.node->next);

        it.node->next = tmp;

        // could be a new tail, if so update tail

        if (tail == it.node)

        {

            tail = tmp;

        }

    }

}

void List::removeAfter(iterator it, Item &item)

{

    // emtpy list or at tail, just return

    if (it.node == tail)

        return;

    if (it.node == nullptr)

    {

        ListNode *tmp = head;

        head = head->next;

        delete tmp;

        if (head == nullptr)

            tail = nullptr;

    }

    else

    {

        ListNode *tmp = it.node->next;

        it.node->next = tmp->next;

        delete tmp;

        // could be that it.node is the new nullptr

        if (it.node->next == nullptr)

            tail = it.node;

    }

}

List::iterator List::find(Item item)

{

   iterator it = iterator(head);

    while(it.node->next!=NULL){

        if(it.getItem() ==item)

            return it;

        it = it.node->next;

    }

    return iterator(NULL);

}

int main()

{

    List l;

    l.append("one");

    l.append("two");

    l.append("three");

    l.append("four");

    auto it = l.find("one");

    if (!it.end())

        std::cout << "Should be one: " << it.getItem() << std::endl;

    else

        std::cout << "Iterator should not have been null." << std::endl;

    auto no_it = l.find("zero");

    if (no_it.end())

        std::cout << "As expected, zero not found." << std::endl;

    else

        std::cout << "Oops! should not have found zero." << std::endl;

    return 0;

}