Implementing Singly Linked List using C++

Question

I have implemented Single Linked List. Need Suggestions for improving it ? Also i need to know how i can pass a list object to a function? Thanks in advance.

Node.hpp

#ifndef NODE_H
#define NODE_H

class Node
{
public:
    int data;

    Node *next;
};

#endif

LinkedList.hpp

#ifndef LINKEDLIST_H
#define LINKEDLIST_H
#include "Node.hpp"

class LinkedList {
private:
    Node *head;
public:
    LinkedList();
    ~LinkedList();
    /*Insert Before the Value Method : Insert a Value before the passed value.*/
    void insert_bfv(int, int);
    /*Insert Nth Method : Insert a value at nth Location in the list if exist.*/
    void insert_nth(int, int);
    /*Move To Nth Method : Move a Node to the Nth Location.*/
    void moveto_nth(int, int);
    /*Insert First Method : Insert a Value in the start of list.*/
    void insert_first(int);
    /*Insert Last Method : Insert a Value at the end of list.*/
    void insert_last(int);
    /*Delete Nth Method : Delete nth value from the list.*/
    void delete_nth(int);
    /*Delete Value Method : Search and Delete a passed Value from list.*/
    void delete_val(int);
    /*Search value Method : Check if a passed value is in the list.*/
    void search_val(int);
    /*Delete First Method : Delete the first value in the list.*/
    void delete_first();
    /*Delete Last Method : Delete the last value in the list.*/
    void delete_last();
    /*Is Empty Method : To check if list is Empty.*/
    bool is_empty();
    /*Print List Method : Print all values in the list.*/
    void print_l();
    /*Length Method : Return the number of nodes in the list.*/
    int length();
    /*First Method : Return the first value of the list else (-1).*/
    int first();
    /*Sum List Method : Return the Sum of data Values of the list.*/
    int sum_l();
};

#endif

LinkedList.cpp

#include "LinkedList.hpp"
#include "Node.hpp"
#include <iostream>
using namespace std;

/*Constructor*/
LinkedList::LinkedList() { 
    head = NULL;
}

/*Destructor*/
LinkedList::~LinkedList() {
    if (!is_empty()) {
        Node *temp = head, *prev = NULL;
        while (temp->next != NULL) {
            prev = temp;
            temp = temp->next;
            delete prev;
        }
        delete temp;
    }
}
/*Is Empty Method : To check if list is Empty.*/
bool LinkedList::is_empty() { 
    return head == NULL; 
}

/*First Method : Return the first value of the list else (-1).*/
int LinkedList::first() {
    if (!is_empty())
        return head->data;
    else
        return -1;
}

/*Insert First Method : Insert a Value in the start of list.*/
void LinkedList::insert_first(int x) {
    Node *newer = new Node;
    newer->data = x;
    newer->next = head;
    head = newer;
}

/*Insert Last Method : Insert a Value at the end of list.*/
void  LinkedList::insert_last(int x) {
    Node *newer = new Node;
    newer->data = x;
    if (is_empty()) {
        newer->next = head;
        head = newer;
    }
    else {
        Node *temp = head;
        while (temp->next != NULL) {
            temp = temp->next;
        }
        newer->next = temp->next;
        temp->next = newer;
    }
}
/*Print List Method : Print all values in the list.*/
void LinkedList::print_l() {
    if (is_empty()) {
        cout << "List is Empty." << endl;
    }
    else {
        Node *temp = head;
        while (temp != NULL) {
            cout << temp->data << " ";
            temp = temp->next;
        }
        cout << endl;
    }
}

/*Search value Method : Check if a passed value is in the list.*/
void LinkedList::search_val(int x) {
    if (is_empty())
        cout << "List is Empty." << endl;
    else {
        bool check = false;
        Node *temp = head;
        while (temp != NULL) {
            if (temp->data == x) {
                cout << "Value found." << endl;
                check = true;
                break;
            }
            else 
                temp = temp->next;
        }
        if (check == false)
            cout << "Value not found." << endl;
    }
}
/*Delete First Method : Delete the first value in the list.*/
void LinkedList::delete_first() {
    if (is_empty())
        cout << "List is already Empty." << endl;
    else {
        Node *temp = head;
        head = temp->next;
        delete temp;
    }
}

