2
\$\begingroup\$

The code below is my implementation of Templated Doubly Linked List in C++. I would be much obliged if you review my code and give me pointers on where and how I can improve the code. Thanks in advance.

#include <iostream>

template<typename T>
class two_way_linked_list
{
    class node
    {
    public:
        T data;
        node* next;
        node* prev;

        //constructors
        node():next(nullptr),prev(nullptr)
        {
        }
        node(T d):data(d),next(nullptr),prev(nullptr)
        {
        }
    };
    node* head = nullptr;
    node* tail = nullptr;
public:

    //overloaded << operator to print the list
    friend std::ostream& operator << (std::ostream& out , two_way_linked_list<T>& obj)
    {
        node* temp=obj.head;
        out << "Printing the list: " << std::endl;
        while (temp)
        {
            out << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
        return out;
    }

    //basic functions
    void push_back(T);
    void push_front(T);
    bool is_empty();
    void reverse();
    void clear();
    void remove(T);
};

//adds a item into end of the list
template <typename T>
void two_way_linked_list<T>:: push_back(T dat)
{
    node* current = new node(dat);
    if (head == nullptr)
    {
        head = current;
    }
    else
    {
        tail -> next = current;
        current -> prev = tail;
    }
    tail = current;
}

//adds an item to front of list
template <typename T>
void two_way_linked_list<T>:: push_front(T dat)
{
    node* current = new node(dat);
    if (head == nullptr)
    {
        head = current;
        tail = current;
    }
    else
    {
        head -> prev = current;
        current -> next = head;
        head = current;
    }
}

//checks if the list is empty
template <typename T>
bool two_way_linked_list<T>:: is_empty()
{
    if (head == nullptr && tail == nullptr)
    {
        return true;
    }
    else
        return false;
}

//reverses the list
template <typename T>
void two_way_linked_list<T>:: reverse()
{
    node* current = tail;
    node* future_next = nullptr;
    while (current)
    {
        future_next = current -> prev;
        if (current == tail)
        {
            head = tail;
            current -> prev = nullptr;
            current -> next = future_next;
        }
        else
        {
            current -> next = future_next;
            current -> prev = tail;
        }
        tail = current;
        current = future_next;
    }
}

//removes a given data node
template <typename T>
void two_way_linked_list<T>::remove(T dat)
{
    node* current = head;
    node* previous = head;
    while (current)
    {
        if (current -> data == dat)
        {
            if(head == tail)
            {
                head = nullptr;
                tail = nullptr;
                delete current;
                std::cout << "Removed: " << dat << std::endl;
                return ;
            }
            else if (current == head)
            {
                head = current->next;
                head -> prev = nullptr;
                delete current;
                std::cout << "Removed: " << dat << std::endl;
                return ;
            }
            else if (current == tail)
            {
                previous -> next = nullptr;
                tail = previous;
                delete current;
                std::cout << "Removed: " << dat <<std::endl;
                return ;
            }
            else
            {
                (previous -> next) = (current -> next);
                (current -> next) -> prev = previous;
                delete current;
                std::cout << "Removed: " << dat <<std::endl;
                return ;
            }
        }
        previous = current;
        current = current -> next;
    }
    std::cerr << "Element not in list" << std::endl;
    return ;
}

//deallocates all dynamically allocated memory
template <typename T>
void two_way_linked_list<T>::clear()
{
    node* current = head;
    node* temp = head;
    while (current)
    {
        current = current -> next;
        delete temp;
        temp = current;
    }
    delete temp;
    head = nullptr;
    tail = nullptr;
}

int main()
{
    //driver program for int type list
    two_way_linked_list<int> list1;
    int temp;
    while (1)
    {
        std::cin >> temp;
        if (temp == -1) break;
        else
        {
            list1.push_front(temp);
        }
    }
    std::cout << list1;
    list1.remove(1);
    std::cout << list1;
    list1.reverse();
    std::cout << list1;
    list1.remove(5);
    std::cout << list1;
    list1.reverse();
    std::cout << list1;
    list1.remove(3);
    std::cout << list1;
    list1.remove(6);
    std::cout << list1;
    list1.reverse();
    std::cout << list1;
    list1.reverse();
    std::cout << list1;
    list1.clear();
}
\$\endgroup\$
2
\$\begingroup\$

It leaks.

There is no destructor. Thus it will leak unless you manually clean the object.

{
    two_way_linked_list<int>  list;
    list.push_back(4);
}
// Leaks HERE.

Does not obey the rule of 3/5

The compiler generates several methods for you. These methods work well as long as the class does not have "Owned RAW pointers". Your class does (the head and tail).

As a result when you make copies of the object you will get unexpected results. Also if you add a destructor it will probably crash on a double delete.

{
    two_way_linked_list<int>   x;
    x.push_back(5);
    two_way_linked_list<int>   y(x);
    y.push_back(6);

    std::cout << x << "\n";  // probably prints 5 and 6
                             // Even though you pushed 6 to y.
}

Don't use if test to return bool.

bool two_way_linked_list<T>:: is_empty()
{
    if (head == nullptr && tail == nullptr)
    {
        return true;
    }
    else
        return false;
}

// Easier to write as
bool two_way_linked_list<T>:: is_empty()
{
    return head == nullptr && tail == nullptr;
}

Simplify remove

Since you have a doubly linked list. You don't need the variable previous. You can find that from current->prev.

