Accessing and Changing Objects in Linked List c++

Question

I've been able to find Q&A's for inserting and deleting objects from a linked list. But my problem is accessing and updating those objects from a linked list.

The following code is part of a school project wherein I need to make a Linked List of Payroll objects. I need to be able to insert, delete, search by specific parameters, and update employee payroll info. I'm having no problems inserting and deleting. But I'm somewhat lost on how to search and access those objects to interact with their variables.

In the InList function, I pass a linked list and an int, create the Payroll object and assign the int as the employee number variable. Then I use P's search function and pass that payroll object as the argument.

void InList(const orderedLinkedList<Payroll>& P, int employee_number)
{
    Payroll payListEmpNum;
    payListEmpNum.setEmployeeNumber(employee_number);

    if (P.search(payListEmpNum) == 1)
    {
        payListEmpNum.printPayroll();//this is just printing my local employee_number.
    }
    else 
    {
        cout << "Sorry, that employee was not found.\n" << endl;
    };
}

This is the search function for my orderedlinkedlist class. It iterates through the list, and tests each object's employee number against the object that I sent. I can send my current pointer to my Payroll class to print the records, but that doesn't give me access to the data.

template <class Type>
bool orderedLinkedList<Type>::search(const Type& searchItem) const
{
    bool found = false;
    nodeType<Type> *current; //pointer to traverse the list


    current = first;  //start the search at the first node

    while (current != NULL && !found)
        if (current->info >= searchItem)
            found = true;
        else
            current = current->link;

    if (found) {
        found = (current->info == searchItem); //test for equality
    }
    return found;
}//end search

However, since the search function doesn't return any data, InList only prints my local variable, employee_number, and null for all the other variables.

I'm not sure how to get access to my object's variables. Should I write a different function to handle this? Is this a pointer problem?

Thanks!

Answer 1

As it is a school project, it is all about learning. So here a few points mentioned, which helps you tackle this and future similar problems:

• The name of the list you wrote is orderedList<T>. Hence, one would assume the list is sorted by some key, which is probably part of T As such, if one searches for that key, one would assume it is not linear search, but instead some faster search algorithm is used for the find() or search() as well as for the exists() functions.
• On the other hand, if it is required to search the list by criteria other than the key used to sort the list, linear search is okay, but then the find function should allow searching by arbitrary criteria.
• A minor drawback of the code shown in the question might be (unless it becomes obvious in parts of the code not shown), which key is being used for sorting the list. As such, offering a search() function which returns a non-const element is dangerous, as the user could by accident modify the key of the returned element and thus break the sorting of the list.
• Now it is not a big secret, that there is a list already in the C++ standard library std::list, for example. So, instead of inventing new names for commonplace functions, why not simply look up the functions of the standard class and reuse those names? 2 Benefits: 1. users who know Standard types, can use your code more quickly. 2. You as well as others will learn something they can reuse later, when they start to use standard library.
• As we have seen, that changing an element of the list can be dangerous, fatal, there is still one other option: Remove the found element, change it/copy it, modify it and re-insert into the list. This way, you can be sure not to compromise the lists implementation.

As such, I advice to opt a bit to the immutable side and offer a function similar to the one below for vanilla search purposes. As an aside, please note, that the concept of iterators as done in std library would help reuse this function for other use cases.

template <class T>
const T* find(const orderedList<T> & list, std::function<bool(const T&)> predicate)
{
     const nodeType<T> *current = list.head(); 
     while( nullptr != current )
     {
         if( predicate(current->info) ) // assuming info is of type T...
             return &current->info;
         current = current->link;
     }
     return nullptr;
}

For mutating purposes, you could consider a function like:

template <class T>
bool replace( orderedList<T>& list, std::function<bool(const T&)> predicate, 
    std::function<void(T&)> modifier )
{
     // pseudocode:
     // 1. find node (nodeeType<T>), like in find() above.
     // 2. remove that node from the list.
     // 3. call modifier(node->info)
     // 4. re-insert node into list, using insert() or similar.
     // 5. return true, if a replacement has been done, false if element 
     // was not found and list did not change.
}

Obviously, I chose free standing functions and not member functions of the list class. Especially if the list is already done, instead of modifying it over and over again, it is often a good idea to simply write algorithm functions which use the lists type but are not members of the list.

// Sample application code:
#include <functional>
#include <orderedList>
#include <cstdint>

struct Payroll
{
    uint32_t employee_id;
    float salary;
};

typedef orderedList<Payroll> PayrollList;

bool change_salary( PayrollList& list, uint32_t emp_id, float newSalary )
{
    return replace( list, [&]( const Payroll& payroll ) -> bool {
            if( emp_id == payroll.employee_id )
                 return true;
            return false;
        }, [&](Payroll& payroll) {
             payroll.salary = newSalary;
        });
}

Answer 2

You should have a function that returns a pointer to the item if it exists, or nullptr otherwise.

template <class Type>
const Type* orderedLinkedList<Type>::search(const Type& searchItem) const
{
    bool found = false;
    nodeType<Type> *current; //pointer to traverse the list

    current = first;  //start the search at the first node

    while (current != nullptr)
    {
        if (current->info == searchItem)
            return &current->info;
        current = current->link;
    }
    return nullptr;
}

If you want to still have a true / false function, it can use the above:

template <class Type>
bool orderedLinkedList<Type>::exists(const Type& searchItem) const
{  return search(searchItem) != nullptr; }

Note that in search, we return a pointer to the actual data, not a pointer to nodeType. The reason being that if this function is public, and nodeType is an implementation detail of the linked list, returning nodeType's may not make sense to the user.

The user shouldn't know or care what a nodeType is or its purpose. What does make sense is the data that the user stored in the linked list, and that is what is returned.

Answer 3

You need to return a pointer to the object found in the search function. Return a invalid (NULL) if not found.

template

nodeType<Type> * orderedLinkedList<Type>::search(const Type& searchItem) const
{
    bool found = false;
    nodeType<Type> *current; //pointer to traverse the list


    current = first;  //start the search at the first node

    while (current != NULL && !found)
        if (current->info >= searchItem) {
            if (current->info == searchItem)
                return current;
            else 
                return nullptr;
        }
        else
           current = current->link;


    return nullptr;
}//end search