/*Delete Last Method : Delete the last value in the list.*/
void LinkedList::delete_last() {
    if (is_empty())
        cout << "List is already Empty." << endl;
    else if (head->next == NULL) {
        Node *temp = head;
        head = NULL;
        delete temp;
    }
    else {
        Node *temp = head, *prev = NULL;
        while (temp->next != NULL) {
            prev = temp;
            temp = temp->next;
        }
        prev->next = NULL;
        delete temp;
    }
}

/*Insert Before the Value Method : Insert a Value before the passed value.*/
void LinkedList::insert_bfv(int x, int k) {
    if (is_empty())
        cout << "List is Empty." << endl;
    else {
        Node *newer = new Node;
        newer->data = x;
        Node *temp = head, *prev = NULL;
        while (temp->next != NULL && temp->data != k) {
            prev = temp;
            temp = temp->next;
        }
        if (temp->next == NULL && temp->data != k) {
            cout << "Passed value is not in the list." << endl;
        }
        else if (temp == head) {
            newer->next = temp;
            head = newer;
        }
        else {
            newer->next = temp;
            prev->next = newer;
        }
    }
}

/*Insert Nth Method : Insert a value at nth Location in the list if exist.*/
void LinkedList::insert_nth(int x, int n) {
    if (!(n <= 0 && n>length())) {
        Node *newer = new Node;
        newer->data = x;
        Node *temp = head;
        int count = 1;
        while (temp != NULL && count != n) {
            count++;
            temp = temp->next;
        }
        newer->next = temp->next;
        temp->next = newer;
    }
    else {
        cout << "Location range is incorect." << endl;
    }
}

/*Delete Value Method : Search and Delete a passed Value from list.*/
void LinkedList::delete_val(int k) {
    Node *temp = head, *prev = NULL;
    if (is_empty())
        cout << "List is Empty." << endl;
    else if (temp->data == k) {
        head = temp->next;
        delete temp;
    }
    else {
        while (temp->data != k && temp->next != NULL) {
            prev = temp;
            temp = temp->next;
        }
        if (temp->next == NULL && temp->data != k)
            cout << "Value Not Found in the list." << endl;
        else {
            prev->next = temp->next;
            delete temp;
        }
    }
}
/*Delete Nth Method : Delete nth value from the list.*/
void LinkedList::delete_nth(int k) {
    Node *temp = head, *prev = NULL;
    if (is_empty()) 
        cout << "List is Empty." << endl;
    else {
        if (k > length() && k <= 0)
            cout << "Node does not exist." << endl;
        else {
            int count = 1;
            while (temp != NULL && count != k) {
                prev = temp;
                temp = temp->next;
                count++;
            }
            prev->next = temp->next;
            delete temp;
        }
    }
}

/*Length Method : Return the number of nodes in the list.*/
int LinkedList::length() {
    if (is_empty())
        return 0;
    else {
        int count = 0;
        Node *temp = head;
        while (temp != NULL) {
            count++;
            temp = temp->next;
        }
        return count;
    }
}

/*SUM LIST Method : Return the Sum of data Values of the list.*/
int LinkedList::sum_l() {
    Node *temp = head;
    int sum = 0;
    while (temp != NULL) {
        sum = sum + temp->data;
        temp = temp->next;
    }
    return sum;
}

/*Move To Nth Method : Move a Node to the Nth Location.*/
void LinkedList::moveto_nth(int n1, int n2) {
    if(n1 < n2 && n1 < length() && n2 <= length() && n1 > 0 && n2 > 1 && n1 != n2) {
        Node *temp1 = head, *temp2 = head, *prev = NULL;
        int count1 = 1, count2 = 1;
        while (temp1 != NULL && count1 != n1) {
            prev = temp1;
            temp1 = temp1->next;
            count1++;
        }
        while (temp2 != NULL && count2 != n2) {
            temp2 = temp2->next;
            count2++;
        }
        if(prev == NULL)
            head = head->next;
        else
            prev->next = temp1->next;
        temp1->next = temp2->next;
        temp2->next = temp1;
    }
    else {
        cout << "Range is incorect." << endl;
    }
}

main.cpp

#include "LinkedList.hpp"

int main() {
    LinkedList list;
    list.insert_last(12);
    list.insert_last(13);
    list.print_l();
    list.delete_first();
    list.print_l();
}

