TransWikia.com

Doubly Linked List Data Structure ADT in C++

Code Review Asked by Guy on the Internet on January 5, 2021

I’m trying to implement a Doubly Linked List data structure in C++. Please give me suggestions on how this code can be improved. Try to remain in C++11 because that’s what I know atm.

#ifndef DOUBLY_LINKED_LIST_HPP
#define DOUBLY_LINKED_LIST_HPP

#include <iostream>

template <typename T>
class DoublyLinkedList {

    template <typename T>
    struct Node {
        T val;
        Node<T>* next;
        Node<T>* prev;
    };

public:
    DoublyLinkedList() : len(0), head(nullptr), tail(nullptr)
    {
    }

    DoublyLinkedList(const DoublyLinkedList& rhs) : DoublyLinkedList()
    {
        Node<T>* currNode = rhs.head;
        while (currNode) {
            this->PushBack(currNode->val);
            currNode = currNode->next;
        }
    }

    DoublyLinkedList(DoublyLinkedList&& rhs) : head(rhs.head), tail(rhs.tail), len(rhs.len)
    {
        rhs.head = rhs.tail =  nullptr;
    }

    DoublyLinkedList& operator=(DoublyLinkedList rhs)
    {
        swap(*this, rhs);
        return *this;
    }

    ~DoublyLinkedList()
    {
        this->Clear();
    }

    const T& GetFront() const
    {
        return head->val;
    }

    const T& GetBack() const
    {
        return tail->val;
    }

    size_t GetLength() const
    {
        return len;
    }

    void PushFront(const T& val)
    {
        Node<T>* newNode = new Node<T>{ val, head, nullptr };

        if (tail == nullptr) {
            tail = newNode;
        }
        else {
            head->prev = newNode;
        }

        head = newNode;
        ++len;
    }

    void PushBack(const T& val)
    {
        Node<T>* newNode = new Node<T>{ val, nullptr, tail };

        if (head == nullptr /*&& tail == nullptr*/) {
            head = newNode;
        }
        else {
            tail->next = newNode;
        }

        tail = newNode;
        ++len;
    }

    void InsertAt(size_t idx, const T& val)
    {
        Node<T>* currNode = head;

        while (idx--) {
            currNode = currNode->next;
        }

        if (currNode == tail || currNode == nullptr) {
            this->PushBack(val);
        }
        else if (currNode == head) {
            this->PushFront(val);
        }
        else {
            Node<T>* newNode = new Node<T>{ val, currNode, currNode->prev };
            currNode->prev->next = newNode;
            currNode->prev = newNode;
        }
    }


    T PopFront()
    {
        T val = std::move(head->val);
        Node<T>* newHead = head->next;

        delete head;

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


        head = newHead;
        --len;

        return val;
    }



    T PopBack()
    {
        T val = std::move(tail->val);
        Node<T>* newTail = tail->prev;

        delete tail;

        if (newTail) {
            newTail->next = nullptr;
        }
        else {
            head = nullptr;
        }

        tail = newTail;
        --len;

        return val;
    }

    T RemoveAt(size_t idx)
    {
        Node<T>* currNode = head;

        while (idx--) {
            currNode = currNode->next;
        }

        if (currNode == tail || currNode == nullptr) {
            return this->PopBack();
        }
        else if (currNode == head) {
            return this->PopFront();
        }
        else {
            T val = std::move(currNode->val);
            currNode->prev->next = currNode->next;
            currNode->next->prev = currNode->prev;

            delete currNode;

            return val;
        }
    }

    void Clear() 
    {
        Node<T>* currNode = head;

        while (currNode) {
            Node<T>* nextNode = currNode->next;
            delete currNode;
            currNode = nextNode;
        }

        this->head = this->tail = nullptr;
        this->len = 0;
    }

    friend std::ostream& operator<< (std::ostream& out, const DoublyLinkedList<T>& list)
    {
        out << "DoublyLinkedList{";
        Node<T>* currNode = list.head;
        while (currNode) {
            std::cout << currNode->val;

            if (currNode->next) std::cout << ", ";

            currNode = currNode->next;
        }

        out << "}";
        return out;
    }

    friend void swap(DoublyLinkedList<T>& lhs, DoublyLinkedList<T>& rhs)
    {
        std::swap(lhs.head, rhs.head);
        std::swap(lhs.tail, rhs.tail);
        std::swap(lhs.len, rhs.len);

        return;
    }

private:
    Node<T>* head;
    Node<T>* tail;
    size_t len;
};


