Generic Double Linked List

Question

I am a mathematician attempting to become proficient with C++. At the moment I am learning about data structures. I am trying to write a double linked list now from scratch with some help from online tutorials. I wanted to see if there is anything that I could improve. I have made similar posts with other data structures. With the enormous help everyone has given me I feel more and more confident with my coding.

Here is the header file:

#ifndef DoubleLinkedLists_h
#define DoubleLinkedLists_h
template <class T>
class DoubleLinkedLists {
private:
 struct Node {
 T data;
 Node* next;
 Node* previous;
 };
 Node* head;
 Node* tail;
public:
 // Constructors
 DoubleLinkedLists() : head(nullptr), tail(nullptr) {} // empty constructor
 DoubleLinkedLists(DoubleLinkedLists const& value); // copy constructor
 DoubleLinkedLists<T>(DoubleLinkedLists<T>&& move) noexcept; // move constuctor
 DoubleLinkedLists<T>& operator=(DoubleLinkedLists&& move) noexcept; // move assignment operator
 ~DoubleLinkedLists(); // destructor
 // Overload operators
 DoubleLinkedLists& operator=(DoubleLinkedLists const& rhs);
 friend std::ostream& operator<<(std::ostream& str, DoubleLinkedLists<T> const& data) {
 data.display(str);
 return str;
 }
 // Member functions
 void swap(DoubleLinkedLists& other) noexcept;
 void createNode(const T& theData);
 void createNode(T&& theData);
 void display(std::ostream& str) const;
 void insertHead(const T& theData);
 void insertTail(const T& theData);
 void insertPosition(int pos, const T& theData);
 void deleteHead();
 void deleteTail();
 void deletePosition(int pos);
 bool search(const T& x);
};
template <class T>
DoubleLinkedLists<T>::DoubleLinkedLists(DoubleLinkedLists const& value) : head(nullptr), tail(nullptr) {
 for(Node* loop = value->head; loop != nullptr; loop = loop->next) {
 createNode(loop->data);
 }
}
template <class T>
DoubleLinkedLists<T>::DoubleLinkedLists(DoubleLinkedLists<T>&& move) noexcept : head(nullptr), tail(nullptr) {
 move.swap(*this);
}
template <class T>
DoubleLinkedLists<T>& DoubleLinkedLists<T>::operator=(DoubleLinkedLists<T> &&move) noexcept {
 move.swap(*this);
 return *this;
}
template <class T>
DoubleLinkedLists<T>::~DoubleLinkedLists() {
 while(head != nullptr) {
 deleteHead();
 }
}
template <class T>
DoubleLinkedLists<T>& DoubleLinkedLists<T>::operator=(DoubleLinkedLists const& rhs) {
 DoubleLinkedLists copy(rhs);
 swap(copy);
 return *this;
}
template <class T>
void DoubleLinkedLists<T>::swap(DoubleLinkedLists<T>& other) noexcept {
 using std::swap;
 swap(head, other.head);
 swap(tail, other.tail);
}
template <class T>
void DoubleLinkedLists<T>::createNode(const T& theData) {
 Node* newData = new Node;
 newData->data = theData;
 newData->next = nullptr;
 if(head == nullptr) {
 newData->previous = nullptr;
 head = newData;
 tail = newData;
 }
 else {
 newData = new Node;
 newData->data = theData;
 newData->previous = tail;
 tail->next = newData;
 tail = newData;
 }
}
template <class T>
void DoubleLinkedLists<T>::createNode(T&& theData) {
 Node* newData = new Node;
 newData->data = std::move(theData);
 newData->next = nullptr;
 if(head == nullptr) {
 newData->previous = nullptr;
 head = newData;
 tail = newData;
 }
 else {
 newData = new Node;
 newData->data = std::move(theData);
 newData->previous = tail;
 tail->next = newData;
 tail = newData;
 }
}
template <class T>
void DoubleLinkedLists<T>::insertHead(const T& theData) {
 Node* newNode = new Node;
 newNode->data = theData;
 newNode->next = head;
 head->previous = newNode;
 head = newNode;
}
template <class T>
void DoubleLinkedLists<T>::insertTail(const T& theData) {
 Node* newNode = new Node;
 newNode->data = theData;
 newNode->previous = tail;
 tail->next = newNode;
 tail = newNode;
}
template <class T>
void DoubleLinkedLists<T>::insertPosition(int pos, const T& theData) {
 Node* prev = new Node;
 Node* current = head;
 Node* newNode = new Node;
 for(int i = 1; i < pos; i++) {
 prev = current;
 current = current->next;
 }
 newNode->data = theData;
 prev->next = newNode;
 newNode->next = current;
}
template <class T>
void DoubleLinkedLists<T>::display(std::ostream &str) const {
 for(Node* loop = head; loop != nullptr; loop = loop->next) {
 str << loop->data << "\t";
 }
 str << "\n";
}
template <class T>
void DoubleLinkedLists<T>::deleteHead() {
 Node* old = head;
 head = head->next;
 delete old;
}
template <class T>
void DoubleLinkedLists<T>::deleteTail() {
 Node* prev = nullptr;
 Node* current = head;
 while(current->next != nullptr) {
 prev = current;
 current = current->next;
 }
 tail = prev;
 prev->next = nullptr;
 delete current;
}
template <class T>
void DoubleLinkedLists<T>::deletePosition(int pos) {
 Node* prev = new Node;
 Node* current = head;
 for(int i = 1; i < pos; i++) {
 prev = current;
 current = current->next;
 }
 prev->next = current->next;
}
template <class T>
bool DoubleLinkedLists<T>::search(const T &x) {
 Node* current = head;
 while(current != nullptr) {
 if(current->data == x) {
 return true;
 }
 current = current->next;
 }
 return false;
}
#endif /* DoubleLinkedLists_h */

