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;
}

Missing a few includes, which compiler are you using? It also leaks memory. — yuri
– yuri, Commented Jun 5, 2018 at 18:24
The main culprits are createNode, insertPosition and deletePosition — yuri
– yuri, Commented Jun 5, 2018 at 18:36
@yuri They leak memory or is the implementation wrong or both? — Snorrlaxxx
– Snorrlaxxx, Commented Jun 6, 2018 at 4:54

yuri · Accepted Answer · 2018-06-06 15:08:22Z

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

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? — Snorrlaxxx
– Snorrlaxxx, Commented Jun 6, 2018 at 13:19
@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. — yuri
– yuri, Commented Jun 6, 2018 at 15:07
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
– Snorrlaxxx, Commented Jun 11, 2018 at 9:33
Also, I am not sure what to do in the // do the deed part of the insertPosition. Could you expand that answer? — Snorrlaxxx
– Snorrlaxxx, Commented Jun 11, 2018 at 9:42
@Snorrlaxxx That's simply where you create the new node and link it into the rest of the list. — yuri
– yuri, Commented Jun 11, 2018 at 12:29

Stack Exchange Network

Generic Double Linked List

1 Answer 1

You must log in to answer this question.

Linked

Hot Network Questions

Generic Double Linked List

1 Answer 1

You must log in to answer this question.

Linked

Related

Hot Network Questions