Single Linked List - simple approach

Question

I am a student, trying to learn C++11 and data structures. I would like to ask you to to review my code. I have spent some time and analyse similar questions on Code Review and it gave me basic idea what I should pay attention to.

I have learnt about the rule of three, but I am not sure if my implementation is correct, especially = operator.

I would be grateful if someone more experienced than me could check it. I would like to improve my programming skills.

EDIT: I didn't expect that stdexcept is required. On my local machine it compiles without that library... (Linux, eclipse, c++11 flag added). I am confused, sorry.

Code:

#include <iostream>
#include <stdexcept>

template <typename T>
class SingleLinkedList{
private:
    struct Node{
        T data;
        Node * next;
        Node() : next(nullptr) {}
        Node(const T num) : data(num), next(nullptr) {}
    };

private:
    Node * head;
    Node * tail;

public:
    SingleLinkedList();                                             // constructor
    ~SingleLinkedList();                                            // destructor
    SingleLinkedList(const SingleLinkedList &oldList);              // copy constructor
    SingleLinkedList& operator=(const SingleLinkedList &oldList);   // copy assignment operator

    void insert(T const& value);
    void displayList(std::ostream& stream = std::cout) const;
    void pushFront(T value);
    void pushBack(T value);
    void pushAtPosition(int position, T value);
    void popFront();
    void popBack();
    void popAtPosition(int position);
    int getLength();
    int getValue(int position);
    Node * search(T value);

};

template <typename T>
SingleLinkedList<T>::SingleLinkedList() : head(nullptr), tail(nullptr){
    std::cout << "Constructor called..." << std::endl;
}

template <typename T>
SingleLinkedList<T>::~SingleLinkedList(){
    std::cout << "Destructor called..." << std::endl;
    int index = 1;
    Node * temp = nullptr;
    while(head!=nullptr){
        temp = head;
        head = head->next;
        delete temp;
        //std::cout << "Node number: " << index << " destroyed" << std::endl;
        index++;
    }
}

template <typename T>
SingleLinkedList<T>::SingleLinkedList(const SingleLinkedList<T> &oldList){
    std::cout << "Copy constructor..." << std::endl;

    // is it necessary? my constructor by default initializes head and tail with nulls
    this->head = nullptr;
    this->tail = nullptr;

    Node * temp = nullptr;
    temp = oldList.head;

    while(temp!=nullptr){
        this->insert(temp->data);
        temp = temp->next;
    }
}

template <typename T>
SingleLinkedList<T>& SingleLinkedList<T>::operator=(const SingleLinkedList &oldList){
    std::cout << "Copy assignment operator..." << std::endl;

    if(this != &oldList){
        // delete previous content
        this->~SingleLinkedList();

        // copy all nodes from oldList to newList
        Node * temp = nullptr;
        temp = oldList.head;

        while(temp!=nullptr){
            this->insert(temp->data);
            temp = temp->next;
        }
    }
    return *this;
}

