1
\$\begingroup\$

I need some review for this CPP Linked list implementation. This is my first time implementing such a data structure in CPP. Thanks in advance.

 /* 
 **
 **   author:  Omar_Hafez
 **   created: 12/05/2022  05:15:38 PM
 **
 */
     
#include <bits/stdc++.h>
using namespace std;


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

template<class T>
class Linked_List {
  private:

    Node<T> *head = NULL;
    int count = 0;

  public:

    bool is_empty() {
      return (head == NULL);
    }

    void push_front(T value) {
      Node<T> *new_node = new Node<T>;
      new_node -> data = value;
      new_node -> next = head;
      head = new_node;
      count++;
    }

    void push_back(T value) {
      Node<T> *new_node = new Node<T>;
      new_node -> data = value;
      new_node -> next = NULL;
      if(is_empty()) head = new_node;
      else {
        Node<T> *tmp = head;
        while(tmp -> next != NULL) {
          tmp = tmp -> next;
        }        
        tmp -> next = new_node;
      }
      count++;
    }

    int push_after(T value, T after) {
      if(is_empty()) return 0;
      Node<T> *tmp = head;
      while(tmp != NULL && (tmp -> data) != after) {
        tmp = tmp -> next;
      }
      if(tmp == NULL) return -1;
      Node<T> *new_node = new Node<T>;
      new_node -> data = value;
      new_node -> next = tmp -> next;
      tmp -> next = new_node;
      count++;
      return 1;
    }

    int delete_front() {
      if(is_empty()) return 0;
      if(count == 1) {
        count--;
        head = NULL;
        return 1;
      }
      head = head -> next;
      count--;
      return 1;
    }

    int delete_back() {
      if(is_empty()) return 0;
      if(count == 1) {
        count--;
        head = NULL;
        return 1;
      }
      Node<T> *tmp = head;
      while(tmp -> next -> next != NULL) tmp = tmp -> next;
      tmp -> next = NULL;
      count--;
      return 1;
    }

    int erase(int value) {
      if(is_empty()) return 0;
      int cnt = 0;
      while(!is_empty() && head -> data == value) {
        cnt++;
        delete_front();
      }
      Node<T> *tmp = head;
      while(tmp -> next != NULL) {
        if(tmp -> next -> data == value) {
          tmp -> next = tmp -> next -> next;
          cnt++;
          count--;
        } 
        else 
          tmp = tmp -> next;
      }
      if(tmp -> data == value) {
        delete_back();
        cnt++;
      }
      return cnt;
    }

    void print_values() {
      Node<T> *tmp = head;
      while(tmp != NULL) {
        cout << (tmp -> data) << " ";
        tmp = tmp -> next;
      }
      cout << endl;
    }

    int search(T value) {
      Node<T> *tmp = head;
      while(tmp != NULL) {
        if(tmp -> data == value) return value;
        tmp = tmp -> next;
      }
      return -1;
    }

    int size() {
      return count;
    }
};
\$\endgroup\$
3
  • 1
    \$\begingroup\$ I was beaten by @Martin York. Anyways, your search function is faulty, in that it's returning T instead of int. You might want to add int index on your code then return that instead! \$\endgroup\$ Commented May 12, 2022 at 22:17
  • \$\begingroup\$ I got that. I forget that It is T, not int so I will fix it to return T. Thanks a lot. \$\endgroup\$
    – Omar_Hafez
    Commented May 14, 2022 at 16:35
  • \$\begingroup\$ Some minor addition: You might consider adding a tail attribute to the Linked List class so that you don't have to traverse the whole list for *_back() methods.. \$\endgroup\$ Commented May 14, 2022 at 23:33

1 Answer 1

4
\$\begingroup\$

Overview

This is a singly linked list. Which is fine. But it is relatively trivial to implement a doubly linked list (next/prev link in each node). Also by using a doubly linked list and a sentinel (look up the sentinel pattern) you can remove the need to check for nullptr (which makes the code easier to read).

You don't release the memory you allocate with new. For every call to new there should be an matching call to delete. This means your object should have a destructor.

You don't obey the rule of three or five.

If your object owns (owns ⇒ creates and destroys) a resource (in this case head) then the compiler-implemented copy constructor and assignment operator will not work (as you expect) and you need to implement your own.

Code-Review

Always good.

/* 
 **
 **   author:  Omar_Hafez
 **   created: 12/05/2022  05:15:38 PM
 **
 */

Not sure if you need a time :-) but you may want to add (C) 2022 if this is auto generated. Note: By posting on this site you are licensing under CC (see bottom of page for details).


Never do:

This:

#include <bits/stdc++.h>

That include is non-standard and your code is going to break and not compile at some point.

Or this:

using namespace std;

This is going to get you in trouble in the long run. You should read the article Why is "using namespace std;" considered bad practice? second answer is the best in my opinion.

Rather than doing this, prefix standard library types objects with std::. It's only 5 characters and the name std was designed to be short for that reason.


