Moving from C, how can I implement a doubly linked list in C++ using C++ features?

In 99.9% of the cases I would agree with you on this. But as a training exercise on how to use C++ to create a data structure it is not really a bad start. It teaches about how to use classes to encapsulate memory management (so other code doesn't have to worry about memory leaks etc.). It touches on "ownership" who owns what data and when are raw pointers still ok (when they don't own anything) etc. But yes he should definitely start with learning how to use containers and algorithms first. I would say implementing data structures is a bit more of an advanced use case and it helps a lot if you already know how algorithms and containers (iterators/ranges) work together.

List is a fundamental data-structure, with the other one being an array. They don't require anything above plain C pointers for most efficient and laconic implementations.

Using smart-pointers for lists is a particularly notorious software engineering anti-pattern.

If you try using smart-pointers for list's node sibling pointers, for example, the node's destructor invokes its sibling nodes' destructors in recursive fashion, which ends up overflowing the stack even with lists of relatively modest size.

Get very familiar with the concept of ownership before going too much further in your journey. With very rare exceptions, a container owns its contents. Using smart pointer makes the contents own other contents and usually results in complications like unnecessary recursion.

There are two "main" ways to safely create dynamically allocated storage in C++.

1: Smart Pointers.
2: Containers.

These are distinct patterns, and each has its own "style" for implementing safe, non-leaking storage. You don't generally mix the two.

A doubly linked list is a container, so I would not use smart pointers to implement it.

I would note that std::list has all the properties of a doubly linked list and is therefore likely implemented that way in all standard implementations.

I struggle to find an elegent way to implement this with smart pointers instead.

The trouble is that each "frame" of the dynamically linked list is "owned" by a single object (the list), but has pointers from two other "frame"s (the previous and the next frame). So, trying to use smart pointers does not match the pattern that these smart pointers are used to implement.

I could implement it using shared pointers,

Do you mean std::sharedptr?

but I heard that these should be saldom used and that you should attempt implementing using uniqueptr by default.

Yes. You are have spotted the contradiction in the pattern. If you have a doubly linked list then there are two pointers to each "frame". So you would either need to use a std::sharedptr and have ownership of each frame shared between the prev/next frame (this is very painful as this introduces cycles, and std::sharedptr with cycles is a problem), or you can use std::unique_ptr but here you can only have one owner so only one of the pointers (say next) is the owning pointer, while prev is a non owning pointer. This works but is an asymmetric pattern thus hard to think about and introduces its own complexities.

In this situation the best pattern (in my opinion) is a C pointer (between frames). The "frames" don't own each other they are just linked together. The container is the owner of all the "frames" and it is the responsibility of the container to manage the memory of all the frames via its constructors / destructors.

Some very good discussion about linked list implementations on Code Review

C-pointers work much better than smart pointers for a double-linked list. Smart pointers can have issues with stack overflow. Also, if the smart pointers were freed manually, there's no point to using smart pointers.

The destructor of the list class is responsible for freeing any resources held by the list. Smart pointers would just add much additional overhead, without bringing any benefits.

class DoublyLinkedList -- Note -- doing this already steps you out of the C world and puts you into C++.

I struggle to find an elegent way to implement this with smart pointers -- Don't bother.

Just implement the linked list using raw pointers, but with one major difference I outlined above, and what you are starting to do -- you put a class interface around it and templatize it. You can't do that in C, or at least there is no language features in C that can do that.

The class should be templatized, have proper constructors and destructor, etc. I haven't looked at the C++ standard std::list internally, but I doubt you will see smart pointers in use within any of the low-level data structures.

It is said that raw pointers are a c feature, and that in c++ you should use smart pointers instead -- Yes, for higher-level code, not for low-level code such as the implementation of a data structure.

You need to control the lifetime of basically everything carefully when implementing a data structure, so it becomes more straighforward if the pointer doesn't do things "under the hood" that will just surprise you (in a bad way).

Normal smart pointer usage for list leads to recursion, which tends to be more limited, even if not intrinsically wrong.

if the smart pointers were freed manually, there's no point to using smart pointers.

Smart pointer still expresses ownership. It still help to ensure correct implementation/usage.

Smart pointers would just add much additional overhead

From standard point of view, std::uniqueptr has no overhead (even if implementation has some because of "no-ABI breaking change rule"), and is usable for a double-link list.

std::sharedptr has overhead with the shared block count, but it not needed for a double-link list.

There's no need for smart pointers in this case, best practise would be to use raw pointers. The most fundamental principle in C++ is that of abstraction. You separate the internals of your class from the external interface. The users of your class will not care if the internals of your class uses raw pointers; they can only see the external interface. In other words, if raw pointers are the best option for implementing a class then go for it, just don't expose those pointers in the interface.

Designing a class interface, and implementing that interface are two different disciplines with two different sets of 'best practises'.

For reference, here is how it could be done: you start out with a singly linked list, which is a standard purely-functional data structure and as such can easily be implemented with uniqueptrs. Then you add a back-reference in each node; this will still be just a plain old C pointer since the nodes are already memory-managed through the smart pointers in the other direction.

