C++ classes & linked list: adding & counting items

Question

I need to make a linked list with classes. Each list will store two values: a URI and IP. After doing all the adding, I need to be able count the total number of items in the linked list. I have tried the following code but it doesn't compile. We are not allowed to use std::list. Any suggestions please?

#include <iostream>
#include <cstdlib>
#include <string>

using namespace std;

class ip_uri_store {
  protected:
    string ip;
    string uri;
    ip_uri_store *next;

  public:
     ip_uri_store(string huri, string hip);
    void additem(string auri, string aip);
    void deleteitem(string duri);
    void findbyuri(string furi);
    void findbyip(string fip);
    int totalitems();
};

ip_uri_store *head = NULL;
ip_uri_store *curr = NULL;

void ip_uri_store::additem(string auri, string aip)
{
    curr = head;
    while (curr->next != NULL) {
 curr = curr->next;
    }

    curr->uri = auri;
    curr->next = new ip_uri_store;
    curr->ip = aip;
    curr->next = new ip_uri_store;
    curr = curr->next;
    curr = head;
}

int ip_uri_store::totalitems()
{
    int i = 0;

    curr = head;

    while (curr->next != NULL) {
 i += 1;
 curr = curr->next;
    }

    return i;
}

int main(int argc, char *argv[])
{
    if (argc == 1) {
 cout << "123456, [email protected], Gordon Brown" << endl;
 return (0);
    }

    head = new ip_uri_store;
    curr = head;
    int i;


    for (i = 1; i < argc; i++) {

 if (argv[i][0] == 'A') //add item
 {
     ip_uri_store.additem(argv[i + 1], argv[i + 2]);
     i += 2;
 }

 else if (argv[i][0] == 'N') //print total tiems
 {
     cout << ip_uri_store.totalitems() << endl;
 }

 else {
     cout << "command error\n";
     return 0;
 }
    }
    return (0);
}

Answer 1

You need to provide the two arguments to the constructor of your ip_uri_store class:

// The constructor call needs two arguments
curr->next = new ip_uri_store(huri, hip);

You cannot call instance methods on the class itself:

// Invalid, totalitems() is valid only on instances of ip_uri_store. 
cout << ip_uri_store.totalitems() << endl;

Why are the variables head and curr global? They really should be data members of a class.

Pull out the ip, uri and next members of ip_uri_store and put them in their own structure, say ip_uri_store_node. Then, ip_ur_store_node can define a constructor that initializes them. Then make ip_uri_store hold the head and curr pointers to ip_uri_store_node instances.

This is what I mean:

struct ip_uri_store_node
{
    string ip;
    string uri;
    ip_uri_store_node* next;

    ip_uri_store_node(const char* u, const char* i)
        : ip(i), uri(u), next(0) {}
};

class ip_uri_store
{
private:
    ip_uri_store_node* head;
    ip_uri_store_node* curr;
public:
    // Initializes head and curr
    ip_uri_store();
    // These functions woud act on head and curr.
    void additem(string auri, string aip);
    void deleteitem(string duri);
    void findbyuri(string furi);
    void findbyip(string fip);
    int totalitems();
};

int main()
{
    ip_uri_store list;
    // Do things with the list...
    return 0;
}

The function additem can create new instances of ip_uri_store_node like this:

curr->next = new ip_uri_store_node(auri, aip);

The rest is up to you.

Answer 2

Your ip_uri_store::additem() is pretty messed up. In it you change the curr object before you assign a new value to it:

curr->uri = auri;
curr->next = new ip_uri_store;

In doing so you change the last item in the list instead of assigning auri to the new item added later. (Interestingly, you got the order right with ip.)

---

I like the idea of giving pieces of code names, so that you can read what they do. Functions are what this is done with. For example, I'd factor out the code that finds the last list node

ip_uri_store *find_last_node(ip_uri_store *curr)
{
    while (curr->next != NULL) {
        curr = curr->next;
    }
    return curr;
}

and call it from ip_uri_store::additem():

void ip_uri_store::additem(string auri, string aip)
{
    ip_uri_store *curr = find_last_node(head);
    // ...

Now create a new object and remember its address in curr->next

    // ...
    curr->next = new ip_uri_store(auri,aip);
}

---

Your ip_uri_store::totalitems() returns an int. Why? Do you ever expect the count of objects to be negative? Better return an unsigned type.

---

You should consider what happens when you delete a list node. If it still points to a next object, chances are the pointer isn't stored anywhere else, and so the object (and those it points to) is (are) leaking. One way to deal with that is to write a destructor for ip_uri_store which deletes next. (If you want to delete a node without having it delete its own tail, you could assign NULL to its next pointer first.)

Also, according to the Rule of Three, you need to think about copying of list nodes. That's not easy to get right in the first try, so you might just want to forbid it:

class ip_uri_store {
  private:
    ip_uri_store(const ip_uri_store&); // not implemented
    ip_uri_store& operator=(const ip_uri_store&); // not implemented
  // ...

---

Instead of using global variables, you put them into class. That way you could have more than one list. Rename ip_uri_store to ip_uri_store_impl and pout it into a new ip_uri_store class:

class ip_uri_store {
  private:
    class ip_uri_store_impl { /* ... */ };
    ip_uri_store_impl* head;
};

Since this class manages dynamically allocated objects, you need to think about destruction and copying such objects.

The wrapper class should have public methods that invoke the methods of ip_uri_store_impl whenthey nedd to. Functions like totalitems(), which operate on the whole list (instead of a node), should probably be implemented in the wrapper class.