Linked list implementation using Templates in C++

Question

I am new to C++ and have been studying data structures lately. I have created linked lists in the following way:

class Random{
private:
   struct Node{
          int data;
          Node* next;
         };
} 

But I came across a piece of code that is doing the same thing in the following way:

template<Typename T>
struct Listnode {
      T data;
      shared_ptr<ListNode<T>> next;
};

I looked it up and found that we use templates when we want to have multiple data types. Like now we can use int, double, float instead of "T". Whereas in the former case we could only use int. However, I don't understand how:

Node* next

is the same as:

shared_ptr<ListNode<T>> next

and how will these be called, I know for the former we use the:

Node->next = new Node;
Node->data = randomdata;

How does it work for the former way. Another thing of the two implementations, which one is better and why?

Answer 1

The T* ptr; form is the basic method declaring a pointer to a memory holding a value of type T. This kind of pointer is initialized either by the base adress of an array T[], by new T(), by new T[] or something else.

As you can see by now there are many ways to allocate the memory the pointer is pointing to. This is one of the pitfalls when it comes to freeing the memory used. should you use delete, delete[], or are we pointing to a memory not even allocated by us? What if we forget to free the allocated memory, or try to access memory already freed?

=> with raw pointers, bugs can be occur easily!

Here smartpointers come to the rescue! Smartpointers like std::unique_ptr, and std::shared_ptr encapsulate these raw pointers for us and handle typesafe memory management. Thus when going out of scope, the memory in a unique_ptr is automatically freed. The same is valid for shared_ptr if no references to it exists.

I would always recommend to use c++'s smart pointers where possible! Which kind of smart pointer you should use depends on the kind of linked list you want to implement (e.g. if circular lists are supported too). btw. have you thought about std::vector or std::list?

Answer 2

As Karoly Horvath said, it's not the same thing:

• T* is a "plain" pointer to objects of type T, it stores an address in memory, and implicitly the type of the object that we can expect to find at this address (which is useful to know e.g. the size of the target memory).
• std::shared_ptr<T> is an object that belongs to the category of "smart-pointers", which are called "smart" because they can manage the memory that is being pointed, by keeping track of how many references exist to that memory location. This means in practical terms that dynamically allocated memory will be released for you when it is no longer used by your code at runtime.

I would say that for a simple linked-list (singly or doubly linked), there is no need to use shared_ptrs. It might be useful e.g. for graphs with dynamic recurrent structure. For genericity sake though, it is better to use a templated version of your node:

template <typename T>
struct ListNode
{
    T data;
    ListNode<T> *next;
};

Answer 3

The second form is a type of "smart" pointer. Most code using modern c++ should be using them.

Using raw (non smart) pointers you have to remember to do the pairing of new/delete or new[]/delete[] when the object goes out of scope. In the simplistic case of a constructor/destructor its not that much of a burden. But, when you are using pointers in a function and that function throws an exception, it gets a bit tricky to free things up.

There are more than one type of smart pointer. unique, shared and weak. Uniques are for one off object that are only used in one place (like an object or function). Shared are for cases where multiple objects are using the same pointer/resource and you only want to call the allocated object's destructor when the last owner of the pointer goes out of scope. Weaks are for cases where the resource is managed by someone else and the pointed to resource should live on after the object with the weak pointer goes out of scope (they are also needed for avoiding cyclical allocations that prevent GC and cause memory leaks).

Smart pointers are a good thing, you should read up on them (Stroustrups book is great). There are few cases now were naked pointers are needed.

Answer 4

First lets get some junk out of the way:

1. It is good to learn and understand the raw implementations of linked lists as you will encounter them (for many good or bad reasons) in production code.
2. IF you ~have~ to use 'invasive' linked lists in your code, templates and 'smarter pointers' are going to save you headaches. (IMO).
3. You are almost always served better by collection classes/templates.

With the caveats above:

The std::shared_ptr is a 'smarter pointer' that wraps a raw pointer (typically produced by calling operator new) and adds RAII style semantics to the mix along with a contract that allows multiple holders of the underlying object to reference the content without it going away. (When used properly.)

A linked list is 'just' a convention for a program to follow (hopefully, but not required to be) homogeneous types without moving the data around. With ('old school', not bad) linked lists ALL of the link management is your responsibility. It is extra easy to either forget, or get distracted and 'forget' to free resources. This is a cause of many nights of debugging and pesky things called 'memory leaks'.

The hybrid 'template link list' is 'better' in that the resource management responsibility is reduced. It is NOT eliminated. It will help reduce a type of memory leak that is forgetting to delete an allocated node. It will NOT eliminate 'memory leaks' that are caused by circular references. (This is case where an 'external actor' is required to break the circular chain and can be extraordinarily complex in 'real' code.)

std::shared_ptr has operators defined that allow you to 'pretend' that you are interacting with WHAT the std::shared pointer is managing. In that way, visually the code looks mostly the same, but the class is(/may be) hiding a little complexity on your behalf. (Pointer checking, etc.)

Which is better? IMO neither. However given a choice between ONLY those two, I would absolutely prefer the 'smarter pointer' version over the 'manual do it your self' style in the VAST majority of cases.

If it was ME I would pick another container. However, if your intent is to learn about the fundamentals of how those containers are implemented (a good thing!) this isn't exactly the answer you want to hear. :-)