6
\$\begingroup\$

This follows from a post I made here. I made changes according to the answer I accepted in the following link. I tried to make all the changes necessary that I could. I just want to see if there are any other further adjustments that I need to have for this generic single linked list.

Here is my header file:

#ifndef LinkedList_hpp
#define LinkedList_hpp

#include <iostream>


template<class T>
class SingleLinkedList {
private:

    template<class S>
    struct Node {
        S data;
        Node<S>* next;
    };

    Node<T>* head;
    Node<T>* tail;



public:
    SingleLinkedList() : head(nullptr), tail(nullptr) {}

    SingleLinkedList(SingleLinkedList const& value) : head(nullptr), tail(nullptr) {
        for(Node<T>* loop = value->head; loop != nullptr; loop = loop->next) {
            createNode(loop->data);
        }
    }

    SingleLinkedList& operator=(SingleLinkedList const& rhs) { SingleLinkedList copy(rhs);}

     void swap(SingleLinkedList& other) noexcept {
         using std::swap;
         swap(head, other.head);
         swap(tail, other.tail);
     }

    ~SingleLinkedList(){
        Node<T>* nodePtr = head;
        while(nodePtr != nullptr) {
            Node<T>* nextNode = nodePtr->next;
            nodePtr = nextNode;
            delete nodePtr;
        }
    }

    void createNode(const T&& theData) {
        Node<T>* temp = new Node<T>;
        temp->data = std::move(theData);
        temp->next = nullptr;
        if(head == nullptr) {
            head = temp;
            tail = temp;
            temp = nullptr;
        }
        else {
            tail->next = temp;
            tail = temp;
        }
    }

    void display(std::ostream& str = std::cout) {
        Node<T>* temp = head;
        while(temp != nullptr) {
            str << temp->data << "\t";
            temp = temp->next;
        }
        delete temp;
    }

    void insert_start(const T& theData) {
        Node<T>* temp = new Node<T>;
        temp->data = theData;
        temp->next = head;
        head = temp;
        delete temp;
    }

    void insert_position(int pos, const T& theData) {
        Node<T>* previous = new Node<T>;
        Node<T>* current = new Node<T>;
        Node<T>* temp = new Node<T>;
        current = head;
        for(int i  = 1; i < pos; i++) {
            previous = current;
            current = current->next;
        }
        temp->data = theData;
        previous->next = temp;
        temp->next = current;
    }

    void delete_first() {
        Node<T>* temp = head;
        head = head->next;
        delete temp;
    }

    void delete_last() {
        Node<T>* previous = nullptr;
        Node<T>* current = nullptr;
        current = head;
        while(current->next != nullptr) {
            previous = current;
            current = current->next;
        }
        tail = previous;
        previous->next = nullptr;
        delete current;
    }

    void delete_position(int pos) {
        Node<T>* previous = new Node<T>;
        Node<T>* current = new Node<T>;
        current = head;
        for(int i = 1; i < pos; i++) {
            previous = current;
            current = current->next;
        }
        previous->next = current->next;
    }

    bool search(const T& x) {
        struct Node<T>* current = head;  
        while (current != NULL) {
            if (current->data == x)
                return true;
            current = current->next;
        }
        return false;
    }

    friend std::ostream& operator<<(std::ostream& str, SingleLinkedList& data) {
        data.display(str);
        return str;
    }
};

#endif /* LinkedList_hpp */

Here is the main.cpp file that tests this header file:

#include <iostream>
#include "LinkedList.hpp"


int main(int argc, const char * argv[]) {

    SingleLinkedList<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 End-----------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.createNode(55);
    std::cout << obj << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"----------------Inserting At Start----------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.insert_start(50);
    std::cout << obj << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"-------------Inserting At Particular--------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.insert_position(5,60);
    std::cout << obj << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"----------------Deleting At Start-----------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.delete_first();
    std::cout << obj << std::endl;

    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"----------------Deleting At End-----------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.delete_last();
    std::cout << obj << std::endl;


    std::cout<<"\n--------------------------------------------------\n";
    std::cout<<"--------------Deleting At Particular--------------";
    std::cout<<"\n--------------------------------------------------\n";
    obj.delete_position(4);
    std::cout << obj << std::endl;
    std::cout << std::endl;

    obj.search(8) ? std::cout << "Yes" << std::endl : std::cout << "No" << std::endl;;



    return 0;
}
\$\endgroup\$
7
\$\begingroup\$

