Doubly Linked List Data Structure ADT in C++

Question

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
```

• user228914: Side note, why do you limit to C++11?
• Guy on the Internet: @Aryan Parekh "Because that's what I know atm"

Answer 1

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

• Deduplicator: As an aside: "What's the difference between "STL" and "C++ Standard Library"? "

Answer 2

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.