9
\$\begingroup\$

Linked List C++

I am new to data structures and I have to implement my own data structures for a project. I have made this working Singly Linked List data structure in C++. I would like to ask everyone who is more experienced than me in this matter if my implementation is optimized enough, and if my memory usage and allocation works fine (because I think that my memory might be broken). Any other suggestions and fixes are welcome.

#pragma once
#ifndef LINKEDLIST_H
#define LINKEDLIST_H

#include <iostream>
#include <limits>


using namespace std;

template <class T>
struct node
{
    T data;
    node<T> *next;
};

template <class T>
class SLL
{
        private:
        node<T> *head, *tail;
        public:

        SLL() // Constructor
        {
            head = nullptr;
            tail = nullptr;
            cout << "Constructor Called" << '\n';
        }


        ~SLL() // Destructor
        {
            int index = 1;
            node<T>* tempo;
            while(head != nullptr)
            {
                tempo = head->next;
                delete head;
                head = tempo;
                cout << "Destructor Called "<< "Destroying node number "<< index << '\n';
                index++;
            }
        }

        void createnode(T value)

        {
            node<T> *temp = new node<T>;
            temp->data = value;
            temp->next = nullptr;
            if(head == nullptr)
            {
                head = temp;
                tail = temp;
                temp = nullptr;
            }
            else
            {
                tail->next = temp;
                tail = temp;
            }
        }


        void display()
        {
            node<T> *temp = new node<T>;
            temp = head;
            while(temp != nullptr)
            {
                cout << temp->data <<" ";
                temp = temp->next;
            }
            cout << '\n';
        }


        void insert_start(T value)

        {
            node<T> *temp = new node<T>;
            temp->data = value;
            temp->next = head;
            head = temp;
        }



        void insert_position(int pos, T value)

        {
            node<T> *pre = new node<T>;
            node<T> *cur = new node<T>;
            node<T> *temp = new node<T>;
            cur = head;
            for(int i=1; i<pos; i++)
            {
                pre = cur;
                cur = cur->next;
            }
            temp->data = value;
            pre->next = temp;
            temp->next = cur;
        }


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


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


        void delete_position(T pos)

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

        int length() const{

            node<T> *current = head;
            int len = 0;
            while(current){
                len++;
                current = current->next;
            }
            cout << "The lists length is: " << len << '\n';
            return len;
        }



        T find(int k)
        {
            node<T> *current = new node<T>;

            if(k < 1){
                cout << "Invalid Index point" << '\n';
                throw std::out_of_range ("Invalid Index point");
            }
            if(k > length()){
                cout << "Index Out of Bounds" << '\n';
                throw std::out_of_range ("Invalid Index point");
            }
            current = head;
            int index = 1;
            while (index < k && current){
                current = current->next;
                index++;
            }
            if(current){
                cout << "In index point: " << k << " || " << " The value is: "<< current->data << '\n';
                return current->data;
            }
        }

        int search(const T& x) const{

            node<T> *current = new node<T>;
            current = head;
            int index = 1;
            while (current && current->data != x){
                current = current->next;
                index++;
            }
            if(current){
                cout << "The value: " << x << " || " << "Was found in index point: " << index << '\n';
                return index;
            }
            return 0;
        }

        bool isempty(){

            if(head == nullptr){
                cout << "The list is empty" << '\n';
                return true;
            }
            cout << "The list is NOT empty" << '\n';
            return false;
        }

        T const findbig(){
            T max;
            node<T> *current = new node<T>;
            node<T> *nn = new node<T>;
            nn = head->next;
            current = head;
            max = std::numeric_limits<T>::min();
            int index = 1;
            while(current){
                if(current->data > max){
                    max = current->data;
                }
                current = current->next;
                index++;
            }
            cout << "The BIGGEST value found in the list is: " << max << '\n';
            return max;
            }

            T const findsmall(){
                T min;
                node<T> *current = new node<T>;
                current = head;
                min = std::numeric_limits<T>::max();
                int index = 1;
                while(current){
                    if(current->data < min){
                        min = current->data;
                    }
                    current = current->next;
                    index++;
                }
                cout << "The LOWEST value found in the list is: " << min << '\n';
                return min;
                }

};

#endif
\$\endgroup\$
12
\$\begingroup\$

I like this.

#ifndef LINKEDLIST_H
#define LINKEDLIST_H

But it is not very unique. If used in a big project this may clash with other guards. I usually include the name of the namespace in the guard. Alternatively you can generate a GUID.

Don't do this.

using namespace std;

More detail can be found here Why is “using namespace std” considered bad practice?

You should note that the standard namespace is called std and not standard so it does not become a burden to prefix objects in the standard namespace with std::.