I feel like some of the functions like insertPosition(), deletePosition() I may have not linked the previous node correctly, but I am not entirely sure. Everything runs and compiles as it should.

Here is the main.cpp file:

#include <iostream>
#include "DoubleLinkedLists.h"
int main(int argc, const char * argv[]) {
 ///////////////////////////////////////////////////////////////////////////////////
 ///////////////////////////// Double Linked List //////////////////////////////////
 ///////////////////////////////////////////////////////////////////////////////////
 DoubleLinkedLists<int> obj;
 obj.createNode(2);
 obj.createNode(4);
 obj.createNode(6);
 obj.createNode(8);
 obj.createNode(10);
 std::cout<<"\n--------------------------------------------------\n";
 std::cout<<"---------------Displaying All nodes---------------";
 std::cout<<"\n--------------------------------------------------\n";
 std::cout << obj << std::endl;
 std::cout<<"\n--------------------------------------------------\n";
 std::cout<<"----------------Inserting At Start----------------";
 std::cout<<"\n--------------------------------------------------\n";
 obj.insertHead(50);
 std::cout << obj << std::endl;
 std::cout<<"\n--------------------------------------------------\n";
 std::cout<<"-----------------Inserting At End-----------------";
 std::cout<<"\n--------------------------------------------------\n";
 obj.insertTail(20);
 std::cout << obj << std::endl;
 std::cout<<"\n--------------------------------------------------\n";
 std::cout<<"-------------Inserting At Particular--------------";
 std::cout<<"\n--------------------------------------------------\n";
 obj.insertPosition(5,60);
 std::cout << obj << std::endl;
 std::cout<<"\n--------------------------------------------------\n";
 std::cout<<"----------------Deleting At Start-----------------";
 std::cout<<"\n--------------------------------------------------\n";
 obj.deleteHead();
 std::cout << obj << std::endl;
 std::cout<<"\n--------------------------------------------------\n";
 std::cout<<"----------------Deleting At End-----------------";
 std::cout<<"\n--------------------------------------------------\n";
 obj.deleteTail();
 std::cout << obj << std::endl;
 std::cout<<"\n--------------------------------------------------\n";
 std::cout<<"--------------Deleting At Particular--------------";
 std::cout<<"\n--------------------------------------------------\n";
 obj.deletePosition(4);
 std::cout << obj << std::endl;
 std::cout << std::endl;
 obj.search(8) ? printf("Yes"):printf("No");
 return 0;
}

