Singly-linked grocery list

Question

For my own linked list implementation, I've decided to try something different: a linked list of groceries.

The main differences between this implementation and a standard list are:

1. more data fields (name, quantity, if item has been purchased)
2. two size data members (different items and total items)
3. depending on quantity to be removed, an entire node may not be removed

I don't have any particular concerns, and I'd like a general review of this.

I've tested this with some test cases on Ideone.

GroceryList.hpp

#ifndef GROCERY_LIST_HPP
#define GROCERY_LIST_HPP

#include <cstddef>
#include <string>

class LinkedGroceryList
{
private:
    struct Grocery
    {
        std::string name;
        std::size_t quantity;
        bool purchased;
        Grocery* next;
    };

    Grocery* head;
    std::size_t differentGroceries;
    std::size_t totalGroceries;

public:
    LinkedGroceryList();
    ~LinkedGroceryList();
    void addGrocery(std::string const&, std::size_t);
    void removeGrocery(std::string const&, unsigned int);
    bool findGrocery(std::string const&) const;
    void markAsPurchased(std::string const&);
    void displayGroceries() const;
    void clearGroceries();
    std::size_t different() const { return differentGroceries; }
    std::size_t total() const { return totalGroceries; }
    bool empty() const { return differentGroceries == 0; }
};

#endif

GroceryList.cpp

#include "GroceryList.hpp"
#include <iostream>

LinkedGroceryList::LinkedGroceryList()
    : head(nullptr)
    , differentGroceries(0)
    , totalGroceries(0)
{}

LinkedGroceryList::~LinkedGroceryList()
{
    clearGroceries();
}

void LinkedGroceryList::addGrocery(std::string const& name, std::size_t quantity)
{
    Grocery* newGrocery = new Grocery;

    newGrocery->name = name;
    newGrocery->quantity = quantity;
    newGrocery->purchased = false;

    newGrocery->next = nullptr;

    if (!head)
    {
        head = newGrocery;
    }
    else
    {
        Grocery* groceryPtr = head;

        while (groceryPtr->next)
            groceryPtr = groceryPtr->next;

        groceryPtr->next = newGrocery;
    }

    differentGroceries++;
    totalGroceries += quantity;
}

void LinkedGroceryList::removeGrocery(std::string const& name, unsigned int quantity)
{
    if (!head) return;

    Grocery* groceryPtr;

    if (head->name == name)
    {
        groceryPtr = head;
        head = groceryPtr->next;

        totalGroceries -= quantity;
        if (quantity == groceryPtr->quantity)
            differentGroceries--;
        else
        {
            groceryPtr->quantity -= quantity;
            return;
        }

        delete groceryPtr;
    }
    else
    {
        Grocery* predPtr = nullptr;
        groceryPtr = head;

        while (groceryPtr && groceryPtr->name != name)
        {
            predPtr = groceryPtr;
            groceryPtr = groceryPtr->next;
        }

        if (groceryPtr)
        {
            totalGroceries -= quantity;
            if (quantity == groceryPtr->quantity)
                differentGroceries--;
            else
            {
                groceryPtr->quantity -= quantity;
                return;
            }

            predPtr->next = groceryPtr->next;
            delete groceryPtr;
        }
    }
}

bool LinkedGroceryList::findGrocery(std::string const& name) const
{
    if (!head) return false;

    if (head->name == name)
        return true;
    else
    {
        Grocery* groceryPtr = head->next;

        while (groceryPtr)
        {
            if (groceryPtr->name == name)
            return true;

            groceryPtr = groceryPtr->next;
        }
    }

    return false;
}

void LinkedGroceryList::markAsPurchased(std::string const& name)
{
    Grocery* groceryPtr = head;

    while (groceryPtr)
    {
        if (groceryPtr->name == name)
        groceryPtr->purchased = true;

        groceryPtr = groceryPtr->next;
    }
}

