Inspired by the talk of Herb Sutter in CppCon2016, I decided to make a doubly linked list using templates, smart pointers, and raw pointers (for back-pointers, having a cycle of std::unique_ptrs would be a bug).
The following proof-of-concept implementation compiles and works properly.
I would love to hear your suggestions / improvements about the entire header and your design approach.
Below you can find the header and a small test main.
LinkedList.h
#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.
}
}
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.reset(); //Destroy 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
main.cpp
#include "LinkedList.h"
int main() { //Temporary Test Main will be split from the implementation file in the future
DLL::LinkedList <int> list; //Create an empty list
list.append(1);
list.append(2);
list.append(3);
list.append(4);
list.append(5);
list.print();
list.remove(5);
list.print();
list.remove(1);
list.print();
list.remove(3);
list.print();
list.remove(2);
list.print();
list.remove(4);
list.print();
return 0;
}
I compiled with g++: g++ -std=c++14 main.cpp -o out and with the VS2015 compiler.
The C++14 flag is needed for the std::make_unique call.