Could you show us a simple program that would demonstrate the usage of the code you wrote? Simple main() with 3-4 operations will be ok. — Incomputable
– Incomputable, Commented Dec 14, 2017 at 14:25
Great! Upvoted. CodeReview is much slower place compared to StackOverflow, so it might take several hours or days to get a response. On the other hand, CodeReview doesn't need much interaction with the asker after the post has been set up. I hope you'll get some nice reviews. — Incomputable
– Incomputable, Commented Dec 14, 2017 at 14:32

Ben Steffan · Accepted Answer · 2017-12-14 16:26:58Z

Flexibility

You have fixed your data type to be int. What if I want to store, say, a double, or a std::string in my list? Fat chance.

Instead, you should make both classes templated, so that you can have lists of whatever type you want.

Interface

I'm sorry to tell you this, but your linked list is basically useless. Why? Because you don't offer any interface for iterating the list. So what can be done with it? Currently only two things: It can be printed and you can calculate its sum, so not very much at all.

What you're really missing is an iterator interface here (although a pointer interface would be a start, I guess). Although iterators are kind of cumbersome to implement, they are one of the most useful features of modern C++ and required if you want your class to be able to operate with standard algorithms. For example, there is std::accumulate which makes your sum_l function obsolete (and is also more versatile).

Furthermore, you have a lot of insert_XXX and delete_XXX methods which are hardly necessary. You should take a look at what std::list offers as an interface and orient your code at that.