void LinkedGroceryList::displayGroceries() const
{
    if (!head) return;

    Grocery* groceryPtr = head;

    while (groceryPtr)
    {
        std::cout << groceryPtr->name << ", ";
        std::cout << groceryPtr->quantity << ", ";
        std::cout << ((groceryPtr->purchased) ? "purchased\n" : "not purchased\n");
        groceryPtr = groceryPtr->next;
    }
}

void LinkedGroceryList::clearGroceries()
{
    if (!head) return;

    Grocery* predPtr = head;
    Grocery* nextGrocery;

    while (predPtr)
    {
        nextGrocery = predPtr->next;
        delete predPtr;
        predPtr = nextGrocery;
    }

    head = nullptr;
    differentGroceries = 0;
    totalGroceries = 0;
}

Driver

#include "GroceryList.hpp"
#include <iostream>

int main()
{
    LinkedGroceryList meats;
    meats.addGrocery("steak", 5);
    meats.addGrocery("chicken", 3);
    meats.addGrocery("pork", 2);

    meats.displayGroceries();
    std::cout << "\nDifferent items: " << meats.different() << "\n";
    std::cout << "Total items: " << meats.total();
    std::cout << "\nsteak present? " << std::boolalpha << meats.findGrocery("steak");
    std::cout << "\ncarrots present? " << std::boolalpha << meats.findGrocery("carrots");

    std::cout << "\n\nRemoving 1 pork...\n\n";
    meats.removeGrocery("pork", 1);

    meats.displayGroceries();
    std::cout << "\nDifferent items: " << meats.different() << "\n";
    std::cout << "Total items: " << meats.total();
    std::cout << "\npork present? " << std::boolalpha << meats.findGrocery("pork");

    meats.markAsPurchased("steak");
    std::cout << "\n\nsteak has been purchased\n\n";
    meats.displayGroceries();
}

Answer 1

Rather than having the user pass in name and quantity, have the user pass in a Grocery. You complete throw away any sense of encapsulation by having the user provide the components rather than the object.

---

Rather than displayGroceries, I would overload operator>> for ostreams.

---

Give Grocery a constructor so you can condense the creation code to be a succinct one liner rather than a half-dozen assignments. (And a constructor can be more efficient since you can avoid a default construct of properties just to immediately assign to them.)

---

Imagine you didn't write this code, and consider the following:

void addGrocery(std::string const&, std::size_t);

What in the world are the parameters? A string and a size_t. Alright... Maybe a name and quantity? Maybe a name and cost in cents? Maybe a name and the aisle the item is found on? Give your public declarations meaningful names!

(Note that this is a perfect example of a reason to work on Grocerys, not string/size_t pairs.)

---

Either keep a tail pointer or insert at the head of the list. addGrocery should not be linear time. That defeats the purpose of a linked list.

---

For simple loop conditions, I prefer for loops:

for (Grocery* grocery = head; grocery; grocery = grocery->next) {
    // ...
}

It's much easier to see what's going on without having to read through an entire while

---

You've way over complicated some of your loops with unnecessary special cases for when head is null. Just let a for not loop is head is null:

bool LinkedGroceryList::findGrocery(std::string const& name) const
{

    for (auto node = head; node; node = node->next) {
        if (head->name == name) {
            return true;
        }
    }
    return false;
}

---

The way you're using the names to do a linear search implies that you're using the wrong data structure. Any time you scan searching for one or more items with an exact match on a key, you need either a map (or mutlimap for one to many).

---

Your differentGroceries and totalGroceries names are a bit confusing. I would consider calling them numGroceries and quantitySum (with similar changes for the method names).

Answer 2

You need to consider the Rule of Three.

That is: the default copy and assignment implementations will not handle the head as you'd like. You need to define them correctly, or hide them (or remove them in C++ 11).

For example:

class LinkedGroceryList
{
private:
    LinkedGroceryList(const LinkedGroceryList& other);
public:
// etc...
};

I agreed with @Corbin as to the names for the sizes, but would consider using size() to hold the length of the list, i.e. differentGroceries to ape the standard library. Likewise clear rather than clearGroceries, as the element type is implicit in the container name.

