My steps:
- Pushing int value =
1 - Pushing int value =
2 - Trying to
pop_back() - Last node
mLastis nullptr now - The first node's
nextpointer stores a garbage value instead ofnulltpr
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)
pop_backreturningNULLwith an empty list will be fatal later. Consider what will happen with aLinkedList<std::string>when it tried to construct thestringto return from a null pointer.std::optional<T>instead ofNULL