 if (current->dat == dat)
 {
      // Some Null checking required.
      // But not included in this demo.
      current->prev->next = current->next;
      current->next->prev = current->prev;
 }

Use a Sentinel Value.

If you add a fake value to the list. So the list always has one node (the sentinel can not be deleted). Then you make the list circular so the head points to the tail and the tail points back at the tail.

Then you can get rid of all the nullptr checks. This makes the code much simpler to read and write.

Pass by reference.

You pass your parameters by value. When they data type is an integer this is not a problem. But sice this is a templated class the data type can be anything. As a result when you pass by value you generate a copy of the object. So pass the parameter by const reference to avoid the copy.

void two_way_linked_list<T>:: push_back(T const& dat) 
                                          ^^^^^^^   // Add const ref

This avoids a copy when you pass the parameter to the function.

// Other places
void two_way_linked_list<T>:: push_front(T dat)
void two_way_linked_list<T>::remove(T dat)

Move Semantics

You don't take advantage of move semantics. To put something in the list you still need to copy it into the node. Sometimes this has to happen. But sometimes you can move an object into a list and save the cost of a copy.

void two_way_linked_list<T>:: push_back(T&& dat) 
                                         ^^   An r-Value reference
                                              dat can be moved into
                                              destroying original value
                                              and cheaply putting value
                                              into the list.
\$\endgroup\$
2
\$\begingroup\$

Your C++ is improving. However, a couple of thoughts:

Advice 1

operator<< may be simplified and funkyfied a little bit:

friend std::ostream& operator << (std::ostream& out , two_way_linked_list<T>& obj)
{
    out << "[";
    std::string separator = "";
    for (node* n = obj.head; n != nullptr; n = n->next)
    {
        out << separator;
        separator = ", ";
        out << n->data;
    }

    return out << "]";
}

Possible output may be, say, [1, 2, 3].

Advice 2

is_empty() may be just

template <typename T>
bool two_way_linked_list<T>::is_empty() const
{
    return head == nullptr;
}

Note that checking of tail is omitted since it is too nullptr when head is nullptr.

Advice 3

reverse() can be

template <typename T>
void two_way_linked_list<T>::reverse()
{
    if (is_empty())
    {
        return;
    }

    node* new_head = head;
    node* new_tail = head;
    node* current  = head->next;
    node* next;

    while (current)
    {
        next = current->next;
        current->next = new_head;
        new_head->prev = current;
        new_head = current;
        current = next;
    }

    new_head->prev = nullptr;
    new_tail->next = nullptr;

    head = new_head;
    tail = new_tail;
}

Advice 4

remove is overkilling it. Consider having an utility private method that scans from the list and returns the linked list node that contains the given datum. Next, you will need another utility method that receives a linked list node and unlinks it from the list:

template<typename T>
typename two_way_linked_list<T>::node* two_way_linked_list<T>::find_node_by_data(T const& data) const
{
    node* current = head;

    while (current)
    {
        if (current->data == data)
        {
            return current;
        }

        current = current->next;
    }

    return nullptr;
}

template<typename T>
void two_way_linked_list<T>::unlink(two_way_linked_list<T>::node* n)
{
    if (n->prev)
    {
        n->prev->next = n->next;
    }
    else
    {
        head = n->next;
        head->prev = nullptr;
    }

    if (n->next)
    {
        n->next->prev = n->prev;
    }
    else
    {
        tail = n->prev;
        tail->next = nullptr;
    }
}

//removes a given data node
template <typename T>
void two_way_linked_list<T>::remove(T dat)
{
    node* target_node = find_node_by_data(dat);

    if (target_node)
    {
        unlink(target_node);
        delete target_node;
    }
}

Advice 5

clear can be simpler:

template <typename T>
void two_way_linked_list<T>::clear()
{
    for (node* current = head, *next; current;)
    {
        next = current->next;
        delete current;
        current = next;
    }

    head = nullptr;
    tail = nullptr;
}

Finally

I think that printing to standard output from within algorithms/data structures should be omitted. Think what happens if your friend uses your list: when he proceeds to deleting many elements from a large list, he will be overwhelmed with all the output and will waste many CPU cycles while printing to standard output.

\$\endgroup\$
1
\$\begingroup\$
        //constructors
        node() : next(nullptr), prev(nullptr) {}

When working with templated types, be careful with assumptions. T is not guaranteed to be default-constructible. When T is a built-in type, what is the value stored by the member data when node is default-constructed?

        // omit it.
        // node() : next(nullptr), prev(nullptr) {}

