Linked list, implementation of insert function

[kyrresc]

Posted a similar question regarding Linked Lists, but as this is regarding the implementation of another member function I thought I'd make a new thread.

#pragma once

#include <memory>
#include <ostream>
#include <string>

// test code 
void testLinkedList();


namespace LinkedList {
class Node {
private:
    const std::string value;    // The data held by the LinkedList
    std::unique_ptr<Node> next; // unique_ptr to the next node
    Node* prev;                 // raw (non-owning) ptr to the previous node
public:
    Node() : value(), next(nullptr), prev(nullptr) {}
    // construct a node with string value, a unique_ptr to the next node, and a pointer to the previous node
    Node(const std::string& value, std::unique_ptr<Node> next, Node* prev)
        : value(value)
        , next(std::move(next))
        , prev(prev)
    {}
    // We can use the default destructor, since unique_ptr takes care of deleting memory
    ~Node() = default;
    // return the value of the node
    std::string getValue() const { return value; }

    // return a raw (non-owning) pointer to the next node
    Node* getNext() const { return next.get(); }
    // return a raw (non-owning) pointer to the previous node
    Node* getPrev() const { return prev; }

    // write the value of the node to the ostream
    friend std::ostream & operator<<(std::ostream & os, const Node & node);

    friend class LinkedList;
};

class LinkedList {
private:
    // ptr to the first node
    std::unique_ptr<Node> head;
    // a raw pointer to the last node, the last node is always a dummy node
    // this is declared as a const ptr to a Node, so that tail never can
    // point anywhere else
    Node* const tail;
public:
    //create the dummy node, and make tail point to it
    LinkedList()
        : head(std::make_unique<Node>())
        , tail(head.get())
    {}
    ~LinkedList() = default;

    //if next is a nullptr (i.e. head is the dummy node), the list is emtpy
    bool isEmpty() const { return !head->next; }


    //return a pointer to first element
    Node* begin() const { return head.get(); }
    //return a pointer to beyond-end element
    Node* end() const { return tail; }

    // The insert function takes a pointer to node (pos) and a string (value). It creates a new
    // node which contains value. The new node is inserted into the LinkedList BEFORE the
    // node pointed to by pos.
    Node* insert(Node *pos, const std::string& value);

    // The find function traverses the linked list and returns a pointer to the first node
    // that contains the value given.
    // If the value isn't in the list, find returns a pointer to the dummy node at the end
    // of the list.
    Node* find(const std::string& value);

    // The remove function takes a pointer to a node, and removes the node from the list. The
    // function returns a pointer to the element after the removed node.
    Node* remove(Node* pos);

    // The remove function takes a string and removes the first node which contains the value.
    void remove(const std::string& value);

    // write a string representation of the list to the ostream
    friend std::ostream & operator<<(std::ostream & os, const LinkedList& list);
};
}// namespace LinkedList 

So I want to implement the insert function described in the code-snippet. This is what I have done:

LinkedList::Node* LinkedList::LinkedList::insert(Node *pos, const std::string& value) {
    
    if (pos == begin()) { 
        auto new_head = std::make_unique<Node>(value,move(head),nullptr); 
        head = move(new_head);
        pos->prev = begin();
    }
    else {
    std::unique_ptr<Node> new_node = std::make_unique<Node>(value,move(pos->prev->next),pos->prev); 
    pos->prev->next = move(new_node); 
    pos->prev = pos->prev->getNext(); 
    }
    return pos->getPrev();
}

It is said that we always insert a node BEFORE the pos the insert function takes in, so I assume we never have to change what is in fact the dummy node.
If we consider a linked list of two nodes A <-> B, and we want to insert a new node C.

If we want to insert a node at the start of the list, i.e. before node A, we have to make sure to give the new node (new_node) ownership of the original head pointer. I.e. after line #4 it's new_node(aka C) who now owns A, NOT head anymore. We then have to give head ownership of C. This is achieved in line #5. Finally we set A's prev-pointer equal to the C-pointer, so A and C are now connected with both a unique_ptr and a normal ptr.

Is this correct?

[dutch]

I don't think the next pointer should be a unique_ptr.

[kyrresc]

It should -- see line #15.

[dutch]

I saw line 15. I disagree with it.
Does anyone else have an opinion on this?

[dhayden]

Does head point to a dummy node or the first node? isEmpty() thinks it points to a dummy node. Insert() thinks it points to the first node.

I agree with dutch: don't make next a unique_ptr. Doubly linked lists are hard enough to code without having to worry that a tiny slip will delete half your list.

See my comment on this thread regarding a validation routine. It should help you debug your list code: http://www.cplusplus.com/forum/beginner/251469/