template 
class DoublyLinkedList {
  struct Node {
    T data;
    std::uniqueptr prev;
    Node next;
    Node(const T& data, std::unique_ptr prev):
       data(data), prev(std::move(prev)), next(nullptr) {}
  };
  Node head;
  std::uniqueptr last;
 public:
  void pushback(const T& x) {
    last = std::makeunique(x, std::move(last));
    if(auto& prev = last->prev)
      prev->next = last.get();
    else
      head = last.get();
  }
};

This is good in the sense that no memory is leaked despite the absence of an explicit destructor. Unfortunately (as remarked earlier by Maxim Egorushkin), the implicit destructor that chases down the chain of uniqueptrs is recursive, and C++ does not give you tail recursion, so this will overflow the call stack when a sufficiently large list is destructed. Of course, that can be avoided by explicitly defining a destructor in iterative style

  ...
  ~DoublyLinkedList() {
    while(last)
      this->popback();
  }
  void popback() {
    last = std::move(last->prev);
  }
  ...

At that point it is dubious whether we've gained anything from the smart pointer, compared to explicit deletion on raw pointers. Using a mix of raw and smart pointers is rather awkward in particular in that it disrupts the symmetry of the doubly-linked list structure.

I would still argue that it is a good idea to default to using smart pointers instead of allocating stuff with new, because memory leaks are about the most annoying problem to chase down. Smart pointers introduce their own issues, but these are easier to fix (in many cases, highlighted already by compiler errors).

Try it online!

Fair, but "use a standard library" is a C++ practice that doesn't exist in C so it's still a good thing to try.

There is so much in C that is possible, but very much discouraged in C++, that making small steps from C toward C++ usually gets you stuck midway, writing very much suboptimal C++. It is a good approach to eradicate these early on. If nothing else, anyone should get rid of C-style arrays and raw owning pointers. They simply have no place in modern C++.

"how to implement doubly linked list in C++ using the C++ features?" - Don't. Just use std::list (or even better; forget about linked lists and just use std::vector).

None of these comments are very helpful, possibly because the question looks a bit insincere.

Regardless, there are several pointer types available in C++. uniqueptr, which means "I own this thing", sharedptr and weakptr which are for use in multithreading problems, and raw pointers. You can't use uniqueptr here, because if uniqueptr head points to the head element, then you cannot have the next element in the linked list be a struct Node containing a member uniqueptr prev because then prev also points to the same Node pointed at by head. This makes no semantic sense, and there is no way to make two uniqueptrs point to the same thing. (There are ways to do it but it violates all the ownership semantics and therefore memory safety guarantees which are the point of using uniqueptr in the first place.)

It may be that you asked this question because you are a Rust developer, and you learned how to write a linked list in Rust, and found that it is not straightforward, because Rust is not a language which makes it easy to work with cyclical or self-referential data structures.

So, the conclusion is raw pointers are still the correct thing to use.

The flaw being that said recursion is unbounded, and grows rapidly. At least with a balanced binary tree or the like, the growth is logarithmic; going from 10M elements to 20M only adds one additional level of recursion, so it's fairly unlikely/impossible any real world data set would involve deep recursion (read: at least hundreds, if not thousands of nested calls) to clean up the data structure.

With a linked list, using std::uniqueptr to get node destruction "for free" (that is, you don't even need to define a destructor for your linked list class) means strictly linear growth in recursion (and not one the compiler can fix with tail-call optimizations or the like), and therefore a much higher likelihood that real-world data would grow large enough that, at the moment the linked list is freed in bulk, you overflow the stack from millions of std::uniqueptr destructors calling one another in sequence.

That's why the OP isn't seeing examples using smart pointers. Because they're a terrible idea here, even if they're zero overhead, even if you can make them work (e.g. having your doubly-linked list use std::sharedptr for forward links, eating the cost of the reference count block and manipulatings it, and std::weakptr for backwards links, to avoid reference cycles that would prevent cleanup); no matter how much work you do to make them work as you hope, if you don't write your own destructor, the unbounded recursion will get you as soon as someone puts enough data in there.

When you move from C to C++ I recommend reading the C++ core guidelines. As you will see there is a tendency to not use new/delete (malloc/free). But for real inspiration you could have a look at std::list and open its header file. You will see something that "C" doesn't have and that's templates. That said you can still implement with raw pointers and new/delete since those will not be "naked" they're inside a datastructure (your DoublyLinkedList) and it is you datastructure that can manage ownership. Another way of looking at it would be from the "ownership" point of view. In this case using smart pointers would actually complicate your tasks, Nodes are NOT the sole owner of prev or next so std::uniqueptr is out for that reason, and using std::sharedptr is also not ok, since Nodes still do not own other nodes (and shared_ptr models ownership too). It is the DoublyLinkedList that owns the nodes and should manage their lifetimes.

That's what I am trying to say. Learn to use those first :)

class DoublyLinkedList {
  mutable std::list list;
  struct NodePtr {
    std::list::iterator it;
    NodePtr (std::list::iterator it) : it(it) {}
    int data () const { return *it; }
    int & data () { return *it; }
    NodePtr prev () const { auto x = it; return --x; }
    NodePtr next () const { auto x = it; return ++x; }
  };
  NodePtr head () const { return list.begin(); }
  NodePtr tail () const { return NodePtr(list_.end()).prev(); }
  ...
};