        node(T d) : data(d), next(nullptr), prev(nullptr) {}

Prefer in-class initializers to member initializers in constructors for constant initializers. By defining constants in-class, you make it explicit that members will always default to a value unless assigned to.

For in-parameters, pass cheaply-copied types by value and others by reference to const. When copying is cheap (doubles), nothing beats the simplicity and safety of passing by value. When you don't know the size or are not using an optimization technique (like copying inputs), prefer to pass by reference to const.

        node* next = nullptr;
        node* prev = nullptr;

        node(const T& d) : data(d) {}

    struct node {
        node* next = nullptr;
        node* prev = nullptr;
        // ...
    }

    node* head = nullptr;
    node* tail = nullptr;

If a class has a raw pointer (T*), consider whether it might be owning. Use std::observer_ptr<T> (C++17 library feature) or a raw pointer for non-owning pointers. Use std::unique_ptr<T> when you need to represent single-ownership.

    struct node {
        std::unique_ptr<node> next = nullptr;
        node* prev = nullptr;                 
        // ...
    }

    std::unique_ptr<node> head = nullptr;
    node* tail = nullptr;

If a class manages a resource, define a destructor. Don't rely on users manually calling a function to free resources. Destructors are designed to do this.

If you define a destructor, you probably need to define or suppress copy/move operations. Obey the rule of five and be aware how the default behavior interacts with your owned resources.

    // The compiler generated destructor will recursively destruct, which
    // is fine if you have unlimited stack space.  Otherwise, eventually
    // overflows the stack.
    //~two_way_linked_list() = default;

    ~two_way_linked_list() noexcept {
        clear();
    }

    two_way_linked_list(const two_way_linked_list& other) { /*...*/ }
    two_way_linked_list(two_way_linked_list&& other) { /*...*/ }
    two_way_linked_list& operator=(const two_way_linked_list& other) { /*...*/ }
    two_way_linked_list& operator=(two_way_linked_list&& other) { /*...*/ }

    void clear() {
        while (head) {
            head = std::move(head->next);
        }
        tail = nullptr;
    }

    friend std::ostream& operator << (std::ostream& out, two_way_linked_list<T>& obj) {
        node* temp=obj.head;
        out << "Printing the list: " << std::endl;
        while (temp) {
            out << temp->data << " ";
            temp = temp->next;
        }
        std::cout << std::endl;
        return out;
    }

Be aware of what std::endl actually does. std::endl is a stream manipulator that outputs a new line and flushes the stream. For unbuffered streams, this isn't an issue. If someone were to pass a buffered stream to this function, the flushing can wreak havoc. If your intent is to just output a new line character, then be explicit.

    out << "Printing the list: \n";
    // ...
    out << '\n';

#include only what you need. This is likely the result of dumping your library code and test driver into the same file, but #include <iostream> results in std::cout << std::endl; successfully being compiled when you actually meant out << '\n'. When providing a streaming interface, prefer including <iosfwd> instead of <iostream> to avoid injecting the statically-constructed default streams into every translation unit that includes your library code.

Provide iterators to traverse the container. Iterators will also allow your code to interface easily with other libraries like the C++ standard library, boost, etc.

    friend std::ostream& operator << (std::ostream& out, two_way_linked_list<T>& obj) {
        out << "Printing the list: \n";
        std::copy(obj.begin(), obj.end(), 
                  std::make_ostream_joiner(out, " "));
        return out << '\n';
    }

Note: std::make_ostream_joiner and std::ostream_joiner<T> are C++17 library additions. You can write your own infix iterator if you want to use it now instead of waiting.


    void push_back(T);
    void push_front(T);
    void remove(T);

Same as earlier, prefer passing templated types of unknown size by reference to const.

    void push_back(const T&);
    void push_front(const T&);
    void remove(const T&);

    bool is_empty();

Apply the container requirements to maximize reusability with existing libraries. Users will be able to reuse your container with standard library code (non-member std::begin, std::end, std::empty, std::size, etc). Use the same method names (in this case empty() instead of is_empty() and type definitions required by the C++ standard. See C++ concepts: Container.

Make member functions const by default. const-correctness allows your code to be precisely state the design intent and allows accidental changes to the observable state to be caught at compile time.

    bool empty() const;

        tail -> next = current;

Spacing may not have a syntactic meaning to the compilers, but they do have syntactic meaning for readers. Spacing is useful for differentiating and emphasizing constructs.

        // space before parens emphasizes a language construct
        while (1) { break; }

        // no space before parens emphasizes a function call
        foo(1);

Surrounding an operator with spaces is typically seen with binary operators ( +, -, ==, <, etc).

        // we usually don't put spaces on unary operators
        list.push_back(1);    // dot operator
        ++i;                  // increment operator
        if (!list.empty())    // negation operator

        // weird?
        list . push_back(1)
        ++ i;
        if (! list.empty())

It's up to you and this is an opinion, but I would recommend that you be mindful of the spacing.

        tail->next = current;

Recommended Resources:

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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