Linked List design and implementation - C++

Question

Seeking recommendations on how to improve this code, LL always seem to be a struggle.

A basic linked list that does include next and previous pointers. I used a struct inside of a class, which I'm not sure if that's frowned upon. The program includes 5 basic member functions, one to add to the head of the list, one to add to the tail of the list, one to delete the head, one to delete any index, one that checks the list for duplicate data (based on the data variable in the struct), and a print. Everything works as it should, but I'm just not sure if I was efficient, in fact I'm pretty sure I wasn't. Sorry If im forgetting something, but I'm new here!

1.

class list
{
private:
    struct node
    {
        int data;
        node* next;
        node* prev;
    };

    typedef node* nodePtr;

    nodePtr head;
    nodePtr temp;
    nodePtr prev;

public:
    list(); 
    void add_to_head(int);
    void add_to_tail(int);
    void delete_index(int);
    void check_duplicates(int);
    void print();
};

2.

#include <iostream>
using std:: cout;
using std:: endl;


list::list(void)
{
    head = NULL;
    temp = NULL;
    prev = NULL;
}

void list:: add_to_head(int num)
{
    nodePtr n = new node;

    n->data = num;

    if(head == NULL)
    {
        n->prev = NULL;
        n->next = NULL;
        head = n;

    }
    else
    {
        n->next = head;
        n->prev = NULL;
        head = n;
    }

    return;
}


void list::add_to_tail(int num)
{
    nodePtr n = new node;

    n->data = num;

    if(head == NULL)
    {
        n->prev = NULL;
        n->next = NULL;
        head = n;
    }
    else
    {
        temp = head;

        while(temp->next != NULL)
        {
            temp = temp->next;
        }

        temp->next = n;
        n->prev = temp;
        n->next = NULL;
    }

    return;
}

void list::delete_index(int index)
{
    if(index == 0)
    {
        temp = head->next;
        temp ->prev = NULL;

        prev = head;
        delete prev;

        head = temp;
    }
    else
    {
        nodePtr del = new node;

        int count =0;
        temp = head;

        while(count != index)
        {
            prev = temp;
            temp = temp->next;
            count++;    
        }

        del = temp;

        if(temp->next == NULL)
        {
            prev->next = NULL;
        }
        else
        {
            prev->next = temp->next;
            temp = temp->next;
            temp->prev = prev;
        }

        delete del;
    }

    return;
}


void list::check_duplicates(int num)
{
    int count = -1;

    temp = head;

    while(temp != NULL)
    {
        if(temp->data == num)
        {
            count++;
        }

        temp = temp->next;
    }

    if(count > 0)
    {
        cout<<endl<<endl<<"The number "<<num<<" was found "<<count + 1<<" times."<<endl;
    }

    else if(count == -1)
    {
        if(head == NULL)
        {
            cout<<"The list is empty."<<endl;
        }
        else
        {
            cout<<"The number was not found within the list."<<endl;
        }
    }

    return;
}


void list::print()
{
    temp = head;

    cout<<endl<<"The list:"<<endl;

    while(temp != NULL)
    {
        cout<<temp->data<<" ";
        temp = temp->next;
    }

    return;
}

Answer 1

You can simplify your code a lot.

    if(head == NULL)
    {
        n->prev = NULL;
        n->next = NULL;
        head = n;
    }
    else
    {
        n->next = head;
        n->prev = NULL;
        head = n;
    }

Both sides of this else look identical.
I think you can shorten your code with:

void list:: add_to_head(int num)
{
    nodePtr oldHead = head;
    head = new node{num, oldHead, nullptr);
    // Also you forget to do this bit.
    if (oldHead) {
        oldHead->prev = head;
    }
}

@pm100 covered the temporary variable.

nodePtr temp;
nodePtr prev;

You don't need these as a class member. It should be local to the member functions where they are used.

If I was you I would add another member though.

nodePtr tail;

Then you don't need to search for the tail every time you add a new element.

Const correctness. In a lot of code we pass variables by reference and const reference. If you pass an object by const reference you can only call const members on it.

So you should take care to mark functions that don't mutate the object as const. This will allow you to call the methods from a const reference. Also it enables some compiler optimizations when it knows you are not mutating the object.

So the following functions should probably be const.

void check_duplicates(int) const;
void print() const;

Your print() is fine. But I would make it more generic. Rather than print to std::cout you should print to a generic stream (you can always default to std:::cout.

print(std::ostream& str = std::cout) const;

Also in C++ printing is usually done via operator<<. So I would add this function. All it needs to do is call the print function passing the stream.

std::ostream& operator<<(std::ostream& str, List const& data)
{
     data.print(str);
     return str;
}

Answer 2

• Class design

  A member called temp is an immediate red flag. It doesn't represent any state of the list, it is just a variable used to traverse a list, and shall be defined where it is used. Make it local to appropriate methods.

  Same applies to prev.

  Some methods (particularly, delete_index) may crash on bad inputs. If it is a conscious design decision, it must be documented.

  I highly recommend to have nodeptr tail; member.

• struct node better have a constructor

  node(int num): data(num), prev(nullptr), next(nullptr) {}
  

• add_to_head doesn't update the old head's prev. Besides, it looks unnecessary complicated. Consider

  add_to_head(int num) {
      nodeptr n = new node(num);
      n->next = head;
      if (head) {
          head->prev = n;
      }
      head = n;
  }
  

• delete_index leaks memory:

      del = new node;
      ....
      del = temp;
  

Answer 3

A few basics.

You might want to consider a naming convention for member variables. m_head or head_ are common ones. Some people find this useful, others not.

I assume the few places you have an extra space after :: is just a typo

use nullptr instead of NULL

It is unusual to have a print method for a container like this. Why not a save, load, etc. As long as you make it trivial to iterate over the list then you dont need a print

delete_index is an odd name. It suggests that an index is going to be deleted. I would call it delete_at or just plain delete.

temp (and probably prev) do not need to be class members. They are just local variables of some methods

major points

OK how about access methods. Like get_at and first / next. At the moment I can put things in the list but not get them out!

c++ people will expect iterators

It only stores ints, make it generic - you will learn a lot