Skip to main content
4 of 4
copy-edited
Deduplicator
  • 19.9k
  • 1
  • 32
  • 65

Doubly linked list std::unique_ptr template class implementation

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.

solid.py
  • 161
  • 1
  • 8