Code Review

Header guards are not the same as the class name.
Also there is not namespace.

#ifndef LinkedList_hpp
#define LinkedList_hpp

Now that you have the Node inside the SingleLinkedList it does not need to be seprately templated.

template<class T>
class SingleLinkedList {
private:

    template<class S>
    struct Node {
        S data;
        Node<S>* next;
    };

    Node<T>* head;
    Node<T>* tail;

Simplify to this:

template<class T>
class SingleLinkedList {
private:

    struct Node {
        T data;
        Node* next;
    };


    Node* head;
    Node* tail;

This seems to be missing a swap (and a return).

    SingleLinkedList& operator=(SingleLinkedList const& rhs)
    {
        SingleLinkedList copy(rhs);
        // After you make a copy you need to swap the copy with
        // the current value to change this.
        // swap(copy);

        // This needs a return statement.
        // return *this;
    }

Good try at the destructor.
But there seems to be an ordering issue.

    ~SingleLinkedList(){
        Node<T>* nodePtr = head;
        while(nodePtr != nullptr) {
            Node<T>* nextNode = nodePtr->next;

            // You should delete nodePtr here.
            // Then once you have deleted you can move to
            // the next item in the chain by assigning
            // nextNode to nodePtr

            nodePtr = nextNode;

            // To fix simply move this delete above the previous line
            delete nodePtr;
        }
    }

Move semantics are a compliment to normal semantics. Things can not always be moved. So you should do this in addition to the normal copy version not instead of.