Similarly (and some would disagree), I prefer findGrocery to be findGroceryByName. That should not just return a bool, but ideally an iterator to the element with the grocery. Alternatively, rename to containsGroceryWithName or containsGrocery.

Also consider some checking of invariants. For example, differentGroceries == 0 <=> head == nullptr.

In the method markAsPurchased, you should break out of the loop on a match. I'd also return bool indicating success in finding a match.

Why does add take a size_t and remove an unsigned?

In the remove method, for the head case: 1. You reassign the head without considering whether or not all it items are removed. 2. You should check to having a negative number or items which becomes an underflow. 3. The head and main case have common code that should be in a common method.

In the add method, you need to check to see if your list already contains an item with that name. Actually there is a bigger problem here. If you merge items when added with the same name, you'll lose track of what is purchased. If you do not, you'll have much more complexity is remove. And what does remove mean for items that may be purchased or not?

I think this means that purchased is not a bool, but a count of the number of items with the given key that have been purchased. The markAsPurchased method could, but does not necessarily need to, be updated to specify the number of items purchased.

Answer 3

I'd start by making the code more generic:

template <class T>
class LinkedList {

Then I'd probably separate the user's data (what you're storing) from "your" data (the links used by the list itself):

    class Node {
        T user_data;
        Node *next;

I'd then have a constructor for Node that took a (reference to a constant) T as a parameter, and created a Node holding that data:

Node(T const &data, Node *next = nullptr) : user_data(data), next(next) {}

To follow the modern "rule of five", we probably want a move constructor to go with that:

Node (T &&data, Node *next = nullptr) : user_data(data), next(next) {}

This will allow us to "steal the guts" of an existing data item when/if it's no longer going to be used. Depending on what the data item contains, that may be a big win. It may not be either, but implementing it is pretty easy (at least in this case) so it's probably worthwhile even though it's uncertain whether it'll do much (if any) real good.

That (of course) is only for C++11 though. If you're stuck with an older compiler, you have to live without rvalue references (or update your compiler).

While we're talking about C++11, there's another change we should consider: instead of managing memory on our own, we should at least consider using a std::unique_ptr to help us out, so Node becomes:

template <class T>
class Node {
    T user_data;
    std::unique_ptr<Node> next;
};

To go with that, we want to use std::make_unique (which was accidentally left out of C++11, but will be in C++14). A simplified (but adequate for this purpose) version looks like this:

template<typename T, typename... Args>
std::unique_ptr<T> make_unique(Args&&... args)
{
    return std::unique_ptr<T>(new T(std::forward<Args>(args)...));
}

We use this to create a node for us, and std::unique_ptr automates deleting the node when it's no longer needed (i.e., when the unique_ptr that points to the node is destroyed).

Grocery* head;

This, of course, should probably be a unique_ptr as well. Depending on the situation, it could be a shared_ptr instead, but in any case almost certainly should not be a "raw" pointer.

std::size_t differentGroceries;
std::size_t totalGroceries;

At least in my opinion, maintaining the total number of items on a running basis is probably close to pointless. Of all the times I've gone shopping, I can't really remember the last time I wanted to know how many items I bought (or planned to buy).

I agree with Corbin, however, that you have a more fundamental problem here: you're trying to implement a set, and a linked-list simply really isn't a very suitable structure for that task.

Quite a bit has already been said about the implementation, so I'm only going to cover a couple of points I didn't notice in the other critiques.

One point that struck me as seriously problematic is that findGrocery, markAsPurchased and displayGroceries all have essentially identical code to traverse the list. I'd prefer to see a single function to traverse the list, and apply some function to a node, and then (probably based on its return value) decide whether to continue. All three of these can then be implemented in terms of that function.

template <class F>
bool traverse(F f) { 
    for (auto pos = head; pos; pos=pos->next)
       if (f(pos->user_data))
           return true;
    return false;
}

This will (probably) improve efficiency compared to your markAsPurchased (which continues to traverse the list even after it has found an item and marked it as purchased).