trjhtr

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;

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