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)

CodePudding user response：

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.