• yuri: Missing a few includes, which compiler are you using? It also leaks memory.
• Snorrlaxxx: @yuri I am using Xcode, where does it leak memory?
• yuri: The main culprits are createNode, insertPosition and deletePosition
• Snorrlaxxx: @yuri They leak memory or is the implementation wrong or both?

Answer 1

Memory Leaks

At a first glance the double use of new without any nearby delete is suspicious. Let's look at createNode first:

Node* newData = new Node;
newData->data = theData;
newData->next = nullptr;

This first part is always executed, allocating a new Node.

Now if head is not nullptr you allocate another new Node:

if(head == nullptr) {
 newData->previous = nullptr;
 head = newData;
 tail = newData;
}
else {
 newData = new Node;
 newData->data = theData;
 newData->previous = tail;
 tail->next = newData;
 tail = newData;
}

You just lost any reference to your first Node and have no way to clean it up anymore.
Also as a user of this function you don't know what it does without looking at the implementation because the name certainly doesn't tell you. Will it insert at the front? The back? In the middle? No idea.
I would scrap the entire function or merge it into insertTail.

Furthermore don't compare to nullptr. Use the implicit conversion and simply do if (head) and for the inverse if (!head).

---

The next function with double new and no delete in sight is insertPosition.
What is even going on here? Why allocate new memory for the previous node? Why allocate the new node before you found the right spot? What if it fails now? Memory leaks for everyone.
Consider something like the following:

Node* cur_node = head;
int i = 0;
while (cur_node) {
 if (i++ == pos) {
 // do the deed
 }
 cur_node = cur_node->next;
}

No need to allocate any memory before you found the right position to insert at. (note: here the postfix operator is intentional but usually you should prefer the prefix version)

---

No double new but still a problem child: deletePosition

Again, why make a new node for prev? The approach from above applies here as well.

---

Well those functions didn't work out too well but the others are fine right? No.

Let's look at insertHead as an example of what is wrong with most of the other functions.

Node* newNode = new Node;
newNode->data = theData;
newNode->next = head;
head->previous = newNode;
head = newNode;

See the problem?
Assume the list is empty and head is nullptr

newNode->next = head;
head->previous = newNode;

Now this will crash and burn.
This issue of not checking for valid nodes can be found in other functions as well.

General

Dump the comments, they don't help. In fact they're wrong as they claim some code is constructors when it also includes an overloaded assignment operator and even a destructor.

head and tail can be initialized directly in the class.

Generally you should order your interface from public to private and not the other way around.

Naming is really inconsistent. You have value, move, other, rhs. Not really wrong but confusing. Which one you pick is mostly a matter of personal preference but do pick one and stick with it. Consistency is key.

For the operator<< overload the display function should probably be private. Right now you can do std::cout << obj as well as obj.display(std::cout), kinda weird.

You're missing includes. At least <ostream> and <utility>.

• Snorrlaxxx: Thank you for the points you made. I will try to correct it and make the appropriate changes. For the createNode, I should call it push_back. I removed the first two lines where I create a new node. I did the following: newData->previous = tail; tail->next = newData; tail = newData; Since I thought this would be the correct way to link the previous node to the node before it thus the tail portion of the list. Could you show me the correct way of implementing this?
• yuri: @Snorrlaxxx (1) push_back and insertTail can be merged. Take a look at std::list. It has only 3 functions for inserting (not counting emplace variants). If you're feeling adventurous you can use iterators for your insertPosition function. (2) I mistakingly believed you were trying to add to the front. It's probably fine as is. I'll redact my answer accordingly.
• Snorrlaxxx: My apologies for not accepting sooner, I am in Sweden at the moment. I just made some changes to the createNode function. Although, when I take away the comparison of head == nullptr I get a "Thread 1: EXC_BAD_ACCESS (code=1, address=0x8)" at the tail->next = newData part of the code. Thus, I may need to keep it. I am going to move on to the rest of your comments and make the appropriate changes. Once I am finished I will make a new post.
• Snorrlaxxx: Also, I am not sure what to do in the // do the deed part of the insertPosition. Could you expand that answer?
• yuri: @Snorrlaxxx That's simply where you create the new node and link it into the rest of the list.