Singly-linked list data structure implementation

Question

This code seems to work correctly. I would appreciate any comments on how to improve the code, e.g. readability, algorithms, const-correctness, memory, anything else I am forgetting? Also, for the function swap_values, would it make more sense to swap two nodes instead of just values of the nodes and why?

SinglyLinkedList.hpp

#pragma once

#include <iostream>

class SinglyLinkedList {
private:
    struct ListNode {
        int value;
        std::shared_ptr<ListNode> next;
        ListNode(int val) : value(val), next(nullptr) {}
    };

    std::shared_ptr<ListNode> head;
    std::shared_ptr<ListNode> tail;

    std::shared_ptr<ListNode> find (int val) const;

public:
    SinglyLinkedList();

    void print_list () const;
    void push_back (int val);
    void pop_back ();
    void push_front (int val);
    void pop_front ();
    size_t get_size () const;
    bool search (int val) const;
    void swap_values (int val1, int val2);
    void remove_nodes (int val);
    void reverse ();

    ~SinglyLinkedList();

};

SinglyLinkedList.cpp

#include "SinglyLinkedList.hpp"


SinglyLinkedList::SinglyLinkedList () : head (nullptr), tail (nullptr) {

}

void SinglyLinkedList::print_list () const {
    // O(n)
    if (head) {
        std::shared_ptr<ListNode> tempNode = head;
        while (tempNode) {
            std::cout << tempNode->value << " ";
            tempNode = tempNode->next;
        }
        std::cout << "\n";
    } else {
        std::cout << "List is empty.\n";
    }
}

void SinglyLinkedList::push_back(int val) {
    // O(n)
    std::shared_ptr<ListNode> currNode = std::make_shared<ListNode>(val);
    if (head) {
        std::shared_ptr<ListNode> tempNode = head;
        while (tempNode != tail) {
            tempNode = tempNode->next;
        }
        tempNode->next = currNode;
        tail = currNode;
    } else {
        head = currNode;
        tail = currNode;
    }
}

void SinglyLinkedList::pop_back () {
    // O(n)
    if (!head) {
        std::cout << "List is empty.\n";
        return;
    }
    if (head == tail) {
        head = nullptr;
        tail = nullptr;
        return;
    }
    std::shared_ptr<ListNode> currNode = head;
    while (currNode->next != tail) {
        currNode = currNode->next;
    }
    tail = currNode;
    currNode->next = nullptr;
}

void SinglyLinkedList::push_front (int val) {
    // O(1)
    std::shared_ptr<ListNode> currNode = std::make_shared<ListNode>(val);
    currNode->next = head;
    head = currNode;
}

void SinglyLinkedList::pop_front () {
    // O(1)
    if (!head) {
        std::cout << "List is empty.\n";
        return;
    }
    std::shared_ptr<ListNode> currNode = head;
    head = head->next;
    currNode->next = nullptr;
}

size_t SinglyLinkedList::get_size () const {
    // O(n)
    size_t listSize = 0;
    std::shared_ptr<ListNode> currNode = head;
    while (currNode) {
        ++listSize;
        currNode = currNode->next;
    }

    return listSize;
}

bool SinglyLinkedList::search (int val) const {
    // O(n)
    if (!head) {
        std::cout << "List is empty.\n";
        return false;
    }
    std::shared_ptr<ListNode> currNode = head;
    while (currNode) {
        if (currNode->value == val) {
            //std::cout << "Value " << val << " is in the list\n";
            return true;
        }
        currNode = currNode->next;
    }
    //std::cout << "Value " << val << " is not in the list.\n";
    return false;
}
std::shared_ptr<SinglyLinkedList::ListNode> SinglyLinkedList::find (int val) const {
    // O(n)
    if (!head) {
        return nullptr;
    }
    std::shared_ptr<ListNode> currNode = head;
    while (currNode) {
        if (currNode->value == val) {
            return currNode;
        }
        currNode = currNode->next;
    }
    return nullptr;
}

void SinglyLinkedList::swap_values (int val1, int val2) {
    // swap is O(1), find is O(n)
    // Should I be swapping nodes instead of values?
    std::shared_ptr<ListNode> val1Node = find (val1);
    std::shared_ptr<ListNode> val2Node = find (val2);

    if (!val1Node) {
        std::cout << "Value " << val1 << " is not in the list.\n";
        return;
    }
    if (!val2Node) {
        std::cout << "Value " << val2 << " is not in the list.\n";
        return;
    }

    int tempNodeVal = val1Node->value;
    val1Node->value = val2Node->value;
    val2Node->value = tempNodeVal;
}