template <typename T>
void SingleLinkedList<T>::insert(T const& value){
    Node * temp = new Node(value);
    //temp->data = value;
    //temp->next = nullptr;


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

template <typename T>
void SingleLinkedList<T>::displayList(std::ostream& stream) const{
    Node * temp = nullptr;
    temp = head;

    while(temp!=nullptr){
        stream << temp->data << " -> ";
        temp = temp->next;
    }
    stream << std::endl;
}

template <typename T>
void SingleLinkedList<T>::pushFront(T value){
    Node * temp = new Node;
    temp->next = head;
    temp->data = value;
    head = temp;
}


template <typename T>
void SingleLinkedList<T>::pushBack(T value){
    Node * temp = new Node;
    tail->next = temp;
    tail = temp;
    temp->data = value;
}

template <typename T>
void SingleLinkedList<T>::pushAtPosition(int position, T value){
    Node * temp = new Node;
    Node * previous = nullptr;
    Node * current = nullptr;

    if(position < 1){
        std::cout << "Invalid index" << std::endl;
        throw std::out_of_range("Invalid index");
    }
    if(position > getLength()){
        std::cout << "Invalid index" << std::endl;
        throw std::out_of_range("Invalid index");
    }
    if(position == 1){
        pushFront(value);
        return;
    }

    if(position == getLength()){
        pushBack(value);
        return;
    }

    current = head;

    for(int i=1; i<position; i++){
        previous = current;
        current = current->next;
    }
    previous->next = temp;
    temp->next = current;
    temp->data = value;
}

template <typename T>
void SingleLinkedList<T>::popFront(){
    Node * temp = nullptr;
    temp = head;
    head = temp->next;
    delete temp;
}

template <typename T>
void SingleLinkedList<T>::popBack(){
    Node * current = nullptr;
    Node * previous = nullptr;
    current = head;
    while(current->next != nullptr){
        previous = current;
        current = current->next;
    }
    tail = previous;
    previous->next = nullptr;
    delete current;
}


template <typename T>
void SingleLinkedList<T>::popAtPosition(int position){
    Node * previous = nullptr;
    Node * current = nullptr;

    if(position < 1){
        std::cout << "Invalid index" << std::endl;
        throw std::out_of_range("Invalid index");
    }
    if(position > getLength()){
        std::cout << "Invalid index" << std::endl;
        throw std::out_of_range("Invalid index");
    }
    if(position == 1){
        popFront();
        return;
    }

    if(position == getLength()){
        popBack();
        return;
    }

    current = head;
    for(int i=1; i<position; i++){
        previous = current;
        current = current->next;
    }
    previous->next = current->next;
}

template <typename T>
int SingleLinkedList<T>::getLength(){
    Node * current = head;

    int len = 0;
    while(current != nullptr){
        len++;
        current = current->next;
    }
    //std::cout << "The list length is: " << len;
    return len;
}

template <typename T>
int SingleLinkedList<T>::getValue(int position){
    Node * current = head;

    if(position < 1){
        std::cout << "Invalid index" << std::endl;
        throw std::out_of_range("Invalid index");
    }
    if(position > getLength()){
        std::cout << "Invalid index" << std::endl;
        throw std::out_of_range("Invalid index");
    }
    for(int i=1; i<position; i++){
        current = current->next;
    }
    std::cout << "In index: " << position << ", the value is: " << current->data << "." << std::endl;
    return current->data;
}

template <typename T>
typename SingleLinkedList<T>::Node * SingleLinkedList<T>::search(T value){
    if(head==nullptr){
        return nullptr;
    }
    Node * current = head;

    while(current->next != nullptr){
        if(current->data == value)
            return current;
        current = current->next;
    }

    return nullptr;
}

template <typename T>
std::ostream& operator<<(std::ostream& os, const SingleLinkedList<T>& list){
    list.displayList(os);
    return os;
}


int main(){

    SingleLinkedList<int> myList;
    myList.insert(10);
    myList.insert(20);
    myList.insert(30);

    // test of copy constructor
    SingleLinkedList<int> myList2(myList);
    myList2.insert(40);

    // test of copy assignment operator
    SingleLinkedList<int> myList3;
    myList3.insert(90);
    myList3 = myList2;
    myList3.insert(50);

    std::cout << "myList:" << std::endl;
    std::cout << myList;

    std::cout << "myList2:" << std::endl;
    std::cout << myList2;

    std::cout << "myList3:" << std::endl;
    std::cout << myList3;

    // standard operations
    std::cout << "-----------------------------------------------------" << std::endl;
    std::cout << "push front: "<< std::endl;
    myList.pushFront(5);
    myList.pushFront(2);
    std::cout << myList;

    std::cout << "push back: "<< std::endl;
    myList.pushBack(40);
    myList.pushBack(50);
    std::cout << myList;

    std::cout << "push at position: "<< std::endl;
    myList.pushAtPosition(7,4);
    std::cout << myList;

    std::cout << "pop front x2: "<< std::endl;
    myList.popFront();
    myList.popFront();
    std::cout << myList;

    std::cout << "pop back x2: "<< std::endl;
    myList.popBack();
    myList.popBack();
    std::cout << myList;

    //pop at position
    std::cout << "pop at position: "<< std::endl;
    myList.popAtPosition(2);
    std::cout << myList;

    //get value
    std::cout << "get value: "<< std::endl;
    myList.getValue(3);

    // search
    std::cout << "search: "<< std::endl;
    auto result = myList.search(30);
    std::cout << "Value: " << result->data << " found under " << result << std::endl;

    return 0;
}

Now - yes. On my local machine it compiles without stdexcept, I didn't have any idea that it doesn't work, sorry. — pb.
– pb., Commented May 19, 2018 at 23:07
Even if your code does work the question about explaining code (I.e. #2) makes it off- topic. — Sᴀᴍ Onᴇᴌᴀ
– Sᴀᴍ Onᴇᴌᴀ ♦, Commented May 20, 2018 at 0:40
Off-topic question was removed. Please open my question or comment what should I improve. — pb.
– pb., Commented May 20, 2018 at 8:39
"but I am not sure if my implementation is correct, especially = operator." Does the code currently work as intended? — Mast
– Mast ♦, Commented May 21, 2018 at 7:43

JDługosz · Accepted Answer · 2018-05-21 19:58:10Z

There is some good, a few things wrong.

I see you are nesting Node inside the class, which is good. Most people start by making it a separate top-level item.

It is a problem though that the type Node is private, yet search, a public member, returns that!

You can use default initializers on the data members, and not have to list them in the constructors.

Node* head { nullptr };
Node* tail { nullptr };
   ⋮

SingleLinkedList() { cout << "Noisy class\n"; }

If you did not want the side-effect of logging creation, you could just say

SingleLinkedList() =default;

Node * search(T value);

This is not const? Mistake, or does searching modify the tree?

You take T by value in all the functions. What if T is a substantial type? You want to normally take it by const reference, except for functions that will create a Node, in which case treat it as a “sink” parameter.

Node * temp = nullptr;
while(head!=nullptr){
    temp = head;
    head = head->next;
    delete temp;
}

⧺C.149 — no naked new or delete.

You should make the next member a unique_ptr, and then you don’t have to write this body at all.

But if you were writing a loop like this, you don’t need temp — use std::exchange.

template <typename T>
SingleLinkedList<T>::SingleLinkedList(const SingleLinkedList<T> &oldList){
    std::cout << "Copy constructor..." << std::endl;

    // is it necessary? my constructor by default initializes head and tail with nulls
    this->head = nullptr;
    this->tail = nullptr;

    Node * temp = nullptr;
    temp = oldList.head;

    while(temp!=nullptr){
        this->insert(temp->data);
        temp = temp->next;
    }
}

The style in C++ is to put the * or & with the type, not the identifier. This is called out specifically near the beginning of Stroustrup’s first book, and is an intentional difference from C style.

You seem to be exploring different styles in this code; I see three different ways.

is it necessary? my constructor by default initializes head and tail with nulls

The copy default constructor is not involved here, as this is a different constructor. You should use initializer list, not assignment to the data members (as you had in the first constructor).

However, the change I suggested earlier — putting them on the data members themselves — works across all constructors. So with that in place, you do not need to initialize them here.

You don’t write this-> for access to your own members.

Declare a variable when you are ready to initialize it. You almost had that here:

Node * temp = nullptr;
temp = oldList.head;

Why do you initialize it only to assign to it on the very next line?

Node* temp = oldList.head;

Don’t write explicit tests against nullptr. Use the contextual conversion to bool as a more general truth value of objects. This is more important when it comes to smart pointers. The idiomatic thing to write is

while (temp) { ⋯

In your copy assignment operator:

    this->~SingleLinkedList();

No, never do that. This destroys the object, and subsequent use of it is undefined behavior. What you can do is have the destructor and the assignment operator both call a common helper function for tearing down the object.

The rest of it looks the same as the copy constructor. So again, make a common helper.

Node * temp = new Node(value);

As mentioned before, don’t use naked new/delete. So, if you used a unique_ptr, then this becomes make_unique.

The incoming value is a “sink” parameter. That is, you will for certain be creating a new instance of that type in your fresh node. So, optimize for that by taking it by value and moving it to the final location.

auto fresh = make_unique<Node>(std::move(value));

(The constructor for Node needs to continue moving)

void SingleLinkedList<T>::displayList(std::ostream& stream) const{

Don’t write a member for this!

Make a non-member that uses the general-use public abilities of the list to be traversed.

It seems that your primary access is by index position, treating it like a vector. Imagine how slow that is if you go through each element in turn: each time you start over at the beginning and count one position farther!

You should present an Iterator that can be used like those in the standard library.

So, the search function is not necessary! std::find should work on your list.

if(position < 1){
    std::cout << "Invalid index" << std::endl;
    throw std::out_of_range("Invalid index");
}
if(position > getLength()){
    std::cout << "Invalid index" << std::endl;
    throw std::out_of_range("Invalid index");
}

You already allocated temp so throwing will leak memory. Put these preconditions first, before doing anything at all.

You are duplicating most of the content here. Just write it as one test:

if (position<1 || position > getLength()) {
    std::cout << "Invalid index\n";
    raise_index_error();
}

A few other things to notice here: Stop using endl.
Throwing generates a large amount of code, and is on the “cold” code path in a function you want to be inlined most of the time. So always break that out into its own separate function.

Best of luck to you — keep up the good effort!

Thank you so much. I will study your answer and edit that comment. — pb.
– pb., Commented May 22, 2018 at 8:36

Stack Exchange Network

Single Linked List - simple approach

1 Answer 1

You must log in to answer this question.

Hot Network Questions

Single Linked List - simple approach

1 Answer 1

You must log in to answer this question.

Related

Hot Network Questions