    void createNode(const T&& theData) {

So I would have both functions:

    void createNode(const T& theData)
    void createNode(T&& theData)

Note: The && is not used with const as you destroy the internal content as part of the move operation.

You don't want to delete in display().
Also the display can be marked const as it should not change the state of the object.

    void display(std::ostream& str = std::cout) const {
                                             // ^^^^^  add const to mark the function as non mutating.
        Node<T>* temp = head;
        while(temp != nullptr) {
            str << temp->data << "\t";
            temp = temp->next;
        }

        // This line is not needed.
        // You did not create anything so you don't need
        // to delete it.
        delete temp;
    }

No need to delete in insert_start() as you delete in the destructor.

    void insert_start(const T& theData) {
        Node<T>* temp = new Node<T>;
        temp->data = theData;
        temp->next = head;
        head = temp;

        // Remove this.    
        delete temp;
    }

IF the list is empty then this is a problem.

    void delete_first() {
        Node<T>* temp = head;
        head = head->next;
        delete temp;
    }

Normally we have a method called empty() that allows us to check if the list is empty before deleting.

   bool empty() const {return head == nullptr;}

Now a user is responsable for checking before a call to delete.

   while(!list.empty()) {
      list.delete_first();
   }

You remove the item from the list here.
But I don't see a call to delete so I suspect you are leaking a node here.

    void delete_position(int pos) {
        Node<T>* previous = new Node<T>;
        Node<T>* current = new Node<T>;
        current = head;
        for(int i = 1; i < pos; i++) {
            previous = current;
            current = current->next;
        }
        previous->next = current->next;
    }

Reference

Here is basic reference implementation I came up with using your code as a base:

#include <ostream>
#include <utility>

namespace ThorsAnvil
{
    template<typename T>
    class SinglyLinkedList
    {
        struct Node
        {
            T       data;
            Node*   next;
        };
        Node* head;
        Node* tail;

        public:
            SinglyLinkedList()
                : head(nullptr)
                , tail(nullptr)
            {}
            ~SinglyLinkedList()
            {
                while(head != nullptr) {
                    deleteHead();
                }
            }

            SinglyLinkedList(SinglyLinkedList const& copy)
                : SinglyLinkedList()
            {
                for(Node* loop = copy.head; loop != nullptr; loop = loop->next) {
                    addTail(loop->data);
                }
            }
            SinglyLinkedList& operator=(SinglyLinkedList const& rhs)
            {
                SinglyLinkedList    copy(rhs);
                swap(copy);
                return *this;
            }
            SinglyLinkedList(SinglyLinkedList&& move) noexcept
                : SinglyLinkedList()
            {
                swap(move);
            }
            SinglyLinkedList& operator=(SinglyLinkedList&& move) noexcept
            {
                swap(move);
                return *this;
            }
            void swap(SinglyLinkedList& other) noexcept
            {
                using std::swap;
                swap(head, other.head);
                swap(tail, other.tail);
            }
            friend void swap(SinglyLinkedList& lhs, SinglyLinkedList& rhs)
            {
                lhs.swap(rhs);
            }
            void addTail(T const& value)
            {
                Node* newValue = new Node{value, nullptr};
                if (tail != nullptr) {
                    tail->next = newValue;
                }
                tail = newValue;
                if (head == nullptr) {
                    head = newValue;
                }
            }
            void addHead(T const& value)
            {
                Node* newValue = new Node{value, head};
                head = newValue;
                if (tail == nullptr) {
                    tail = newValue;
                }
            }
            // Assumes there is data in list.
            // Users responsibility to validate by calling empty()
            void deleteHead()
            {
                Node* old = head;
                head = head->next;
                delete old;
            }
            // Assumes there is data in list.
            // Users responsibility to validate by calling empty()
            void deleteTail()
            {
                Node* prev = nullptr;
                Node* curr = head;
                while(curr->next != nullptr) {
                    prev = curr;
                    curr = curr->next;
                }
                tail = prev;
                if (prev == nullptr) {
                    head = nullptr;
                }
                else {
                    prev->next = nullptr;
                }
                delete curr;
            }
            bool empty() const {return head == nullptr;}

            void display(std::ostream& str) const
            {
                for(Node* loop = head; loop != nullptr; loop = loop->next) {
                    str << loop->data << "\t";
                }
                str << "\n";
            }
            friend std::ostream& operator<<(std::ostream& str, SinglyLinkedList const& data)
            {
                data.display(str);
                return str;
            }
    };
}
\$\endgroup\$
  • \$\begingroup\$ Thank you for your speedy reply back. I have now implemented all the changes you have recommended except for namespace. Should I make an additional last post to wrap all this up? Thanks again. \$\endgroup\$ – Snorrlaxxx May 23 '18 at 19:37
  • \$\begingroup\$ One comment, I am getting a "Thread 1: signal SIGABRT" error on the line where I delete the nodePtr in my destructor. Any idea how to resolve that issue? \$\endgroup\$ – Snorrlaxxx May 23 '18 at 19:44
  • \$\begingroup\$ Did you add the fix I suggested for the destructor. \$\endgroup\$ – Martin York May 23 '18 at 21:36
  • 1
    \$\begingroup\$ Note: If you use delete_first() when the list is empty you will get an error. As you de-reference the head. \$\endgroup\$ – Martin York May 24 '18 at 21:04
  • 1
    \$\begingroup\$ The move version (r-value reference) will be used when you pass an object that is an r-value reference. A r-value reference is usually an un-named value (ie not a variable but the result of an expression or a literal). createNode(5) here 5 is an r-value reference as it is not a named value. int x= 1; createNode(x); will call the standard version as x is a named variable. int x= 1; createNode(std::move(x)); will call the rvalue reference as the value passed to createNode() is the result of an expression std::move(x) and thus is not a named value. \$\endgroup\$ – Martin York May 24 '18 at 21:06
1
\$\begingroup\$

Building on Martin’s answer:

    Node* head;
    Node* tail;

    public:
        SinglyLinkedList()
            : head(nullptr)
            , tail(nullptr)
        {}

Just use default initializers.

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

Then you do not need to write the default constructor at all.


Don’t write explicit tests against nullptr.

Don’t have naked new/delete.

Your list doesn’t do anything except display. It should have some general purpose means of accessing the values, traversing the list. And then display can be written using that public API.

\$\endgroup\$
  • \$\begingroup\$ What do you mean my list does not do anything? I wrote all the member functions for insert, delete, search, etc. \$\endgroup\$ – Snorrlaxxx May 24 '18 at 21:38

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.