Take the 2-minute tour ×
Stack Overflow is a question and answer site for professional and enthusiast programmers. It's 100% free, no registration required.

Hi I'm trying to implement a simple singly linked list using smart pointers, here is what I have so far, I opted with using C++'s shared_ptr but I read that a unique_ptr would be more appropriate for this case but, I don't really know how you would iterate over the list (i.e currentNode = currentNode->next) to get to the end of the list in order to insert an element using a unique_ptr. Here is the code I have so far:

template <typename T>
class LinkedList;

template <typename T>
class ListNode
{
public:
    ListNode() : _data(T()) {}
    explicit ListNode(const T& value) : _data(value) {}

    friend class LinkedList < T > ;
private:
    T _data;
    shared_ptr<ListNode<T>> _next;
};

template <typename T>
class LinkedList
{
public:
    void push_back(const T& value)
    {
        if (_root)
        {
            shared_ptr<ListNode<T>> currentNode(_root);

            while (currentNode->_next != nullptr)
            {
                currentNode = currentNode->_next;
            }

            currentNode->_next = make_shared<ListNode<T>>(value);
        }
        else
        {
            _root = make_shared<ListNode<T>>(value); // If the list is completely empty, construct a new root (first element)
        }
    }

    void print() const
    {
        shared_ptr<ListNode<T>> currentNode(_root);

        while (currentNode != nullptr)
        {
            cout << currentNode->_data << " ";
            currentNode = currentNode->_next;
        }

        cout << endl;
    }
private:
    shared_ptr<ListNode<T>> _root;
};

If using unique_ptrs are the better way to go for this program, could you illustrate how I would get past the iterating problem? Since unique_ptrs can't be assigned, how would I do the code block:

shared_ptr<ListNode<T>> currentNode(_root);

while (currentNode->_next != nullptr)
{
    currentNode = currentNode->_next;
}

currentNode->_next = make_shared<ListNode<T>>(value);

using unique_ptrs instead of shared_ptrs? Thanks!

share|improve this question
    
You can't use unique_ptr for this case. They're supposed to manage owndership, so how should these work to link from elsewhere? –  πάντα ῥεῖ Jan 2 at 10:04
    
So is my use of shared_ptrs correct in this case? You say that I can't use unique_ptrs in this case, in what case would using unique_ptrs be appropriate? –  derekdt Jan 2 at 10:09
    
@UserWhoseNameCannotBeTyped sure you can. The first node would be owned by a unique_ptr in the LinkedList. Subsequent nodes would be owned by a unique_ptr in the previous node. –  immibis Jan 2 at 10:10
    
@immibis In my attempt to implement this using unique_ptrs, I did what you just described but I didn't know how to get past the problem of iterating to the end of the list to insert an element. –  derekdt Jan 2 at 10:13
1  
@derektruong With unique_ptr you have one unique_ptr to the object, and all other pointers are plain pointers (ListNode<T>*) –  immibis Jan 2 at 10:14

1 Answer 1

up vote 2 down vote accepted

Your loop with std::unique_ptr may look like:

// Iteration doesn't own resource, so no unique_ptr here.
ListNode<T>* currentNode(_root.get());

while (currentNode->_next != nullptr)
{
    currentNode = currentNode->_next.get();
}

currentNode->_next = make_unique<ListNode<T>>(value);
share|improve this answer
    
And to clarify, if I instantiate LinkedList<int> intLinkedList; and when intLinkedList goes out of scope, the _root will be destroyed, which will destroy the ListNode that the _root is managing, which will cause a chain of deletion since the destruction of the root will cause the destruction of _next, which will cause destruction of the next node, etc, etc? –  derekdt Jan 2 at 10:31
    
Yes, the destructor of _root calls (implicitly thank to smart pointer) the destruction of _next, which calls .., until _next is empty and stops the chaining. –  Jarod42 Jan 2 at 10:37

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.