void SinglyLinkedList::remove_nodes (int val) {
    if (!head) {
        std::cout << "List is empty.\n";
        return;
    }
    std::shared_ptr<ListNode> prevNode = nullptr;
    std::shared_ptr<ListNode> currNode = head;
    while (currNode) {
        if (currNode->value == val) {
            // val found - remove
            if (!prevNode) {
                // delete head node
                if (head == tail) {
                    head = nullptr;
                    tail = nullptr;
                    return;
                }
                head = head->next;
                prevNode = currNode;
                currNode = currNode->next;
                prevNode->next = nullptr;
                prevNode = nullptr;
            } else if (currNode == tail) {
                // delete tail node
                tail = prevNode;
                prevNode->next = nullptr;
                currNode->next = nullptr;
            } else {
                prevNode->next = currNode->next;
                currNode->next = nullptr;
                currNode = prevNode->next;
            }
        } else {
            // val not found
            prevNode = currNode;
            currNode = currNode->next;
        }
    }
}

void SinglyLinkedList::reverse () {
    // O(n)
    if (!head || head == tail) {
        return;
    }
    std::shared_ptr<ListNode> currNode = head;
    std::shared_ptr<ListNode> prevNode = nullptr;
    std::shared_ptr<ListNode> nextNode = nullptr;
    head = nullptr;
    tail = head;
    while (currNode) {
        nextNode = currNode->next;
        currNode->next = prevNode;
        prevNode = currNode;
        currNode = nextNode;
    }
    head = prevNode;
}

SinglyLinkedList::~SinglyLinkedList () {

}

main.cpp

#include "SinglyLinkedList.hpp"

int main() {

    // List init
    SinglyLinkedList myList;

    std::cout << "Print list: \n";
    myList.print_list();
    std::cout << "List size: " << myList.get_size() << "\n";

    // Add nodes to the back of the list
    myList.push_back(2);
    myList.push_back(4);
    myList.push_back(3);
    myList.push_back(1);
    std::cout << "Print list: \n";
    myList.print_list();
    std::cout << "List size: " << myList.get_size() << "\n";

    // Add nodes to the front of the list
    myList.push_front(5);
    myList.push_front(7);
    myList.push_front(6);
    std::cout << "Print list: \n";
    myList.print_list();
    std::cout << "List size: " << myList.get_size() << "\n";

    // Pop nodes from the front of the list
    myList.pop_front();
    myList.pop_front();
    std::cout << "Print list: \n";
    myList.print_list();
    std::cout << "List size: " << myList.get_size() << "\n";

    // Pop nodes from the back of the list
    myList.pop_back();
    myList.pop_back();
    std::cout << "Print list: \n";
    myList.print_list();
    std::cout << "List size: " << myList.get_size() << "\n";

    // Check if node with specific velue is in the list
    int valToSearch = 3;
    bool foundVal = myList.search(valToSearch);
    if (foundVal) {
        std::cout << valToSearch << " is in the list.\n";
    } else {
        std::cout << valToSearch << " is not in the list.\n";
    }

    // Swap the values of two nodes
    myList.push_back(7);
    myList.push_back(8);
    myList.push_back(9);
    myList.print_list();
    myList.swap_values(9, 2);
    std::cout << "Print list: \n";
    myList.print_list();

    // Remove nodes from the list
    myList.push_back(9);
    myList.push_back(3);
    myList.push_back(9);
    myList.print_list();
    myList.remove_nodes(5);
    myList.remove_nodes(9);
    myList.remove_nodes(4);
    std::cout << "Print list: \n";
    myList.print_list();

    // Reverse the list
    myList.push_back(9);
    myList.push_back(3);
    myList.push_back(9);
    myList.print_list();
    myList.reverse();
    std::cout << "Print list: \n";
    myList.print_list();

}

Answer 1

About the interface

#pragma once

#pragma once isn't standard, prefer include guards if you want to maximize portability

#include <iostream>

class SinglyLinkedList {
    
private:
    struct ListNode {
        int value;
        std::shared_ptr<ListNode> next;
    

Why a shared_ptr? You don't expose the nodes. I don't see why each node wouldn't be the only one responsible for its next node.

    ListNode(int val) : value(val), next(nullptr) {}

Are you certain that automatically generated copy operator, assignment operator, destructor are fine? Because I don't: at least the destructor will cause issues if the list is too long, because it will trigger recursively until stack-overflow

};

std::shared_ptr<ListNode> head;
std::shared_ptr<ListNode> tail;
std::shared_ptr<ListNode> find (int val) const;

public:
    SinglyLinkedList();

