Linked list with unique_ptr and "old" pointer

[kyrresc]

Hello,

I have recently started working on linked lists, and had a question regarding deleting nodes from the linked list. I have the following code:

#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

And my implementation of the remove(Node* pos) function looks like this:

LinkedList::Node* LinkedList::LinkedList::remove(Node* pos) {
    pos->prev->next = move(pos->next);
    pos->prev = pos->getNext();
        return pos->getNext();
    }

Is this a correct implementation? And do anyone know of any similar examples with linked lists with unique_ptr's I can look at?

[Peter87]

You need to check that pos->prev is not null before accessing pos->prev->next.

After you have changed the next pointer of the previous node the current node will be destroyed so pos does no longer point to a valid node.

[kyrresc]

Thanks. I am a bit confused regarding this.

Like, what happens. I know that we have to change the ownership of the pointer pointing to the NEXT node in the list (and connect it to the node before the element we want to remove), before we delete the node. (line #2 in my code I hope), but I am unsure exactly what to do beyond that.

[Peter87]

A. Updating the next pointer of the previous node
If the node to be removed is not the first element in the list then you want to do what you are already doing on line 2, but if the node is the first element in the list you instead want to update the head pointer of the list.

B. Updating the prev pointer of the next node
If the node to be removed is not the last element in the list then you want to update pos->next->prev (not pos->prev!), otherwise you instead want to update the tail pointer of the list.


Since A will invalidate the pos pointer you either have to do B before A, or store copies of some of the pointer so that you can safely do B after A without using pos.

[kyrresc]

Thank you!

How do I return a pointer to the next node after the deleted node?
Can I make a copy of the node like this

Node* a = pos->getNext();

before I implement part A. of your post (which destroys the pos pointer)?, and then just return a after I've implemented part A.?

[Peter87]

Yes, that should work.

[kyrresc]

Thanks. Is this the correct way of updating the prev pointer of the next node?

 
pos->next->prev = pos->getPrev()

The idea here is that I now point the pointer which originally pointed to the pos node to the node before the pos node.

[Peter87]

Yes, but only in the case when pos->next != nullptr (pos != tail).

[kyrresc]

Would this be a correct implementation?

LinkedList::Node* LinkedList::LinkedList::remove(Node* pos) {
    if (pos == begin()) {
        head = move(pos->next);
        return begin();
    }
    else if (pos != tail) {
        pos->next->prev = pos->prev;
        Node* a = pos->getNext();
        pos->prev->next = move(pos->next);
        return a;
        
        }
    else {
        return tail;
    }
    
    }

[Peter87]

No. Don't forget that pos could point at ...
1. the head
2. the tail
3. both the head and the tail
4. neither of head or tail

[kyrresc]

Is the implementation correct if pos points at head or neither of head or tail? I.e. the part inside the if and else if-statement, respectively. Just to know if I'm on to something or completely off.

[Peter87]

Take what I have written above with a grain of salt. I missed the fact that you always have a dummy node at the end. That simplifies things. I think what you have above is actually correct, except that when you remove the first element you probably want to set the prev pointer of the new head to null.

[kyrresc]

Like this, at line #6?

begin()->prev = nullptr; //setting the prev pointer of the first node to nullptr. 

[Peter87]

Yes, that should do it.