Another thing which is really important is that you disobey the rule of 3/5/0 (depending on the C++ standard you're targeting). Although you do implement a destructor, things such as copy- and move-constructors are missing, which makes your class hard to use (making copies is basically impossible). That also answers your question of what you need to do to be able to pass your list as an argument to functions: implement all required special member functions.

Lastly, we need to talk about error handling. A method such as int first() has a huge problem: You cannot really signal an error. Although you were farsighted enough to take care of the fact that your list might be empty, you didn't find a good solution to that problem: Just returning -1 is bad, because as a user you can't distinguish were this number came from. After all, it might just be that the first element in the list had the value of -1. Luckily, C++ comes with a special error handling feature: Exceptions. Instead of returning you could just throw an exception and have the error be unmistakably passed to the caller. However, exceptions are expensive and should be used sparingly; maybe you'd want to consider having std::optional<int> as a return value instead (if you are using C++17, of course), or remove the check altogether and make it the user's liability to check the size first (In fact, )

General Hints and Tips about Coding Style

Node would make more sense as a struct than as a class: You have no member functions whatsoever and all data members are public. Since this is usually what is expected of a struct, you should match those expectations.
int is not the right type for everything. Especially for things like indices and sizes, other (unsigned) integer types are more appropriate. Why? Because int can be pretty limited in size. For example, on my machine an int is a 32-bit signed integer, but, since it actually is a 64-bit architecture, I could possibly have a memory address outside the int range, which would likely lead to overflow (which is UB!) and the last few elements of the list being inaccessible. Instead, std::size_t suggests itself here; it is a type made to represent sizes (just as the name suggests). Think about what a parameter means and how it will be used when you define its type.
Don't use using namespace std;. You gain almost nothing except an additional chance to break your code in subtle ways by introducing all the names from std:: into the global namespace where they may clash with your own names.
If you use C++11 or beyond, don't use NULL, use nullptr as it offers improved type safety.
Separate responsibilities. In particular, don't have any method from LinkedList do any IO. Write helper methods/classes to do this (this is known as the Single Responsibility Principle and is one of the most important principles of Object Oriented Programming).
Give names to the parameters in your functions declarations. Parameters without names often imply that the parameter is ignored, and names offer you another place for documentation.
Don't use std::endl. It doesn't serve any purpose, except confusing you about what it does, which is printing a newline character but also flushing the output buffer which is almost never what you want. Use '\n' instead.
Write out NULL (or nullptr) when you mean it. Please don't write
```
while (temp->next != NULL) {
    //...
}
newer->next = temp->next;
```
when you should write newer->next = NULL because that is what your code is actually doing. There's no need to be overly clever and assign from a location whose value is known; please don't confuse us and yourself and write out the value.
It might be beneficial to have a std::size_t member to track the length of your list so that you don't have to recalculate it every time length() is called.

@MalikBilal, please use "bro" carefully. Not everyone likes it. — Incomputable
– Incomputable, Commented Dec 14, 2017 at 16:41

Harald Scheirich · Accepted Answer · 2017-12-15 13:41:52Z

I don't know what purpose you wrote this class for, I am assuming your LinkedList is supposed to be used by someone. Some of these are repeats of what @ben-steffan wrote, but I had already written them up.

Node should be member of LinkedList

You're not exposing the Node type to the rest of the world, there is no reason to have a separate include file. It can be a private member struct of LinkedList, it doesn't have to be a class either.

Function naming in accordance with stl

C++ has a well established set of containers, you are implementing a container, in fact you are reimplementing a std::fordward_list, although your interface is more the scope of the std::list. The containers have a fairly consistent interface that C++ programmers should be conversant with. If you are implementing a new container try to keep the interface as close as possible. E.g. you have length returning int the stl has size returning size_t. You have insert_last the stl has push_back, etc. Doing this will help everybody understand what you are doing without you having to do a lot of explaining.

Parameter naming

The names of function parameters are your chance to help the users of your functions (sometimes that is you) with what your function is intended to do, if you name them according to what the parameter is about it will really improve the clarity of your code. This especially counts when the type of the parameter does not hint to its function e.g. both void LinkedList::delete_nth(int k) and void LinkedList::delete_val(int k) just have int parameters but both are labeled k if you change the name of the parameters delete_nth(int index) and delete_val(int value) the signature becomes more descriptive but also the code becomes much easier to read.

`new()` can fail

You don't check the result of new(). Allocations may fail, this means in most cases it is good to check the result returned from new.

Errors

The containers in the standard library, employ undefined behavior for operations that are not legal for a container, e.g. pop() on an empty list. Personally I like to see a little bit more safety. There are various ways to note error conditions, returning an error value, raising an exception and asserting are various ways to mark errors, each have their use and people have different preferences. Writing errors to cout is unhelpful.

The conditions that you write out as errors have various degrees of severity. E.g. calling delete_last() on an empty list, is an operation that doesn't cause any kind of harm. It might indicate that the developer is making an incorrect assumption (they think there are items in the list) but there are cases where I would just let that happen. But trying to fetch an item from an empty list is and should be marked as an error. Returning a value that is 'valid' in an error case is also usually not a good idea. E.g. your first() function returns -1, a perfectly valid int.

Modern C++: Use `nullptr` instead of `NULL`

nullptr is type safe and for explicit use with pointers

Destructor

There is some room in shortening up your code, sometimes it's just cutting off a couple of loops or reusing your own code

LinkedList::~LinkedList() {
    Node* previous;
    while (head != NULL) {
        previous = head;
        head = head->next;
        delete previous;
    }
}

Printing becomes more useful when implemented as a an ostream operator

You wrote print_l to output your list on the screen. While using streams sometimes has some drawbacks, being able to just dump things onto a stream is very helpful, this https://stackoverflow.com/questions/476272/how-to-properly-overload-the-operator-for-an-ostream answer has a good summary on that.

I would like to add, that when calling delete_nth you would likely expect a parameter n instead of index, and n would usually start counting at 1 instead of 0. So I would rather call it delete_index, or even better, when using size_t instead of int, make it an overload and call the methods remove(size_t index) and remove(int value), also preventing confusion with the deletion of objects. — Raimund Krämer
– Raimund Krämer, Commented Dec 21, 2017 at 8:34

Stack Exchange Network

Implementing Singly Linked List using C++

2 Answers 2

Flexibility

Interface

General Hints and Tips about Coding Style

Node should be member of LinkedList

Function naming in accordance with stl

Parameter naming

`new()` can fail

Errors

Modern C++: Use `nullptr` instead of `NULL`

Destructor

Printing becomes more useful when implemented as a an ostream operator

You must log in to answer this question.

Linked

Hot Network Questions

Implementing Singly Linked List using C++

2 Answers 2

Flexibility

Interface

General Hints and Tips about Coding Style

Node should be member of LinkedList

Function naming in accordance with stl

Parameter naming

new() can fail

Errors

Modern C++: Use nullptr instead of NULL

Destructor

Printing becomes more useful when implemented as a an ostream operator

You must log in to answer this question.

Linked

Related

Hot Network Questions

`new()` can fail

Modern C++: Use `nullptr` instead of `NULL`