    void print_list () const;

print shouldn't be a member function. There's too many ways to print a list: [1, 2, 3, 4], (1 2 3 4), [1 2 3 4] which are equally fine. That's why you should rather provide a way to access members, and let the user choose the format

void push_back (int val);
void pop_back ();
void push_front (int val);
void pop_front ();

Strangely you don't allow access to the values in the list. I would expect a int back() and int front() at the very least

size_t get_size () const;

Same here for those functions, which are mostly orthogonal to the list class: you could search, swap, reverse, the list if you had access to its elements. remove_nodes indeed needs to rely on a primitive in the class interface, but can't replace it: what if I only want to remove the first / last / duplicated nodes with that value?

bool search (int val) const;
void swap_values (int val1, int val2);
void remove_nodes (int val);
void reverse ();

~SinglyLinkedList();

};

About the implementation:

#include "SinglyLinkedList.hpp"


SinglyLinkedList::SinglyLinkedList () : head (nullptr), tail (nullptr) {
}

You could have inlined this constructor in the header file, your class'd be easier to read

void SinglyLinkedList::print_list () const {
    // O(n)
    if (head) {
        std::shared_ptr<ListNode> tempNode = head;
    

std::shared_ptr should be used when something is co-owned by two objects whose life-times aren't correlated. It is impossible here that tempNode would outlive head. I really believe a unique_ptr for ownership, and a raw pointer obtained by get() for traversal is the way to go

    while (tempNode) {
        std::cout << tempNode->value << " ";
        tempNode = tempNode->next;
    }
    std::cout << "\n";
} else {
    std::cout << "List is empty.\n";
}

This is very rigid. There are a lot of contexts where I don't want a new line, or, worse, a "empty list message"!

}

void SinglyLinkedList::push_back(int val) {
    // O(n)
    

since you maintain a head pointer in your class, you should make use of it to push_back (with O(1) complexity), or dispense with it altogether.

    std::shared_ptr<ListNode> currNode = std::make_shared<ListNode>(val);
    if (head) {
        std::shared_ptr<ListNode> tempNode = head;
        while (tempNode != tail) {
            tempNode = tempNode->next;
        }
        tempNode->next = currNode;
        tail = currNode;
    } else {
        head = currNode;
        tail = currNode;
    }
}

void SinglyLinkedList::pop_back () {
    // O(n)
    if (!head) {
        std::cout << "List is empty.\n";
    

There are many ways to deal with incorrect manipulations, but writing to std::cout isn't one of them. Writing to std::clog or std::cerr would be a beginning, but you primarily need to provide a feed-back mechanism: either an exception, or a return value indicating success / failure

    return;
}
if (head == tail) {
    head = nullptr;
    tail = nullptr;
    return;
}
std::shared_ptr<ListNode> currNode = head;
while (currNode->next != tail) {
    currNode = currNode->next;
}
tail = currNode;

This traversal already appeared twice in your code. It should be encapsulated in its own function

    currNode->next = nullptr;
}

void SinglyLinkedList::push_front (int val) {
    // O(1)
    std::shared_ptr<ListNode> currNode = std::make_shared<ListNode>(val);
    currNode->next = head;
    head = currNode;

There is an std::exchange function in the stl which makes it a one-liner: currNode->next = std::exchange(head, currNode);

}

void SinglyLinkedList::pop_front () {
    // O(1)
    if (!head) {
        std::cout << "List is empty.\n";
        return;
    }
    std::shared_ptr<ListNode> currNode = head;
    head = head->next;
    currNode->next = nullptr;
}

size_t SinglyLinkedList::get_size () const {
    // O(n)
    

You should consider maintaining a size counter to make it O(1), because it's tipically how it's done and clients wouldn't expect O(n) complexity

    size_t listSize = 0;
    std::shared_ptr<ListNode> currNode = head;
    while (currNode) {
        ++listSize;
        currNode = currNode->next;
    }

    return listSize;
}

bool SinglyLinkedList::search (int val) const {
    // O(n)
    if (!head) {
        std::cout << "List is empty.\n";
    

Why print anything? It isn't like it's an error to search an empty list. Simply return false

    return false;
}
std::shared_ptr<ListNode> currNode = head;
while (currNode) {
    if (currNode->value == val) {
        //std::cout << "Value " << val << " is in the list\n";

It's best to eliminate remnants of debugging altogether.

            return true;
        }
        currNode = currNode->next;
    }
    //std::cout << "Value " << val << " is not in the list.\n";
    return false;
}

