1

My steps:

  1. Pushing int value = 1
  2. Pushing int value = 2
  3. Trying to pop_back()
  4. Last node mLast is nullptr now
  5. The first node's next pointer stores a garbage value instead of nulltpr

LinkedList.h

template<typename T>
class LinkedList
{
public:
    struct Node
    {
        T value;
        struct Node* next = nullptr;
    };

    Node *mFirst = nullptr;
    Node *mLast = nullptr;

public:
    LinkedList();

    void push_back(const T& value);
    T pop_back();
    bool isEmpty() const;
    void increaseSize();
    void decreaseSize();

    unsigned long mSize;

private:
    void moveNode(Node **node);

private:
    friend std::ostream& operator<<(std::ostream& os, LinkedList<T>& list)
    {
        if (list.isEmpty())
            return os << std::string();

        // While there is a next node, 
        // write it's value to the output stream
        os << "[";
        Node *current = list.mFirst;
        while (current)
        {
            os << current->value;
            if (current->next)
                os << ", ";

            current = current->next;
        }
        os << "]";

        return os;
    }
};

template<typename T>
inline LinkedList<T>::LinkedList()
    : mFirst(nullptr),
    mLast(nullptr),
    mSize(0)
{
}

template<typename T>
inline void LinkedList<T>::push_back(const T& value)
{
    // Create a node
    Node *node = new Node
    {
        value,
        nullptr
    };

    if (!isEmpty())
    {
        // Last existed node points to the new created node
        // and then new becomes the last
        mLast->next = node;
        mLast = node;
    }
    else
    {
        // The first node is the last if the list is empty
        mLast = mFirst = node;
    }
    increaseSize();
}

template<typename T>
inline T LinkedList<T>::pop_back()
{
    if (isEmpty())
        return NULL;

    // Getting the last value 
    T lastValue = mLast->value;

    moveNode(&mLast);
    decreaseSize();

    return lastValue;
}

template<typename T>
inline void LinkedList<T>::moveNode(Node **node)
{
    if (!node || !(*node))
        return;

    delete *node;
    *node = nullptr;
}

template<typename T>
inline bool LinkedList<T>::isEmpty() const
{
    return (mFirst) ? false : true;
}

template<typename T>
inline void LinkedList<T>::increaseSize()
{
    ++mSize;
}

template<typename T>
inline void LinkedList<T>::decreaseSize()
{
    if (mSize <= 0)
        return;

    --mSize;
}

main.cpp

LinkedList<int> list;
list.push_back(1);
list.push_back(2);
list.pop_back();

cout << list;
return 0;

I can do something like this:

Node **current = &mFirst;
while (*current)
{
    if (*current != mLast)
    {
        current = &((*current)->next);
        continue;
    }

    delete *current;
    *current = nullptr;
    current = nullptr;
    mLast = nullptr;
    break;
}

... but it feels wrong because what if I have 1000 elements in the list :c Or is this the right way how the LinkedList works? Even if yes, I still want to know how to solve the problem

I also tried using std::shared_ptr instead of usual pointers but got the same problem (it was the first time I used smart pointers, maybe I just did it wrong. I just replaced all the pointers with std::shared_ptr)

5
  • Side note: pop_back returning NULL with an empty list will be fatal later. Consider what will happen with a LinkedList<std::string> when it tried to construct the string to return from a null pointer. Commented Jan 13, 2023 at 20:57
  • 1
    One of the main drawbacks of a singly linked list is the amount of traversal you need to do for particular things, like getting the node before the last node, or the last node itself if you don't keep a pointer to it. Commented Jan 13, 2023 at 21:01
  • 1
    But if you remove that last node and can replace it with a cached pointer to the node before that, you're now stuck replacing the cached node before the tail. And with what? Cache the third last well? What about the updating that? By the time you're done all the necessary caching, you have a doubly linked list. Commented Jan 13, 2023 at 21:30
  • @user4581301 yeah, as Vlad mentioned below, I should use std::optional<T> instead of NULL Commented Jan 14, 2023 at 8:28
  • @RetiredNinja seems like I'm trying to overcomplicate the LinkedList, which I shouldn't be doing Commented Jan 14, 2023 at 8:32

1 Answer 1

3

Your functions pop_back and moveNode do not reset correctly the data member mLast

That is after calling these functions the data member mLast is set to nullptr instead of setting it to point to the node that precedes the deleted last node and changing its data member next.

As you are using a singly-linked list then the method pop_back in any case will be inefficient. You will need to traverse all the list to find the node that precedes the last deleted node.

Also pay attention to that this return statement

template<typename T>
inline T LinkedList<T>::pop_back()
{
    if (isEmpty())
        return NULL;
        ....

also does not make sense. Instead you should either throw an exception or return an object of the type std::optional<T> (correspondingly changing the return type of the function).

Also the class definition will be more readable if the friend function will be moved in the public section. And its second parameter should be declared with the qualifier const

friend std::ostream& operator<<(std::ostream& os, const LinkedList<T>& list);

And the data member mSize shall not be declared as public.

unsigned long mSize;

Instead you should write a public getter to it.

And at least you should explicitly define the destructor.

These public member functions

template<typename T>
inline void LinkedList<T>::increaseSize()
{
    ++mSize;
}

template<typename T>
inline void LinkedList<T>::decreaseSize()
{
    if (mSize <= 0)
        return;

    --mSize;
}

do not make sense and should be removed.

Sign up to request clarification or add additional context in comments.

4 Comments

Oh, thanks for the code review, I didn't know about std::optional<T>. And thanks for mentioning the functions that don't make sense, I'll remove it.
At first I had something like this in the moveNode function: 1) Node *prev = (*node); 2) (*node) = (*node)->next; 3) delete prev; 4) prev = nullptr; - but this still doesn't effect the garbage value
I guessed that I'm trying to set the prev variable to nullptr so it doesn't affect the actual next variable I wanted change initially. Is there any way to do this without iterating through the whole list?
@MikelGrenlou There is no possibility to access the node that precedes the tail node without traversing the whole list. Look at std::forward_list. It does not have the method pop_back. Your list should have functions that add nodes to beginning of the list and remove them from the beginning of the list.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.