The following implementation compiles, works properly, however once all nodes are removed, there is a small memory leak (24 bytes (list node + tail))
I traced the leak using valgrind and the VS2015 graphic debugger.
It seems the tail pointer doesn't update properlyI would love to hear your suggestions nullptr once/ improvements about the list is emtpied.
It's a small code segment, I've been searching for days but couldn't possibly fix itentire header and your design approach.
Despite the bug, I am also open to any suggestions, improvements for this small header.
BelowBelow you can find the header and a small test main.
#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include <iostream>
#include <memory>
#include <initializer_list>
namespace DLL {
template <typename T> class LinkedList{
private:
struct ListNode{
std::unique_ptr<ListNode> next; //2 uniq_ptr can't point to one another.
ListNode* prev = nullptr; //weakptr needs to be cast back to a shared_ptr to check its state.
T data{}; //Initialize empty;
ListNode(const T& element){
this->data = element;
}
};
public:
std::unique_ptr<ListNode> head;
ListNode* tail = nullptr;
LinkedList(){}
~LinkedList(){}
void append(const T& element){
ListNode* curr = nullptr;
if (head.get() == nullptr){ //If list is empty.
head = std::make_unique<ListNode>(element);
}
else if(head.get() -> next.get() == nullptr){ //If list has one element.
head.get() -> next = std::make_unique<ListNode>(element);
curr = head.get() -> next.get(); //Sets raw pointer to the first element.
curr -> prev = head.get();
tail = curr;
}
else{
tail -> next = std::make_unique<ListNode>(element);
curr = tail -> next.get(); //Sets raw pointer to the last element.
curr -> prev = tail;
tail = curr;// The new last element is the tail.
}
}
//Somewhere in the following method, the tail holds the last node without releasing it, as it should, despite the list actually printed as empty.
int remove(const T& element){
ListNode* curr = nullptr;
if (head.get() == nullptr){ //If list is empty.
return -1; //Error: Can't remove from empty list.
}
//List has one or more elements.
curr = head.get();
while(curr != nullptr){
if(curr -> data == element){ //Found element.
if(curr -> prev == nullptr){ //it's head
head = std::move(curr -> next); //Head now points to the next element.
if (head) {
head->prev = nullptr;
}
//New head's previous element points to nothing, making it a true head element.
}
else if(curr -> next.get() == nullptr){ //it's tail.
tail = curr -> prev; //Reference the previous element.
tail -> next.releasereset(); //ReleaseDestroy the old tail element.
if(head.get() == tail){
tail = nullptr; //tail and head should not be the same.
} //List contains one element.
}
else{//it's intermediate.
//The next node should point to the previous one
curr -> next -> prev = curr -> prev;
curr -> prev -> next = std::move(curr -> next);
//The prev node now points to the next one of current.
}
return 1; //Element found in list.
}
curr = curr -> next.get(); //Traverse the next element.
}
return 0; //Element not found in list.
}
void print() {
ListNode* curr = head.get(); //Start from the start of the list.
std::cout << "[ ";
while (curr != nullptr) {
std::cout << curr -> data << " ";
curr = curr -> next.get();
}
std::cout << "]" << std::endl;
}
};
}
#endif
Except from the tail invalidation in remove method the rest of the code is correct.
It's one line of code that eludes me. Apart from this small bug, I would also love to hear your suggestions about the entire header and your design approach.