std::shared_ptr<SinglyLinkedList::ListNode> SinglyLinkedList::find (int val) const {
    // O(n)
    if (!head) {
        return nullptr;
    }
    std::shared_ptr<ListNode> currNode = head;
    while (currNode) {
        if (currNode->value == val) {
            return currNode;
        }
        currNode = currNode->next;
    }    
    return nullptr;
}

void SinglyLinkedList::swap_values (int val1, int val2) {
    // swap is O(1), find is O(n)
    // Should I be swapping nodes instead of values?

Indeed you should. That's an example of disputable design: you now have the burden of error management (checks + reports) It would have been better to make find public, with a slightly different interface (an iterator, eg: a non-owning pointer) and then let the user invoke std::iter_swap

    std::shared_ptr<ListNode> val1Node = find (val1);
    std::shared_ptr<ListNode> val2Node = find (val2);

    if (!val1Node) {
        std::cout << "Value " << val1 << " is not in the list.\n";
        return;
    }
    if (!val2Node) {
        std::cout << "Value " << val2 << " is not in the list.\n";
        return;
    }

    int tempNodeVal = val1Node->value;
    val1Node->value = val2Node->value;
    val2Node->value = tempNodeVal;
}

void SinglyLinkedList::remove_nodes (int val) {
    if (!head) {
        std::cout << "List is empty.\n";
        
So what? That's not an error. 
        
        return;
    }
    std::shared_ptr<ListNode> prevNode = nullptr;
    std::shared_ptr<ListNode> currNode = head;
    while (currNode) {
        if (currNode->value == val) {
            

I thought your find member function was written precisely to find a node with the given value, why don't you use it?

        // val found - remove
        if (!prevNode) {
            // delete head node
            if (head == tail) {
                head = nullptr;
                tail = nullptr;
                return;
            }
            head = head->next;
            prevNode = currNode;
            currNode = currNode->next;
            prevNode->next = nullptr;
            prevNode = nullptr;
        } else if (currNode == tail) {
            // delete tail node
            tail = prevNode;
            prevNode->next = nullptr;
            currNode->next = nullptr;
        } else {
            prevNode->next = currNode->next;
            currNode->next = nullptr;
            currNode = prevNode->next;
        }
        

That seems very complicated. I'm almost certain that you can find a more concise way to express it

            } else {
                // val not found
                prevNode = currNode;
                currNode = currNode->next;
            }
        }
    }

void SinglyLinkedList::reverse () {
    // O(n)
    if (!head || head == tail) {
        return;
    }
    std::shared_ptr<ListNode> currNode = head;
    std::shared_ptr<ListNode> prevNode = nullptr;
    std::shared_ptr<ListNode> nextNode = nullptr;
    head = nullptr;
    tail = head;
    while (currNode) {
        nextNode = currNode->next;
        currNode->next = prevNode;
        prevNode = currNode;
        currNode = nextNode;
    }
    head = prevNode;
}

SinglyLinkedList::~SinglyLinkedList () {

If you leave it empty, consider to declare it =default in your interface. But here you need to define your implementation, since default behavior will result in a stack overflow for large lists

}

Conclusion:

You're on the right track to write good code. But you should study the standard library to get a better idea of how to design a C++ container: container/algorithm orthogonality, iterators, etc.

Answer 2

Expanding on papagaga's answer

---

#include <iostream>

Be aware that many of the C++ implementations currently transparently inject a static constructor into ever translation unit that includes <iostream>. My advice, drop any support for <iostream> or split it into its own IO utility class.

---

    struct ListNode {
        int value;
        std::shared_ptr<ListNode> next;
        ListNode(int val) : value(val), next(nullptr) {}
    };

Why name this ListNode? It's already (privately) encapsulated by SinglyLinkedList. Perhaps just call it Node?

When you have constants, you can use in-class member initialization.

        std::shared_ptr<ListNode> next = nullptr;
        ListNode(int val) : value(val) {}

Why std::shared_ptr? Take some time and watch Herb Sutter's talk from CppCon 2016: Leak-Freedom in C++... By Default.

Papagaga touched on this, but it really needs emphasis. Anytime you are dealing with ownership, you need to keep in mind how the default-generated special member functions operate in that context. The rule of three/five is very important. See Quuxplusone's talk from CppNow 2016: The Rule of Seven (Plus or Minus Two).

You should include <memory> for std::shared_ptr<>.

---

    std::shared_ptr<ListNode> head;
    std::shared_ptr<ListNode> tail;

    SinglyLinkedList();

SinglyLinkedList::SinglyLinkedList () : head (nullptr), tail (nullptr) {
}