All your code should be inside a namespace.
Register the domain Spyros.com then use the namespace Spyros { around all your code.

The node object does not need to be exposed to the user.

template <class T>
struct node
{
    T data;
    node<T> *next;
};

I would note that a very common convention is to make user defined types have an initial capitol letter. While variables and functions have an initial lowercase letter.

This allows you to distinguish between the two:

 Node(1,2);  // creating an object of type Node
 node(1,2);  // calling a function node() 

Make this a private member of the SSL class. Curious why you chose a singly linked list. It is much easier to implement a doubly linked list.

Please declare one member per line.

        node<T> *head, *tail;

Also the * is part of the type. So put it next to the type. The way you do it is very C like in C++ the type information is much more important.

        node<T>*  head;
        node<T>*  tail;

Constructor

This is good:

        SLL() // Constructor
        {
            head = nullptr;
            tail = nullptr;
            cout << "Constructor Called" << '\n';
        }

But this is better:

        SLL() // Constructor
            : head(nullptr)
            , tail(nullptr)
        {
            cout << "Constructor Called" << '\n';
        }

Prefer initializer lists.
This will prevent members from being initialized twice (once during the initialization processes and once in the body of the constructor).

But you have not obeyed the rule of three.

Basically: unless you define them the compiler generates three methods for you. Normally if you need to define any one of these methods you really should define all three.

The three are:

  ~SLL();                      // Destructor.
  SLL(SLL const&);             // Copy Constructor
  SLL& operator=(SLL const&);  // Copy Assignment

You define the destructor (and do resource management so work). So you should define the other two (because the default implementation does not do resource management).

Currently your code will break if you copy the list.

  {
      SLL<int>   list1;
      list1.createnode(1);

      SLL<int>   list2(list1);   // Copy constructed

      SLL<int>   list3;
      list3 = list2;             // Copy Assignment.
  }    
  // All three lists point at the same node internally.
  // Thus the destructor of all three objects will destroy the
  // same node.

Destructor

This looks fine.

Methods

Your methods don't follow the standard naming convention. You should look at the standard libraries and try and emulate the conventions they use there.

General Comments.

Passing T by value.

        void createnode(T value)

This is fine for simple types like int. But what if T is a vector or another list or some other big object. When you pass by value you are creating a copy. As a result we normally pass by const reference the called function can then make a copy if they want or just read it if they don't want a copy.

        void createnode(T const& value)

This can be simplified:

            node<T> *temp = new node<T>;
            temp->data = value;
            temp->next = nullptr;

Try

 node<T>* temp = new node<T>(value, nullptr);

Displaying a list function is fine. But it can be useful to display to other streams (std::cout is not the only stream type).

        void display()

Change to

        void display(std::ostream& str = std::cout) const // display does not change the list so mark it const.

Use the str parameter as a stream. It defaults to std::cout but you can pass anything (including a file.

We should also note that in C++ the standard way of printing something is to use operator<<. We can define this in terms of display() like this.

        friend std::ostream& operator<<(std::ostream& os, SSL const& list) {
            list.display(os);
            return os;
        }

Now you can print the stream in the normal C++ way.

In this function you assume that pos is valid.

        void insert_position(int pos, T value)

Things will go very wrong if pos is larger than the number of elements. You need to fix this.

These two calls to new are not needed. They cause you to leak memory.

            node<T> *pre = new node<T>;
            node<T> *cur = new node<T>;

Just set them to nullptr;

            node<T> *pre = nullptr;
            node<T> *cur = nullptr;

Note: For every call to new, there must be a corresponding call to delete. For the nodes in the list this is done in the destructor. But these two nodes are not added to the list.

Again you leak memory in the delete:

        void delete_first()
        {
            node<T> *temp = new node<T>;


        void delete_last()
        {
            node<T> *current = new node<T>;
            node<T> *previous = new node<T>;

In deleting you forget to test if the list is empty. This is going to cause some issues. You should review your delete implementations for the empty list case.

\$\endgroup\$
  • \$\begingroup\$ Thanks for providing such a detailed explanation of what goes wrong i will try to implement all of those changes so i can suit the C++ style of coding, cause I'm relativly new to programming. If something does not seem to work or if i can't get it to, I'll make sure to ask for your guidance. Appreciate the help. \$\endgroup\$ – Spyros Giannikakis Mar 27 '18 at 17:45
  • \$\begingroup\$ Would you be kind enough to explain motivation behind calling initialization of members inside body of c'tor rather than member initialization list good? Also small nitpick, "rule of 3" is kinda misleading in modern days, it's more like 5 or 7 I think. \$\endgroup\$ – luk32 Mar 28 '18 at 9:40
  • \$\begingroup\$ @luk32: The rule of three is still the main way. The rule of 5 is an optional extension (if you obey the rule of three then the rule of 5 is taken care of automatically in that move semantics are disabled). I usually cover move semantics if the OP has some experience. In this case there is so much else to do. Never heard of the rule of 7. \$\endgroup\$ – Martin York Mar 28 '18 at 15:12
  • \$\begingroup\$ @luk32: Fixed the constructor thing. \$\endgroup\$ – Martin York Mar 28 '18 at 15:13
  • \$\begingroup\$ @MartinYork Some believe you should also take special care with the default constructor. Also, if you are providing user-defined value semantics so your resources won't leak, you should think about exception safety (swap() support) for your value types as well. \$\endgroup\$ – Snowhawk Apr 2 '18 at 4:58
10
\$\begingroup\$

don't do this:

using namespace std;

This will create a lot of namespace collisions. Writing std:: where you need to isn't that awful.

You have a destructor so you should also create copy and move constructors and copy and move assign overloads so you follow rule of 5.

Your create node makes extra copy when it doesn't need to. Also let the store value be initialized in place:

void createnode(T value)
{
    node<T> *temp = new node<T>(std::move(value));
    temp->next = nullptr;
    if(head == nullptr)
    {
        head = temp;
        tail = temp;
        temp = nullptr;
    }
    else
    {
        tail->next = temp;
        tail = temp;
    }
}

template< class... Args >
void emplacenode(Args&&... args)
{
    node<T> *temp = new node<T>(std::forward(args)...);//add constructor to init data.
    temp->next = nullptr;
    if(head == nullptr)
    {
        head = temp;
        tail = temp;
        temp = nullptr;
    }
    else
    {
        tail->next = temp;
        tail = temp;
    }
}

insert_start and insert_position don't do anything with the T passed in. insert_position also leaks 2 of the created nodes.

In fact a lot of functions have a node<T> *current = new node<T>; that gets overwritten immediately. This is a horrible leak. If you need to init the value prefer nullptr.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestions. I understand the namespace part. I will also implement the remaining funtionality to follow the rule of 5. But i dont understand what do you mean , when you say that the template parameter T passed in some of my funtions doesn't do anything. Also how should i aprroach to patch the leaks of the 2 created nodes in the insert_position function. Also you suggest that it should init the newly created nodes inside my functions with nullptr and that got me confused as of how i should create them. Is my allocation using new wrong ? \$\endgroup\$ – Spyros Giannikakis Mar 27 '18 at 16:16
  • 1
    \$\begingroup\$ @SpyrosGiannikakis You often allocate new memory when all you need is a pointer to an existing node which can be obtained by simply doing node<T>* temp = head; \$\endgroup\$ – yuri Mar 27 '18 at 16:23
  • \$\begingroup\$ @yuri Oh thanks so there is no point in allocating with new in every function i just need a pointer to something of the same type that already exists. \$\endgroup\$ – Spyros Giannikakis Mar 27 '18 at 16:27
7
\$\begingroup\$
  1. Use either include-guards or the non-standard but common #pragma once, not both. If you insist on using both, change the order, as those compilers optimizing include-guards generally insist on only comments and white-space being outside the guards.

  2. node is an implementation-detail of SLL. As such, it should be in the private part of SLL and pick up the template-argument from that.

  3. Never use using namespace std; in an include-file, not that it is much better in a source-file. Read "Why is “using namespace std;” considered bad practice?" for the reasons.

  4. Don't produce any output from functions not explicitly designed for that. There are exceptions, and in specific cases error-codes for signalling failure.
    Anyway, cerr is for diagnostic output, don't abuse cout.

  5. Consider using in-class-initializers for the member, and default-ing the default ctor.

  6. You are violating the rule of 3 / 5 / 0. As your user-defined dtor signals, your SLL owns the nodes. So the default copy-ctor and copy-assignment are obviously wrong.

  7. Use the standard-library-conventions for names. Otherwise, your container is incompatible with the standard-library. As an example, see std::forward_list.

  8. If you add an iterator-interface, many of your functions can be replaced by a single call to a standard algorithm.

  9. Consider whether instead of passing the T by value, it might not be more efficient to have both constant reference and rvalue reference versions.

  10. Emplace-constructing a new node's value can also be far more efficient. Other methods can delegate to that without loss of efficiency.

\$\endgroup\$
  • \$\begingroup\$ Thanks for the suggestions. Can you please further explain the 7th, 9nth and 10nth points ? Much appreciate the help. \$\endgroup\$ – Spyros Giannikakis Mar 27 '18 at 16:40
  • \$\begingroup\$ @SpyrosGiannikakis done. \$\endgroup\$ – Deduplicator Mar 27 '18 at 16:54
6
\$\begingroup\$

Length

You provide a method to calculate the length of the list. But from the moment of creation of the list, you should be able to track this length. If you add a private counter, increment it whenever a node gets added, and decrease it whenever a node gets deleted, you should be able to instantly provide the length, instead of having to compute it each time the user requests it.

Repeated code

You provide methods for deleting the first node, the last node, and any node. In the first two methods you kind of repeat the code of the latter method.

You could redefine those by calling the latter:

void delete_first()
{
    delete_position(1);
}

void delete_last()
{
    delete_position(length);
}

A similar thing for the insert methods:

void insert_start(T value)
{
    insert_position(value, 1);
}

Segmentation fault

In find you validate your position inputs:

   T find(int k)
    {
        if(k < 1){
            cout << "Invalid Index point" << '\n';
            throw std::out_of_range ("Invalid Index point");
        }
        if(k > length()){
            cout << "Index Out of Bounds" << '\n';
            throw std::out_of_range ("Invalid Index point");
        }

You don't do this in delete_position though. If you have a list of length 4, the call delete_position(10) will look past the end of the list. That's a problem. One that's easily fixed by the same checks as above.

You probably also want to validate the input for insert_position. You don't want a position <1 as input, and neither do you want an input past the end of the list.

\$\endgroup\$

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.