This is good. But nobody should use this information (it is an internal detail to the class Linked_List) so make it a private member of the class so only it can use it.

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

It's not wrong.

    Node<T> *head = NULL;

But in C++ (unlike C) the * is usually placed as part of the type.

    Node<T>*   head = nullptr;

In C++ the type information is very important so keeping it all together is useful in reading.

Also NULL is C code. In C++ we use nullptr - it is type safe (unlike NULL).


We can simplify this a bit and make it more readable in one go:

    void push_front(T value) {
      Node<T> *new_node = new Node<T>;
      new_node -> data = value;          // Normally we don't add space
      new_node -> next = head;           // around the -> operator.
      head = new_node;
      count++;
    }

    // How about this?

    void push_front(T value) {
      head = new Node<T>{head, value};
      ++count;
    }

This is a OK when T is a simple type like int. But what happens when T is LargeObjectWithState or std::vector<std::vector<int>>?

   void push_front(T value)
                   ^^^^^^^

You are passing the parameter by value. That means there is a copy made before the call is even made (to copy it to the location where parameters are stored). Then inside the function you are copying into a Node object.

     new_node -> data = value;   // Makes another copy of the object.

To get around this we normally pass parameters by reference to avoid the first copy.

   void push_front(T const& value)
                     ^^^^^^          // a reference to the original value.
                                     // but we can't change the value.

So that gets around one copy. But C++11 added a concept called move semantics that allows us to move objects (rather than copy them). Parameters that are movable are marked with && to indicate that we want to bind to an R-Value reference and that we may steal the content of the object as a result of calling the function.

   void push_front(T&& value)

There is some magic you have to do. When you assign these values you need to make sure you do so in a way that tells the destination that you are moving the object to the destination:

    // Your function would look like this:
    void push_front(T&& value) {
      Node<T> *new_node = new Node<T>;
      new_node->data = std::move(value);
      new_node->next = head;
      head = new_node;
      count++;
    }

    // or how about this?

    void push_front(T&& value) {
      head = new Node<T>{head, std::move(value)};
      ++count;
    }

Node. You should have both versions of the function:

    void push_front(T&& value);
    void push_front(T const& value);

There is a third variant called emplacing (but we can get to that in a subsequent review).


Basically the same comments for push_back() as push_front().

    void push_back(T value) {

Here is returning magic numbers?

    int push_after(T value, T after) {
  • 0: Empty List
  • -1: Value does not exist
  • 1: Value was inserted.

Not sure why 0 and -1 are different (in both cases after does not exist in the list). So it you combine these two you could return a boolean value to indicate whether the value was inserted.

If you must stick with three then I would create an enum that makes this relationship readable.

    enum InsertStatus {FailedEmptyList, FailedValueDoesNotExist, OK};
    InsertStatus push_after(T value, T after) {

This looks very similar to some of the code above.

      Node<T> *new_node = new Node<T>;
      new_node -> data = value;
      new_node -> next = tmp -> next;
      tmp -> next = new_node;
      count++;

We now have three places where you are calling new Node and then setting up the values and incrementing count. When you have repeated code you may want to put that in a named function, so that if there is a bug you only have to fix it in one place - and it makes reading the code easier.


If you removed this if code.

      if(count == 1) {
        count--;
        head = NULL;
        return 1;
      }
      head = head -> next;
      count--;

Would it change the behaviour? If there is only one item, then head->next should be nullptr. So head = head->next; would set head to nullptr.

My main issue with this function is that you are leaking the Node. You allocated that node with new, so you should release the memory with delete.

      Node* old = head;
      head = head -> next;

      delete old;           // every call to new should be matched with a call to delete.

Don't think this will ever be true.

       if(tmp -> data == value) {
        delete_back();
        cnt++;
      }

You covered this situation in your main loop above.


You don't want to use std::endl. It prints \n then flushes the stream.

      cout << endl;

The stream is flushed automatically. You flushing it manually is only going to make it very inefficient.


If a function does not change the state of the object, mark it constant.

    int size() const 
    {       // ^^^^^^    
      return count;
    }
\$\endgroup\$
3
  • \$\begingroup\$ What a GREAT review! Thanks alot. \$\endgroup\$
    – Omar_Hafez
    Commented May 12, 2022 at 22:00
  • \$\begingroup\$ Rather than overloading functions for const-lvalue and rvalue operands, I usually recommend passing by value when we're going to move-from. This simplifies implementation and prevents combinatorial explosion of function signatures (very important for constructors). Yes, it means copy+move, but if there's a type where that move is significant compared to allocating our Node, then we want to be looking to improve that type's move constructor rather than complicating our container. \$\endgroup\$ Commented May 13, 2022 at 4:37
  • \$\begingroup\$ @TobySpeight is correct (I keep forgetting this simplification of the interface). \$\endgroup\$ Commented May 13, 2022 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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