If you can avoid using defining the special member functions, then do so. Use in-class member initializers here.

    std::shared_ptr<ListNode> head = nullptr;
    std::shared_ptr<ListNode> tail = nullptr;

    SinglyLinkedList();

SinglyLinkedList::SinglyLinkedList () {
}

As long as you never declare any kind of constructor for your class type, the compiler will implicitly declare one for you.

    std::shared_ptr<ListNode> head = nullptr;
    std::shared_ptr<ListNode> tail = nullptr;

    // Don't need this
    // SinglyLinkedList();

// Or this
// SinglyLinkedList::SinglyLinkedList () {
// }

If you declare/define any another constructor, the compiler will not implicitly generate the default constructor for you. To unsuppress the implicitly-generated default constructor, you can declare the default constructor with the keyword default.

    std::shared_ptr<ListNode> head = nullptr;
    std::shared_ptr<ListNode> tail = nullptr;

    SinglyLinkedList() = default;

// Still don't need this...
// SinglyLinkedList::SinglyLinkedList () {
// }

The same can be done with the destructor...

    ~SinglyLinkedList() = default;

However, the semantics of the implicitly generated functions are meant to be used with values, not ownership references/pointers. So you will need to provide a definition or hope your list never gets big enough to blow the stack.

---

    SinglyLinkedList();
    void print_list () const;

Try to be consistent with your spacing. Spaces are great a differentiating between language constructs and functions. You go back and forth between attached and detached parens. Reserve detached parens for the language constructs

for (/*...*/) { }

while (/*...*/) { }

and attach the parens to your functions.

call(/*...*/) { }

---

    void push_back (int val);
    void pop_back ();
    void push_front (int val);
    void pop_front ();

Do not provide the tail operations as those will be surprising for users who may expect constant time operations. See the Principle of Least Astonishment.

---

    size_t get_size () const;

To avoid having to create a customization point to be able to use your container with non-member std::size(), you should name this member function size().

The C++ standard makes no guarantee that the unqualified size_t will exist. You should qualify your types (std::size_t) and include the library that defines it (<cstddef>). Do not rely on <iostream> to latently include it for you.

If you are not going to provide splicing operations, consider caching the size. Splicing is a constant time operation. If you cache the size, you'll need to recalculate the size on every slice, resulting in a linear-time operation. This is why std::forward_list doesn't have a size member function.

---

    void SinglyLinkedList::print_list () const { ... }

<iostream> provides an unnecessary initialization cost due to the static constructors for those that simply want to store data and not print it to the console. Provide an alternative. Here are a few design patterns to consider:

• Iterator - Objects that traverse the container providing direct access to the values.
• Visitor - A function that takes another function (or lambda) and applies each value to that function.
• Adaptor - An IO object that inherits the container, providing functionality for those who want to opt-in at the costs above.

---

void SinglyLinkedList::push_back(int val) { ... }

This doesn't need to be \$\mathcal{O}(n)\$. If tail doesn't exist, then neither should head. If tail does exist, then you append your new node to the tail node.

---

    // swap is O(1), find is O(n)
    // Should I be swapping nodes instead of values?
    std::shared_ptr<ListNode> val1Node = find (val1);
    std::shared_ptr<ListNode> val2Node = find (val2);

    if (!val1Node) {
        std::cout << "Value " << val1 << " is not in the list.\n";
        return;
    }
    if (!val2Node) {
        std::cout << "Value " << val2 << " is not in the list.\n";
        return;
    }

    int tempNodeVal = val1Node->value;
    val1Node->value = val2Node->value;
    val2Node->value = tempNodeVal;

When working with generic types where the size isn't known, it's going to better to swap the links. For this case, why swap? You already have the new values cached in temporaries from the arguments. Just assign them.

    std::shared_ptr<ListNode> val1Node = find (val1);
    std::shared_ptr<ListNode> val2Node = find (val2);

    if (!val1Node || !val2Node) {
        // indicate that a swap didn't happen?
        return false;
    }

    val1Node->value = val2;
    val2Node->value = val1;
    return true;

Answer 3

Other answers have most of this covered. But I'd like to add one observation:

Don't print error messages to std::cout

The standard output stream is for program output. Use std::cerr for error messages; in many cases, the user may be sending standard output to a pipeline or a file, but leave standard error writing to their terminal. In any case, that's the one to watch for error messages.

For a general-purpose utility class like this, you really should consider whether writing a message is the appropriate choice. I recommend you consider throwing exceptions for list underrun or use of other lists' iterators. The calling application can choose whether and how to handle the exception (as it must for std::bad_alloc already).