Is it possible to implement a std::list using unique pointers?

Question

List.h:

#pragma once
#include <iostream>
#include <memory>
#include <initializer_list>


class List{
    public:
        List();
        List(const std::initializer_list<int> &list);
        ~List();
        int size() const;

        void push_back(int val);
        void pop_back();
        void pop_front();
        friend std::ostream &operator << (std::ostream &os, const List &l);

    private:
        void printNodes() const;
        struct Node {
            Node(int data) : data(data) {}
            std::unique_ptr<Node> next;
            Node *previous;
            int data;
        };
        int len;
        std::unique_ptr<Node> head;
        Node *tail;
};

List.cpp

#include "List.h"

List::List() : len(0), head(nullptr), tail(nullptr){
}

List::List(const std::initializer_list<int> &list) : len(0), head(nullptr), tail(nullptr) {
    for (auto &elem : list)
        push_back(elem);
}

List::~List() {
}

void List::push_back(int val){
    if (tail == nullptr) {
        head = std::make_unique<Node>(val);
        tail = head.get();
        head->next = nullptr;
        head->previous = nullptr;
        len++;
    }
    else {
        tail->next = std::make_unique<Node>(val);
        (tail->next)->previous = tail;
        tail = tail->next.get();
        tail->next = nullptr;
        len++;
    }
}

void List::pop_back(){
    if(len == 1){
        auto node = head.release();
        delete node;
        head = nullptr;
        tail = nullptr;
    }else{
        // tail->previous;

    }
}

void List::pop_front(){
    if(len == 1){
        auto node = head.release();
        delete node;
        head = nullptr;
        tail = nullptr;
    }else{


    }
}

void List::printNodes() const{
    Node *temp = head.get();

    while (temp != nullptr) {
        std::cout << temp->data << "\n";
        temp = (temp->next).get();
    }
}

int List::size() const{
    return len;
}

std::ostream &operator<<(std::ostream & os, const List & l){
    l.printNodes();

    return os;
}

Source.cpp

#include <iostream>
#include "List.h"

using namespace std;

int main() {
    List l{3, 5, 1, 6, 7};

    cout << l << endl;
}

Hello Stack Overflow, I'm a Data structures student, and as practice, I'm trying to recreate std::list using smart pointers. Based on what I have read, it appears that unique_ptr should be the default one to use, with shared_ptr and weak_ptr only being used where unique_ptr cannot due to speed differences. Unfortunately, I have hit a wall when trying to implement pop_back() and pop_front(). Do I have to adopt shared pointers to complete the entire std::list reimplementation, or is there a way these functions can be done using unique pointers?

Answer 1

Yes, this is perfectly possible. Let's start with pop_back:

You have a pointer to the node already with tail, but that's not the interesting one, since it's just a raw pointer. The pointer that you need is the unique_ptr to that same node. Where is that pointer stored? Is there an easy way to get to it starting from tail?

Once you have the unique_ptr, unchaining the node from the list is as easy as resetting that pointer. Note that there is no need to call release and delete the node manually.

Now for pop_front: Here you already have the unique_ptr in hand, it's head. But you have to be careful as the whole list rests on this one. Resetting the head will make the entire list disappear. So be sure to detach the rest of the list from the head and reattach it with the list first. If you do this properly, deleting the original head will not even be a worry for you. Try it out!

Be sure to draw a picture of the list to visualize which node points where. It's rather difficult to keep all of this information in your head at once.