3
\$\begingroup\$

This is a continuation from the previous post found here. I made most of the changes that was suggested. I just want to see if there are any additional changes I should make to my code.

Here is my 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->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->previous = tail;
        tail->next = newData;
        tail = newData;
    }
}

template <class T>
void DoubleLinkedLists<T>::insertHead(const T& theData) {
    Node* newNode = new Node;
    newNode->data = theData;
    if(head != nullptr) {
        newNode->next = head;
        head->previous = newNode;
        head = newNode;
    }
    else {
        std::cout << "The list is empty" << std::endl;
    }
}

template <class T>
void DoubleLinkedLists<T>::insertTail(const T& theData) {
    Node* newNode = new Node;
    newNode->data = theData;
    if(tail != nullptr) {
        newNode->previous = tail;
        tail->next = newNode;
        tail = newNode;
    }
    else {
        std::cout << "The list is empty" << std::endl;
    }
}

template <class T>
void DoubleLinkedLists<T>::insertPosition(int pos, const T& theData) {
    Node* current = head;
    int i = 0;
    while (current != nullptr) {
        if (i++ == pos) {
            Node* newNode = new Node;
            newNode->data = theData;
            // Let's do the wiring
            newNode->previous = current->previous;
            newNode->next = current;
            if (newNode->previous != nullptr) {  // If the node is inserted at the end
                newNode->previous->next = newNode;
            }
            current->previous = newNode;
            return;
        }
        current = current->next;
    }
}

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() {
    if(head != nullptr) {
        Node* old = head;
        head = head->next;
        delete old;
    }
    else {
        std::cout << "The list is empty" << std::endl;
    }
}

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 */

Here is the main.cpp file that tests the latter above class:

#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(5);
    std::cout << obj << std::endl;
    std::cout << std::endl;

    obj.search(8) ? printf("Yes"):printf("No");






    return 0;
}
\$\endgroup\$
4
\$\begingroup\$
  • DRY. The code would greatly benefit from the Node(const T& data) and Node(const T&& data) constructors.

  • createNode does not just create a node. It also append it to the list. Call it append (or insertTail, because their functionality is really identical).

  • Streamline createNode:

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

    newData seems like a typo; it should be newNode.

  • insertPosition may insert at the beginning or at the end, but fails to update head or tail.

  • Inability to insertHead and insertTail into an empty list is surprising.

  • deleteTail fails on the empty list. Ditto deletePosition.

  • deletePosition does not update current->next->previous. Also, it does not actually delete anything, aka leaks memory.

\$\endgroup\$
  • 1
    \$\begingroup\$ Aggregate initialization should remove the need for vale constructor. I believe it would require defaulting pointers to nullptr though. \$\endgroup\$ – Incomputable Jun 14 '18 at 1:05
  • \$\begingroup\$ @Incomputable Very good point. \$\endgroup\$ – vnp Jun 14 '18 at 3:24
  • \$\begingroup\$ For the insertPosition function how do I update head or tail in the code? \$\endgroup\$ – Snorrlaxxx Jun 15 '18 at 14:36
  • \$\begingroup\$ Hey could you answer a few of my questions I have and then I will gladly reaccept your answer? \$\endgroup\$ – Snorrlaxxx Jun 16 '18 at 23:03
3
\$\begingroup\$

Use default initializers in-line in the class:

Node* head = nullptr;
Node* tail = nullptr;

and then you don’t need to mention them in every constructor.


friend std::ostream& operator<<(std::ostream& str, DoubleLinkedLists<T> const& data) {
    data.display(str);
    return str;
}

Why is that given friendship? Accessing all the values in the list is an essential public ability, and that’s all display needs to do.


But wait…

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

You can add data to the front or back or (? what does createNode do?), or at a numbered position. You can delete the first, last, or numbered position. You can search and it just returns true/false, not any position info.

So what good is it? You can add stuff, but can’t traverse the list? You can add at some position, but what position would you add to, since there is nothing to tell you what items are where already?


while (current != nullptr) {
    if (i++ == pos) {

Prefer prefix over postfix

Don’t make explicit comparisons against nullptr. Use the contextual truth value provided by the class — important when you start using smart pointers and other pointer-like things.

        Node* newNode = new Node;
        newNode->data = theData;

Well, this leaks memory if the assignment throws an exception. Trivial to avoid by using unique_ptr to hold it locally.

And why are you default-constructing the data item first, and then assigning over it? You should initialize it as it is created.

auto newNode= make_unique<Node>(theData);

(and of course the constructor for Node needs to pass the parameter through)


Your two versions of create_node are nearly identical! Do Not practice copy/paste programming!! If something is the same, don’t duplicate it — reuse it or generalize it.

Here, it is easy to make the node creation a separate step, and then call a common function that both versions use to hook it in.


obj.search(8) ? printf("Yes"):printf("No");

Is that C library printf? Why would you use that without any need for formatting, and why mix C i/o with all the std::cout you were using?

BTW, operator<< on bool can optionally display the strings “true”/“false” instead of numbers.


Prefer using \n over std::endl


Good luck! So many people never learn how the elementary data structures actually work, these days.

\$\endgroup\$
  • \$\begingroup\$ I re-submitted a follow up as the latter person who's answer I accepted did not answer any of the follow up questions I have. I want to fix my class but I am pretty stuck, could you help? \$\endgroup\$ – Snorrlaxxx Jun 25 '18 at 22:57
  • \$\begingroup\$ How do you update head and tail? I don’t follow what you want to know. You already know how the pointers are used to create the linked list. \$\endgroup\$ – JDługosz Jun 26 '18 at 18:15
  • \$\begingroup\$ I got that part to work and updated head and tail. I am referring to the "DRY. The code would greatly benefit from the Node(const T& data) and Node(const T&& data) constructors." and some others. I deleted the new post since it received such negative reviews. \$\endgroup\$ – Snorrlaxxx Jun 27 '18 at 0:59
  • \$\begingroup\$ vpn was referring to code replication: Don’t Repeat Yourself. I think he’s saying that having proper constructors in the Node class will simplify the code that is manipulating the nodes. \$\endgroup\$ – JDługosz Jun 29 '18 at 17:41

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.