#endif
```
c++c++11linked listreinventing the wheeltemplate

2 Answers

Wrap your class in a namespace

Just like the STL has its containers in the std:: namespace, it's a good practice to wrap your containers in your personal namespace too. That way you group related classes and functions together.

Node<T> Node

template <typename T>
class DoublyLinkedList 

    template <typename T>
    struct Node {
        T val;
        Node<T>* next;
        Node<T>* prev;
    };

There is a problem here, you don't need to write out another template for Node since it uses the same type that DoublyLinkedList uses. Due to this, you had to write Node < T > everywhere, except if Node didn't have its template, you could do Node alone

template < typename T >
class DoublyLinkedList
{
    struct Node {
        T val;
        Node* next; // don't require Node < T >*
        Node* prev;
    };

This replaces every Node < T > with Node in your program

 Node<T>* newNode = new Node<T>{ val, head, nullptr };
 Node* newNode = new Node{val, head, nullptr};

Unnecessary this->

   ~DoublyLinkedList()
    {
        this->Clear();
    }

this-> is completely unnecessary here, you don't have to use it everywhere unless you have a good reason.

   ~DoublyLinkedList()
    {
        Clear();
    }

Use an rvalue reference

An lvalue reference in your program already avoids a copy, with an rvalue reference you can make it even more efficient because we know that it's a temporary object, hence we can use std::move and treat an rvalue reference differently

    void PushFront(T const& val) // this remains the same
    {
        Node* newNode = new Node{ val, head, nullptr };

        if (tail == nullptr) {
            tail = newNode;
        }
        else {
            head->prev = newNode;
        }

        head = newNode;
        ++len;
    }

    void PushFront(T&& val) // overload for an rvalue reference
    {
        Node* newNode = new Node{ std::move(val), head, nullptr };

        if (tail == nullptr) {
            tail = newNode;
        }
        else {
            head->prev = newNode;
        }

        head = newNode;
        ++len;
    }

Constructor with std::initializer_list

Defined in header <initializer_list>

A constructor with this will make initializing your list much easier. Once you add a constructor that supports an initializer_list, you can create a list in the following manner

DoublyLinkedList < int > l { 1, 2, 3, 4, 5}; // ?

DoublyLinkedList < int > l2;

l2.PushBack(1);
l2.PushBack(2);
l2.PushBack(3);
l2.PushBack(4);
l2.PushBack(5); // ?

DoublyLinkedList( std::initializer_list < T > const& init); // iterate and add elements

PopBack() on an empty list

Your pop functions don't handle this exception at all, the best thing to do is use assert to deal with this, if you look at the implementation of pop_back() in std::list, it does the same

    void pop_back() noexcept {
#if _CONTAINER_DEBUG_LEVEL > 0
        _STL_VERIFY(_Mypair._Myval2._Mysize != 0, "pop_back called on empty list");
#endif 

        _Unchecked_erase(_Mypair._Myval2._Myhead->_Prev);
    }

Extending your class

A few things which you can add

  • empty() returns whether the list is empty
  • overload of the equality operator == to check if two lists are equal
  • merge two lists

Naming conventions

Consider matching the function names in the STL

PopBack() -> pop_back()
PushBack() -> push_back()
GetLength() -> size()

I also suggest you take change DoublyLinkedList to something like List because the declaration gets really strange

DoublyLinkedList < DoublyLinkedList < int > > my_list;

I again recommend you wrap everything in your own namespace, that way you don't have to afraid of collisions

Correct answer by Aryan Parekh on January 5, 2021

  1. The InsertAt() and RemoveAt() operations are quite expensive when implemented to accept a position. These operations are usually implemented using iterators, which are wrappers around the internal node structure.

  2. Making the stream output operator part of the class is rather inflexible. You should define a standalone non-friend function to help you dump your list. To do that non-friendliness, however, you need access to the internal node structure. But this problem fades away if you implement the iterators.

  3. Generally, you might want to comply with the concept of the standard containers. Use the same method names (ie. size(), push_back()), etc.

  4. Also, I'm not sure but maybe a standard std::swap is going to be enough and actually more efficient. Definitely, the return on the end of void function is useless.

Answered by slepic on January 5, 2021

Add your own answers!

Ask a Question

Get help from others!

Recent Answers

Recent Questions

© 2024 TransWikia.com. All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP